Aaron Li

Algorithm: 排序演算法

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

algorithmBest CaseAverage CaseWorst Case
Insertion sorto(n)o(n^2)o(n^2)
Selection sorto(n^2)o(n^2)o(n^2)
Bubble sorto(n)o(n^2)o(n^2)
Merge sorto(nlogn)o(nlogn)o(nlogn)
Quick Sorto(nlogn)o(nlogn)o(n^2)
Heap sorto(nlogn)o(nlogn)o(nlogn)