8 Types of Sort
Go codePermalink
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| "math/rand" | |
| "time" | |
| ) | |
| const TEST_NUM = 10 | |
| const TEST_LIMIT = 50 | |
| func main() { | |
| randNumList := GetRandomList() | |
| fmt.Printf("Origianl List : \t") | |
| printList(randNumList) | |
| fmt.Printf("Bubble Sort : \t\t") | |
| printList(BubbleSort(randNumList)) | |
| fmt.Printf("Selection Sort : \t") | |
| printList(SelectionSort(randNumList)) | |
| fmt.Printf("Insertion Sort : \t") | |
| printList(InsertionSort(randNumList)) | |
| fmt.Printf("Shell Sort : \t\t") | |
| printList(ShellSort(randNumList)) | |
| fmt.Printf("Quick Sort : \t\t") | |
| printList(QuickSort(randNumList)) | |
| fmt.Printf("Heap Sort : \t\t") | |
| printList(HeapSort(randNumList)) | |
| fmt.Printf("Merge Sort : \t\t") | |
| printList(MergeSort(randNumList)) | |
| fmt.Printf("Radix Sort : \t\t") | |
| printList(RadixSort(randNumList)) | |
| } | |
| func GetRandomList() []int { | |
| result := []int{} | |
| cashMap := map[int]bool{} | |
| src := rand.NewSource(time.Now().UTC().UnixNano()) | |
| r := rand.New(src) | |
| for i := 0; i < TEST_NUM; i++ { | |
| randNum := r.Intn(TEST_LIMIT) | |
| if cashMap[randNum] { | |
| // loop again | |
| i-- | |
| continue | |
| } | |
| cashMap[randNum] = true | |
| result = append(result, randNum) | |
| } | |
| return result | |
| } | |
| func printList(numList []int) { | |
| for i := 0; i < len(numList); i++ { | |
| fmt.Printf("%d\t", numList[i]) | |
| } | |
| fmt.Printf("\n") | |
| } | |
| func deepCopyList(numList []int) []int { | |
| result := make([]int, len(numList)) | |
| copy(result, numList) | |
| return result | |
| } | |
| // time : O(n²) | |
| func BubbleSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| for i := 0; i < len(result)-1; i++ { | |
| for j := 0; j < len(result); j++ { | |
| if j+1 < len(result) && result[j] > result[j+1] { | |
| swap(result, j, j+1) | |
| } | |
| } | |
| } | |
| return result | |
| } | |
| // time : O(n²) | |
| func SelectionSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| for i := 0; i < len(result)-1; i++ { | |
| min := result[i] | |
| minIndex := i | |
| for j := i + 1; j < len(result); j++ { | |
| if result[j] < min { | |
| min = result[j] | |
| minIndex = j | |
| } | |
| } | |
| if minIndex > i { | |
| swap(result, i, minIndex) | |
| } | |
| } | |
| return result | |
| } | |
| // time : O(n²) | |
| func InsertionSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| for i := 1; i < len(result); i++ { | |
| curVal := result[i] | |
| var j int | |
| for j = i - 1; j >= 0 && curVal < result[j]; j-- { | |
| // move next | |
| result[j+1] = result[j] | |
| } | |
| result[j+1] = curVal | |
| } | |
| return result | |
| } | |
| // time : O(n²) | |
| func ShellSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| interval := int(float32(len(result)) * 0.5) | |
| for interval > 0 { | |
| for i := 0; i < len(result); i++ { | |
| intervalSort(result, i, len(result)-i, interval) | |
| } | |
| interval = int(float32(interval) * 0.5) | |
| } | |
| return result | |
| } | |
| func intervalSort(numList []int, start, end, interval int) { | |
| for i := start + interval; i < end; i += interval { | |
| curVal := numList[i] | |
| var j int | |
| for j = i - interval; j >= start && curVal < numList[j]; j -= interval { | |
| numList[j+interval] = numList[j] | |
| } | |
| numList[j+interval] = curVal | |
| } | |
| } | |
| // time : O(n²) | |
| func QuickSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| qSort(result, 0, len(numList)-1) | |
| return result | |
| } | |
| func qSort(numList []int, start, end int) { | |
| if start >= end { | |
| return | |
| } | |
| middle := start + int(float32(end-start)*0.5) | |
| pivot := numList[middle] | |
| left := start | |
| right := end | |
| for left <= right { | |
| for numList[left] < pivot { | |
| left++ | |
| } | |
| for numList[right] > pivot { | |
| right-- | |
| } | |
| if left <= right { | |
| // swap | |
| swap(numList, left, right) | |
| left++ | |
| right-- | |
| } | |
| } | |
| if start < right { | |
| qSort(numList, start, right) | |
| } | |
| if end > left { | |
| qSort(numList, left, end) | |
| } | |
| } | |
| // time : O(nlogn) | |
| func HeapSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| // rearrange heap | |
| for i := int(float32(len(result))*0.5 - 1); i >= 0; i-- { | |
| heapify(result, len(result), i) | |
| } | |
| for i := len(result) - 1; i >= 0; i-- { | |
| // move current root to end | |
| swap(result, 0, i) | |
| // call max heapify on the reduced heap | |
| heapify(result, i, 0) | |
| } | |
| return result | |
| } | |
| func heapify(numList []int, heapSize, rootIndex int) { | |
| newRoot := rootIndex | |
| left := rootIndex * 2 | |
| right := rootIndex*2 + 1 | |
| if left < heapSize && numList[left] > numList[newRoot] { | |
| newRoot = left | |
| } | |
| if right < heapSize && numList[right] > numList[newRoot] { | |
| newRoot = right | |
| } | |
| if newRoot != rootIndex { | |
| swap(numList, rootIndex, newRoot) | |
| // recursice for subtree | |
| heapify(numList, heapSize, newRoot) | |
| } | |
| } | |
| // 2-way merge | |
| // time : O(nlogn) | |
| func MergeSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| return mSort(result) | |
| } | |
| func mSort(numList []int) []int { | |
| if len(numList) < 2 { | |
| return numList | |
| } | |
| halfIndex := int(float32(len(numList)) * 0.5) | |
| first := mSort(numList[:halfIndex]) | |
| second := mSort(numList[halfIndex:]) | |
| return merge(first, second) | |
| } | |
| func merge(first, second []int) []int { | |
| result := []int{} | |
| i := 0 | |
| j := 0 | |
| for i < len(first) && j < len(second) { | |
| if first[i] < second[j] { | |
| result = append(result, first[i]) | |
| i++ | |
| } else { | |
| result = append(result, second[j]) | |
| j++ | |
| } | |
| } | |
| for ; i < len(first); i++ { | |
| result = append(result, first[i]) | |
| } | |
| for ; j < len(second); j++ { | |
| result = append(result, second[j]) | |
| } | |
| return result | |
| } | |
| // time : O(nlogn) | |
| func RadixSort(numList []int) []int { | |
| result := deepCopyList(numList) | |
| largest := getLargestNum(result) | |
| size := len(numList) | |
| significantDigit := 1 | |
| semiSorted := make([]int, size, size) | |
| for largest/significantDigit > 0 { | |
| bucket := [10]int{0} | |
| for i := 0; i < size; i++ { | |
| bucket[(numList[i]/significantDigit)%10]++ | |
| } | |
| for i := 1; i < 10; i++ { | |
| bucket[i] += bucket[i-1] | |
| } | |
| for i := size - 1; i >= 0; i-- { | |
| key := (numList[i] / significantDigit) % 10 | |
| bucket[key]-- | |
| semiSorted[bucket[key]] = numList[i] | |
| } | |
| for i := 0; i < size; i++ { | |
| numList[i] = semiSorted[i] | |
| } | |
| significantDigit *= 10 | |
| } | |
| return semiSorted | |
| } | |
| func getLargestNum(numList []int) int { | |
| max := 0 | |
| for _, v := range numList { | |
| if v > max { | |
| max = v | |
| } | |
| } | |
| return max | |
| } | |
| func swap(numList []int, i, j int) { | |
| temp := numList[i] | |
| numList[i] = numList[j] | |
| numList[j] = temp | |
| } |
outputPermalink
Origianl List : 13 20 22 31 21 43 25 35 1 17
Bubble Sort : 1 13 17 20 21 22 25 31 35 43
Selection Sort : 1 13 17 20 21 22 25 31 35 43
Insertion Sort : 1 13 17 20 21 22 25 31 35 43
Shell Sort : 1 13 17 20 21 22 25 31 35 43
Quick Sort : 1 13 17 20 21 22 25 31 35 43
Heap Sort : 1 13 17 20 21 22 25 31 35 43
Merge Sort : 1 13 17 20 21 22 25 31 35 43
Radix Sort : 1 13 17 20 21 22 25 31 35 43