Sorting Algorithms

Question 1

Bubble Sort

Answer 1

Intuition: “Float” entries to their correct positions one position at a time.

Pseudo:
sorted = false

while (!sorted) {
    sorted = true
    for element in list {
        if element < (or >) nextElement
            swap elements
            sorted = false
    }
}

O(n^2) running time
O(1) space (in place)

Question 2

Selection Sort

Answer 2

Intuition: At each step, find (select) the smallest (or largest) element in unsorted list and add it to the end of the unsorted list

Pseudo:
for i in 0, end {
  smallest = i
  for j in i + 1, end {
    if list[j] < list[smallest]
      smallest = j
    if smallest != i
      swap list[i] and list[smallest]
  }
}

O(n^2) running time
O(1) space (in place)

Question 3

Insertion Sort

Answer 3

Intuition: At each step place item at start of unsorted portion of array in its correct position in sorted portion of array.

Pseudo:
for i in 0, end {
  j = i + 1
  while list[j] < list[j - 1]{
    swap list[j]  and list [j - 1]
    j--
  }
}

O(n^2) running time
O(1) space (in place)

Question 4

Merge Sort

Answer 4

Intuition: Divide list into (almost) equal parts until they are trivially sorted (only one item), then merge sorted lists by adding the smallest item from the front of the two lists until a single sorted list emerges.

Pseudo:
merge-sort(arr, p, r) {
  if arr.len == 1 {
    return
  }

  q = (p + r) / 2
  merge-sort(arr, p, q)
  merge-sort(arr, q, r)
  merge(arr, p, q)
}

O(nlogn) running time
O(n) space (Need to create arrays to merge into)

Question 5

Quicksort

Answer 5

Intuition: At each step, choose arbitrary element p in list, then “partition” array such that everything left of p is < p and everything right of p is > p. Then perform the same operation on array left of p and array right of p.

Pseudo:
quicksort(arr, p, r) {
  if (p < r) {
    q = partition(arr, p, r)
    quicksort(arr, p, q - 1)
    quicksort(arr, q + 1, r)
  }
}

O(nlogn) average running time
O(logn) space (in place)

Question 6

Counting Sort

Answer 6

Intuition: Keep a tally of how many times each element occurs in a list. Then add elements back to list in order as many times as they occurred.

Pseudo:
tally = [0] * max(arr)

for num in arr {
tally[num] += 1
}

i = 0
for j in 0, tally.length {
  while tally[j] > 0 {
    arr[i] = j
    i++
    tally[j]--
  }
}

O(n + max(arr)) running time
O(max(arr)) space

Question 7

Radix Sort

Answer 7

Intuition: Sort numbers one place at a time e.g. Sort by one’s place, then sort by ten’s place, then hundred’s place and so on.

Pros:
- Non-comparative

Pseudo:
maxNum = max(arr)
place = 1

while maxNum // place > 0 {
sortNumsByPlace(arr, place)
place *= 10
}

Running time depends on sorting algorithm used
Space depends on sorting algorithm used

Question 8

Bucket Sort

Answer 8

Intuition: Group items in list into “buckets” containing list elements within a certain range. Then sort each bucket and combine the results into a list.

Pseudo:
for item in arr {
add item to appropriate bucket
}

i = 0
for bucket in buckets {
  sort bucket
  for item in bucket {
    arr[i] = item
    i++
  } 
}

O(n + k) running time (often linear)
O(n) space

Question 9

Heap Sort

Answer 9

Intuition: Add list to heap data structure (max or min), then extract items from the heap one by one.

Pseudo:
heap = new Heap(arr)
i = 0
while !heap.isEmpty {
  arr[i] = heap.pop()
  i++
}

O(nlogn) running time (nlogn time to build heap)
O(1) space (Can sort array into heap in place)

Question 10

Shell Sort

Answer 10

Intuition: Works like insertion sort but with different sized steps. Start out with a larger step size or “gap” and reduce this step size at each iteration. A gap size of one is equivalent to regular insertion sort.

Pros:
- Can be faster than insertion sort

Con:
- Unstable (Does not examine elements between gap)

Pseudo:
gap = len(arr) // 2

while gap > 0 {
compare elements within their gap size
gap //= 2
}

Between O(nlogn) and O(n^2) running time
O(1) space (in place)