Insertion Sort/插入排序

Introduction to Algorithm 2.1

The book says that the insertion sort is a”n efficient algorithm for sorting a small number of elements”.

EN

Algorithm

The idea of insertion sort is also easy, given a list of numbers, simply loop through whole list, if the current value is larger than the left ones, move the current value to the index of the correct position, then move to the next value.

I found the example from Wikipedia:

The original list is [6, 5, 3, 1, 8, 7, 2, 4]. With the 1st value 6, there is no smaller value on its left, so the first round remains the same.

With the 2nd value 5, it’s obvious that 5 is smaller than 6, so move 5 to the left hand of 6, and then the list becomes [5, 6, 3, 1, 8, 7, 2, 4].

With the 3rd value 3, it’s smaller than both 5 and 6, so move 3 to the left hand of 5, and then the list becomes [3, 5, 6, 1, 8, 7, 2, 4].

Repeat same step for the rest values in list, eventually the list is sorted: [1, 2, 3, 4, 5, 6, 7, 8].

Complexity

Time Complexity

In the best case, time complexity is O(n), so it’s a good thing. However, in the worst case, as [8, 7, 6, 5, 4, 3, 2, 1], there is (n - 1) values in total require to be moved, and each value need to be move n times, so the number of inversion is: , which yields an O() time complexity.

On the other hand, in the best case scenario, the time complexity is O() since all the elements in the list needs to be iterated.

Space Complexity

The space complexity is O() since the algorithm only require 1 extra space to store current value.

Pseudocode

From the book, on page 18:

1
2
3
4
5
6
7
8
9
Insertion-sort (A)
for j = 2 to A.length
key = A[j]
// insert A[j] into the sorted sequence A[1 .. j-1].
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key

CN

算法

这张图就能够很好的演示插入排序的算法。

从列表的最左第二个元素开始(),将位于的数值与左边的位置,进行判断。若是位于的数值比当前数值大,则将数值向后移一位——。以此类推,直到位于数值比当前的数值大(或相等)后,则说明之间的数列已经排序。

以这张图里的[6, 5, 3, 1, 8, 7, 2, 4]为例,从第二个数值开始从左算起,,所以向右移一位,因为的左侧没有其他数值,此时的列表为: [5, 6, 3, 1, 8, 7, 2, 4]。

对于第三个数值来说,,因此再一次向右侧移动一位。3再与5进行比较,也需要向右移动一位,此时的数列为:[3, 5, 6, 1, 8, 7, 2, 4]。

重复排序剩下的数值,直到最后完成对整个数列的排序——[1, 2, 3, 4, 5, 6, 7, 8]。


复杂度

时间复杂度

理想条件下,数组中所有的数值都是排序过了,那么只需要遍历从位数值,也因此时间复杂度是

最差条件下,数组中的数值是由大到小排列的,那么就需要遍历位数值,然后每一位数值都需要向前移动位,那么时间复杂度就是,换言之,时间复杂度就是 O()。

空间复杂度

只需要额外的一个数值去保存目前正在遍历的数值,因此空间复杂度是 O()。


伪代码

1
2
3
4
5
6
7
8
9
Insertion-sort (A)
for j = 2 to A.length
key = A[j]
// insert A[j] into the sorted sequence A[1 .. j-1].
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key
-------The end of this article  Thank you for your reading-------
0%