Sort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

func sortArray(nums []int) []int {
    arrLen := len(nums)
    // l: left boundary
    // r: right boundary
    l, r := 0, arrLen - 1

    helperArray := make([]int, arrLen)

    mergeSort(nums, helperArray, l, r)

    return nums
}

// * no need to return []int, slice is passed by reference
func mergeSort(nums, helperArray []int, l, r int) {
    // only one element, no need to sort
    if l == r {
        return
    }

    mid := (l + r) / 2
    // sort left half of the array
    mergeSort(nums, helperArray, l, mid)
    // sort right half of the array
    mergeSort(nums, helperArray, mid+1, r)

    // no need to hold the result using a new array
    // leftHalfArray := mergeSort(nums, helperArray, l, mid)
    // rightHalfArray := mergeSort(nums, helperArray, mid+1, r)

    // This helper array can be declared once and used throughout all iterations;
    // If declared this way, the process of saving tmp sorting result back to the
    // original array is more redundant, and more space is needed within each iteration.
    // var helperArray []int
    // https://leetcode.com/problems/sort-an-array/submissions/1221266267/

    // lp: leftPointer
    // rp: rightPointer
    lp, rp := l, mid+1
    // hi: helper array starting index
    hi := l
    for lp <= mid && rp <= r {
        if nums[lp] < nums[rp] {
            helperArray[hi] = nums[lp]
            lp++
        } else {
            helperArray[hi] = nums[rp]
            rp++
        }
        hi++
    }

    // drains what's left of the sorted left-half array and the sorted right-half array
    for lp <= mid {
        helperArray[hi] = nums[lp]
        lp++
        hi++
    }
    for rp <= r {
        helperArray[hi] = nums[rp]
        rp++
        hi++
    }

    // save result
    for i := l; i <= r; i++ {
        nums[i] = helperArray[i]
    }

    return
}
func main() {
    var n int
    fmt.Scanf("%d", &n)
    nums := make([]int, n)
    tmp = make([]int, n)
    for i := range nums {
        fmt.Scanf("%d", &nums[i])
    }
    
    sortArray(nums)
    for _, n := range nums {
        fmt.Printf("%d ", n)
    }
    fmt.Println()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func bubbleSort(nums []int) {
    arrLen := len(nums)
	// whether i < arrLen or i < arrLen - 1 doesn't matter much
	for i := 0; i < arrLen; i++ {
        for j := 0; j < arrLen-i-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

func bubbleSort2(nums []int) {
    arrLen := len(nums)
	// whether i < arrLen or i < arrLen - 1 doesn't matter much
	for i := 0; i < arrLen; i++ {
        swapped := false
		for j := 0; j < arrLen-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = true
			}
		}
        // already sorted
        if !swapped {
            break
        }
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func selectionSort(num []int) {
    arrLen := len(nums)
	for i := 0; i < arrLen; i++ {
		minIdx := i
		for j := i + 1; j < arrLen; j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		// swap is only needed when i != minIdx
		nums[i], nums[minIdx] = nums[minIdx], nums[i]
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func insertionSort(nums []int) {
	arrLen := len(nums)
	for i := 1; i < arrLen; i++ {
		currVal := nums[i]
		// idx: index that comparing starts at
		idx := i - 1
		for idx >= 0 && currVal < nums[idx] {
			// swap
			nums[idx+1], nums[idx] = nums[idx], nums[idx+1]
			idx--
		}
	}
}