Divide and conquer inspired sorting

5 views (last 30 days)
Francesco Mancino
Francesco Mancino on 26 Apr 2016
Commented: Francesco Mancino on 28 Apr 2016
Hey!
I was wandering if there was a way in Matlab to pick the middle number of an array and then the middle number of the two subarrays formed by picking that one, and so on until you have "rearranged" the array. For example [1,2,3,4,5,6,7] would become [4,2,6,1,3,5,7]. Is there any premade function for it? Is there a way to code that easy?
Thanks for any help! Francesco
  2 Comments
Francesco Mancino
Francesco Mancino on 28 Apr 2016
I was mistaken, hur correct sequence is [4,2,6,1,3,5,7].

Sign in to comment.

Answers (1)

Arnab Sen
Arnab Sen on 28 Apr 2016
Hello Francesco,
MATLAB does not have any function to directly achieve this.
As Image Analyst has already pointed out, I am assuming 5 and 6 is somehow mistakenly swapped in the resulting output. The resulting array should be [4,2,6,1,3,5,7]. Let,
a1=[1,2,3,4,5,6,7]
a2=[4,2,6,1,3,5,7]
In that case I notice that, if a1 is the node sequence of the Inorder traversal of a height balanced binary tree, then a2 is sequence of the level order traversal (more specifically, traverse leftmost node first for each level) of the same tree. So we can create a height balanced binary tree from a1 as below (pseudo code):
class node
{
int data;
node left;
node right;
}
node newNode(int data)
{
node temp=new node;
node.data=data;
node.left=node.right=NULL;
return node;
}
node createTree(int[] a1,int start,int end)
{
if(a1.size==0);
return NULL;
int mid=start+(end-start)/2;
node root=newNode(a1[mid]);
root.left=createTree(a1,start,mid-1);
root.right=createTree(a1,mid+1,end);
return root;
}
call the function createTree as
node tree= createTree(a1,1,size(a1));
Now, we need to do level order traversal for the generated Tree. Consider the following code snippet for that:
Queue q;
Node curr=Tree;
q.push(curr);
k=0;
while(q.empty()!=true) do
Node temp=q.pop();
a2[k++]=temp.data;
q.push(temp.left);
q.push(temp.right);
end
output the resulting array a2.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by