finding best and wost case in Insertion Sort

Question

nkumar 2013-7-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/83363-finding-best-and-wost-case-in-insertion-sort

I have a code from mathworks for insertion sort

function sorted = insertion_sort(unsorted)
    array_size = size(unsorted,2);
    for pivot = 2:array_size
        for j = 1:pivot-1
            if (unsorted(j)>unsorted(pivot))
                temp = unsorted(pivot);
                unsorted (j+1:pivot) = unsorted (j:pivot-1);
                unsorted(j) = temp        
            end
        end
    end
  sorted = unsorted; 
end

suppose mu unsorted value is [5 1 2 9 7 3 8 ]

kindly tell how to calculate best worst and average case

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

请先登录，再进行评论。

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

Answer 1

Roger Stafford 2013-7-28

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/83363-finding-best-and-wost-case-in-insertion-sort#answer_92922

在 MATLAB Online 中打开

It is not clear what you are asking. With a given array such as the one you describe, there can be no "best" or "worst" case. The amount of processing is exactly determined by that array.

In general the worst cases will occur when the initial array is entirely descending and the best cases would be those in which the initial array is already ascending. That is because the amount of shifting in the line

unsorted (j+1:pivot) = unsorted (j:pivot-1);

is maximized or minimized in the two respective cases.

However, this sorting algorithm is far from optimum since it is of order n^2 operations with n the length of the array. An efficient algorithm such as "merge" sorting can accomplish a sort operation with only order n*log(n) operations, and for a large array this can be significantly fewer operations.