Divide and conquer inspired sorting

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

[Image Analyst]

How did you get that? If you take out 4, then you're left with [1,2,3] and [5,6,7]. Now if you take the middle of each of those you get 2 and 6. Yet you got 2 and 5. How?

[Francesco Mancino]

I was mistaken, hur correct sequence is [4,2,6,1,3,5,7].

Answer 1

[Arnab Sen]

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.