排序演算法
by Aaron • 10/23/2022, 7:34:24 AM
Table of Content
Insertion sort
逐一將要排序的資料插入已排序好的序列中
notion:
[ sorted array | unsorted array]
[ "a" ] : target
example
given array: [5, 3, 4, 6, 1]
1. 3 < 5 :
swap(array, 0, 1)
=> ["3", 5 | 4, 6, 1]
2. 4 < 5 :
swap(array, 2, 1)
=> [3, "4", 5 | 6, 1]
3. 6 > 5 :
=> [3, 4, 5, 6 | 1]
4. 1 < 6 :
swap(array, 4, 3)
=> [3, 4, 5, "1", 6]
1 < 5 :
swap(array, 3, 2)
=> [3, 4, "1", 5, 6]
1 < 4 :
swap(array, 2, 1)
=> [3, "1", 4, 5, 6]
1 < 3 :
swap(array, 1, 0)
=> ["1", 3, 4, 5, 6]
finish
func insertionSort(array []int) []int {
for i := 1; i < len(array); i++ {
j := i - 1
target := array[i]
for j >= 0 && target < array[j] {
array[j+1] = array[j]
j--
}
array[j+1] = target
}
return array
}
Selection sort
將 array 分成排序好的和未排序好的 array，逐一將未排序好的 array 的最大（最小）值換到未排序好的 array 的最後面
notion:
[ sorted array | unsorted array]
[ "a" ] : max
example
given array: [5, 3, 4, 6, 1]
1. max value: 6
=> [5, 3, 4, 1 | 6]
2. max value: 5
=> [3, 4, 1 | 5, 6]
3. max value: 4
=> [3, 1 | 4, 5, 6]
4. max value: 3
=> [1, 3, 4, 5, 6]
finish
func prefixMax(array []int, i int) int {
if i > 0 {
j := prefixMax(array, i-1)
if array[j] > array[i] {
return j
}
}
return i
}
func sort(array []int, i int) {
if i > 0 {
j := prefixMax(array, i)
array[i], array[j] = array[j], array[i]
sort(array[:], i-1)
}
}
func selectionSort(array []int) []int {
sort(array[:], len(array)-1)
return array
}
Bubble sort
每一輪從 unsorted array index 0 開始往後兩兩相比較，將較大（小）的往後交換，每一輪都將最大的值換到 unsorted array 後面，當一輪內沒交換過則代表排序完畢
notion:
[ sorted array | unsorted array]
[ "a, b" ] : comparision
example
given array: [5, 3, 4, 6, 1]
1. ["5, 3", 4, 6, 1] => 5 > 3
swap(array, 1, 0)
=> [3, 5, 4, 6, 1]
2. [3, "5, 4", 6, 1] => 5 > 4
swap(array, 2, 1)
=> [3, 4, 5, 6, 1]
3. [3, 4, "5, 6", 1] => 6 > 5
do nothing
=> [3, 4, 5, 6, 1]
4. [3, 4, 5, "6, 1"] => 6 > 1
swap(array, 4, 3)
=> [3, 4, 5, 1, 6]
-------- finish first round -----
1. ["3, 4", 5, 1 | 6] => 4 > 3
do nothing
=> [3, 4, 5, 1 | 6]
2. [3, "4, 5", 1 | 6] => 5 > 4
do nothing
=> [3, 4, 5, 1 | 6]
3. [3, 4, "5, 1" | 6] => 1 < 5
swap(array, 3, 2)
=> [3, 4, 1, 5 | 6]
-------- finish second round -----
1. ["3, 4", 1 | 5, 6] => 4 > 3
do nothing
=> [3, 4, 1 | 5, 6]
2. [3, "4, 1" | 5, 6] => 1 < 4
swap(array, 2, 1)
=> [3, 1, 4 | 5, 6]
-------- finish third round -----
1. ["3, 1" | 4, 5, 6] => 1 < 3
swap(array, 1, 0)
=> [1, 3 | 4, 5, 6]
finish
func bubbleSort(array []int) []int {
n := len(array)
for i := 0; i < n; i++ {
isSorted := true
for j := 0; j < n-i-1; j++ {
if array[j] > array[j+1] {
array[j], array[j+1] = array[j+1], array[j]
isSorted = false
}
}
if isSorted {
break
}
}
return array
}
Merge sort
Merge sort 屬於 divide and conquer 的方式，將 array 切割成 subarray 在合併成 sorted array
example
given array: [5, 3, 4, 6, 1]
5, 3, 4, 6, 1
/ \
5, 3 4, 6, 1
/ \ / \
5 3 4 6, 1
\ / | / \
3, 5 | 6 1
| | \ /
| | 1, 6
| \ /
| 1, 4, 6
\ /
1, 3, 4, 5, 6
func merge(left []int, right []int) []int {
l := len(left) + len(right)
arr := make([]int, l)
arr1 := make([]int, len(left))
arr2 := make([]int, len(right))
arr1 = append(arr1, math.MaxInt)
arr2 = append(arr2, math.MaxInt)
i1, i2 := 0, 0
for i := 0; i < l; i++ {
if arr1[i1] < arr2[i2] {
arr[i] = arr1[i1]
i1++
} else {
arr[i] = arr2[i2]
i2++
}
}
return arr
}
func divideAndConquer(array []int) []int {
if len(array) < 2 {
return array
}
middle := len(array) / 2
leftArray := array[:middle]
rightArray := array[middle:]
return merge(divideAndConquer(leftArray), divideAndConquer(rightArray))
}
func mergeSort(array []int) []int {
return divideAndConquer(array)
}
Quick sort
在 array 找一個基準點，將此 array 變成基準點前的 subarray 都小於基準點，基準點後的 subarray 都大於基準點，此過程稱作 partition。接著再對基準點左右的 subarray 都做 partition。
notion:
"a": baseline
example
given array: [5, 3, 4, 6, 1]
base: array[0]
1. [3, 4, 1, "5", 6]
=> left: [3, 4, 1, 5], right: [6]
2. [1, "3", 4, 5 | 6]
func partition(array []int) int {
base := array[0]
pivot := -1
for i := 0; i < len(array); i++ {
if array[i] <= base {
pivot += 1
array[pivot], array[i] = array[i], array[pivot]
}
}
array[pivot], array[0] = array[0], array[pivot]
return pivot + 1
}
func sorting(array []int) {
if len(array) < 2 {
return
}
pivot := partition(array)
sorting(array[:pivot])
sorting(array[pivot:])
}
func quickSort(array []int) []int {
sorting(array[:])
return array
}
Heap sort
為 selection sort 的變形，將找 unsorted array 的最大值的過程使用 heap。過程分成兩部分， 1. buildHeap: 使 array 符合 heap 的規則。 2. 不停的砍斷 heap 的 head, 與 heapify
example
given array: [5, 3, 4, 6, 1]
5 "5" <- heapify
/ \ / \
heapify-> "3" 4 => 6 4
/ \ / \
6 1 3 1
6
=> / \ => [6, 5, 4, 3, 1]
5 4
/ \
3 1
=> cut off head
"1" <-heapify
=> / \ => [1, 5, 4, 3 | 6]
5 4
/
3
5 5
=> / \ => / \
heapify-> "1" 4 3. 4
/ /
3 1
=> cut off head
1
=> / \ => [1, 3, 4 | 5, 6]
heapify-> 3 4
...
func heapify(array []int, n int, i int) {
left := 2*i + 1
right := 2*i + 2
max := i
if left < n && array[left] > array[max] {
max = left
}
if right < n && array[right] > array[max] {
max = right
}
if max != i {
array[max], array[i] = array[i], array[max]
heapify(array[:], n, max)
}
}
// parent: ( i - 1 ) / 2
// left: i * 2 + 1
// right: i * 2 + 2
func buildHeap(array []int, n int) {
lastNode := n - 1
parent := (lastNode - 1) / 2
for i := parent; i >= 0; i-- {
heapify(array[:], n, i)
}
}
func heapSort(array []int) []int {
n := len(array)
buildHeap(array[:], n)
for i := n - 1; i > 0; i-- {
array[0], array[i] = array[i], array[0]
heapify(array[:], i, 0)
}
return array
}
Comparision
| algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Insertion sort | o(n) | o(n^2) | o(n^2) |
| Selection sort | o(n^2) | o(n^2) | o(n^2) |
| Bubble sort | o(n) | o(n^2) | o(n^2) |
| Merge sort | o(nlogn) | o(nlogn) | o(nlogn) |
| Quick Sort | o(nlogn) | o(nlogn) | o(n^2) |
| Heap sort | o(nlogn) | o(nlogn) | o(nlogn) |