finding best and wost case in Insertion Sort

1 次查看（过去 30 天）
nkumar
nkumar 2013-7-28
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

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

回答（1 个）

Roger Stafford
Roger Stafford 2013-7-28
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.

类别

在 Help Center 和 File Exchange 中查找有关 Matrices and Arrays 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by