Selection Sort

Idea

Selection Sort repeatedly picks the minimum (or maximum) from the unsorted part and places it at the end of the sorted part until done.

选择排序演示

6425122211

下一步

Algorithm

1. In each pass, find the minimum in the unsorted part and swap with its first element.
2. Repeat $n-1$ passes until fully sorted.

Pseudo-code:

for i = 0 to n-2:
    min = i
    for j = i+1 to n-1:
        if A[j] < A[min]:
            min = j
    if min != i:
        swap(A[i], A[min])

Complexity

• Best/worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

Run selection sort on $A = [64, 25, 12, 22, 11]$ and show each pass.

参考答案

思路：每趟选最小放前。

步骤：

1. 初始：[64, 25, 12, 22, 11]
2. 第 1 趟：[11, 25, 12, 22, 64]
3. 第 2 趟：[11, 12, 25, 22, 64]
4. 第 3 趟：[11, 12, 22, 25, 64]
5. 第 4 趟：[11, 12, 22, 25, 64]

答案：如上，每趟最小归位。

Exercise 2

What are the time and space complexities of selection sort?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n^2)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n^2)$，空间 $O(1)$。

PreviousBubble SortBubble sort basics, algorithm flow, complexity, and practice. NextShell SortShell sort basics, algorithm flow, complexity, and practice.