Sorting Algorithms

Sep 23, 2016

Sorting is fundamental, but different algorithms embody different ideas worth studying. To reinforce my understanding, I am implementing the basic sorting algorithms by hand.

Translated from Chinese with AI · Read the original

Sorting is fundamental, but different algorithms embody different ideas worth studying. To reinforce my understanding, I am implementing the basic sorting algorithms by hand.

Quicksort

Given an array:

Choose a pivot, then put values smaller than it on the left and larger values on the right.
Repeat step 1 on the subarrays to the left and right of the pivot.

1
def quickSort(arr: Array[Int], begin: Int, end: Int): Unit = {
2
  if (end > begin) {
3
    var (i, j) = (begin, end)
4
    val pivot = arr(i)
5

6
    while (i < j) {
7
      while (j > i && arr(j) > pivot) {
8
        j -= 1
9
      }
10

11
      if (j > i) {
12
        swap(arr, i, j)
13
      }
14

15
      while (i < j && arr(i) < pivot) {
16
        i += 1
17
      }
18

19
      if (i < j) {
20
        swap(arr, i, j)
21
      }
22
    }
23

24
    quickSort(arr, begin, i-1)
25
    quickSort(arr, i+1, end)
26
  }
27
}

Insertion Sort:

1
def insertSort(arr: Array[Int]): Unit = {
2
  arr.indices.foreach(i => {
3
    val v = arr(i)
4
    (i to 1 by -1).foreach(j => {
5
      if (arr(j-1) > arr(j)) {
6
        val temp = arr(j)
7
        arr.update(j, arr(j-1))
8
        arr.update(j-1, temp)
9
      }
10
    })
11
  })
12
}

Bubble Sort

Traverse all elements and keep swapping them. n * n: a rather silly algorithm.

1
def bubbleSort(arr: Array[Int]): Unit = {
2
  arr.indices.foreach(i => {
3
    (0 until arr.length - 1).foreach(j => {
4
      if (arr(j) > arr(j+1)) {
5
        swap(arr, j, j+1)
6
      }
7
    })
8
  })
9
}

Selection Sort

Too silly a sorting algorithm to bother writing…

Merge Sort

Merge two sorted arrays: sorted array = merge(sorted array(0 -> mid), sorted array(mid+1 -> N)), giving a recursive procedure.

1
def mergeSort(arr: Array[Int], begin: Int, end: Int): Array[Int] = {
2
  if (begin == end) Array(arr(begin))
3
  else {
4
    val mid = (begin + end) / 2
5
    merge(mergeSort(arr, begin, mid), mergeSort(arr, mid+1, end))
6
  }
7
}
8

9
def merge(arr1: Array[Int], arr2: Array[Int]): Array[Int] = {
10
  var (i, j) = (0, 0)
11
  val newArr = mutable.ArrayBuffer[Int]()
12
  while (i < arr1.length || j < arr2.length) {
13
    if (i >= arr1.length) {
14
      newArr.append(arr2(j))
15
      j +=1
16
    } else if (j >= arr2.length) {
17
      newArr.append(arr1(i))
18
      i += 1
19
    } else if (arr1(i) <= arr2(j)) {
20
      newArr.append(arr1(i))
21
      i += 1
22
    } else if (arr1(i) > arr2(j)) {
23
      newArr.append(arr2(j))
24
      j += 1
25
    }
26
  }
27
  newArr.toArray
28
}

Heap Sort

Build a max heap from the array, where each parent is greater than its children.
Move the first value of the max heap to the end, rebuild the heap from the remaining values, and repeat.

1
def heapsort(arr: Array[Int]): Unit = {
2
  // 构建大顶堆
3
  (0 to arr.length / 2).foreach(i => {
4
    adjustHeap(arr, i, arr.length)
5
  })
6

7
  // remove first
8
  (arr.length to 1 by -1).foreach(i => {
9
    swap(arr, 0, i-1)
10
    adjustHeap(arr, 0, i-1)
11
  })
12
}
13

14
def adjustHeap(arr: Array[Int], idx: Int, length: Int): Unit = {
15

16
  (0 to length / 2).foreach(i => {
17
    var maxIdx = i
18
    if (i * 2+1 < length && arr(i*2+1) > arr(i)) {
19
      maxIdx = i * 2+1
20
    }
21

22
    if (i * 2 + 2 < length && arr(i*2+2) > arr(maxIdx)) {
23
      maxIdx = i * 2 + 2
24
    }
25

26
    swap(arr, i, maxIdx)
27
  })
28
}

Counting Sort

Trade space for time: exploit a bounded set of possible values to place elements directly into their corresponding positions.

Bucket Sort

Use a partition function to distribute the dataset into buckets, then sort the data within each bucket.