ROSALIND｜Insertion Sort (INS)

發表於

求一個整數數列使用 insertion sort 所需的數字交換次數

Given: A positive integer $n \leq 10^3$ and an array $A[1..n]$ of integers.

Return: The number of swaps performed by the insertion sort algorithm on $A[1..n]$.

(https://rosalind.info/problems/ins/)

Insertion sort 的流程很像整理手牌，由左至右逐一檢查數字。如果當前數字比前面的數字小就往前挪，直到所有數字都被排序。

1
2
3
4
1. 尋找錯位數字
           ▼
[ 1  3  4  2  5  6 ]
        ~~~~
1
2
3
4
2. 向前插入（位移兩次）
   ┌───2───┐
   ↓       |
[ 1  3  4  □  5  6 ]
1
2
3. 完成排序
[ 1  2  3  4  5  6 ]

此題要求計算排序時數字位移的次數，所以在我新增了一個計數器，讓它在每次插入時更新。

1
2
3
4
5
6
7
8
9
10
def ins(l):
    swap_num = 0
    for i in range(1, len(l)):
        if l[i-1] > l[i]:  # 發現順序錯誤的數字
            j = i
            while j > 0 and l[j-1] > l[i]: # 向前位移
                j = j - 1
                swap_num = swap_num + 1 # 每位移一單位就更新一次計數器
            l.insert(j, l.pop(i)) # 抽出該數字放到正確的位置
    return l, swap_num