Wrong output for strand sort algorithm

Question

mustafa 2023-5-31

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1976044-wrong-output-for-strand-sort-algorithm

评论： mustafa 2023-6-9

This sorting code depends on strand sort algorithm but when I enter input for example v1=[5,9,13,24,1,6] wrong output given(ans=5;9;13;24;5;9;13;24;1;6). Furthermore, matlab do not give any error but warning which indicates preallocating. How can I amend this code?

function result=myystrandsort(lst)
if length(lst)<=1
    result=lst;
    return;
end
result=[];
sorted=[];
while ~isempty(lst)
    sorted(end+1)=lst(1);
    lst(1)=[];
    it=1;
    while it<=length(lst)
        if sorted(end)<=lst(it)
            sorted(end+1)=lst(it);
            lst(it)=[];
        else
            it=it+1;
        end
    end
    result=[result,sorted];
end
result=result(:);

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Aman 2023-6-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1976044-wrong-output-for-strand-sort-algorithm#answer_1248119

在 MATLAB Online 中打开

Hi Mustafa,

There are a few corrections to be made in your code:

You are not clearing the sorted array after the inner while loop, which is causing the elements to reappear in the result. To fix this, you can define the sorted array inside the while loop like this:

while ~isempty(lst) 
    sorted=[]; 
    sorted(1)=lst(1); 
    lst(1)=[]; 
    it=1; 

Additionally, you cannot merge result and sorted arrays directly, since both arrays are sorted, you need to merge them in a sorted manner.

Hope this helps!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Harsh Saxena 2023-6-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1976044-wrong-output-for-strand-sort-algorithm#answer_1248134

在 MATLAB Online 中打开

Hi Mustafa,

There are mainly two problems with the code:

Sorted list needs to be empty after every iteration of while ~isempty loop.
You need to merge the list in sorted order.

function result=myystrandsort(lst)
    if length(lst)<=1
        result=lst;
        return;
    end
    result=[];
    while ~isempty(lst)
        sorted = [];
        sorted(end+1)=lst(1);
        lst(1)=[];
        it=1;
        while it<=length(lst)
            if(sorted(end)<=lst(it))
                sorted(end+1)=lst(it);
                lst(it)=[];
            else
                it=it+1;
            end
        end
        result=merge_sorted(result,sorted);
    end
    result=result(:);
end

Here the merge_sorted function can be created as follows:

function outArray = merge_sorted(in1,in2)
  inAll = [in1(:); flipud(in2(:))]; 
  N = numel(inAll);  
  
  iFront = 1;           
  iBack = N;          
  outArray = zeros(N,1);  
  
  for iOut = 1:N                  
    if inAll(iFront) <= inAll(iBack)   
      outArray(iOut) = inAll(iFront); 
      iFront = iFront+1;              
    else                               
      outArray(iOut) = inAll(iBack);   
      iBack = iBack-1;                
    end
  end
  
end