Divide and conquer inspired sorting

1 次查看（过去 30 天）
Francesco Mancino
Francesco Mancino 2016-4-26
评论： Francesco Mancino 2016-4-28
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 个评论
Image Analyst
Image Analyst 2016-4-26
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
Francesco Mancino 2016-4-28
I was mistaken, hur correct sequence is [4,2,6,1,3,5,7].

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Arnab Sen
Arnab Sen 2016-4-28
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.

类别

在 Help Center 和 File Exchange 中查找有关 Network Connection and Exploration 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by