Sorting Algorithms Flashcards Preview

Algorithms > Sorting Algorithms > Flashcards

Flashcards in Sorting Algorithms Deck (10)
Loading flashcards...
1
Q

Bubble Sort

A

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)

2
Q

Selection Sort

A

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)

3
Q

Insertion Sort

A

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)

4
Q

Merge Sort

A

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)

5
Q

Quicksort

A

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)

6
Q

Counting Sort

A

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

7
Q

Radix Sort

A

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

8
Q

Bucket Sort

A

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

9
Q

Heap Sort

A

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)

10
Q

Shell Sort

A

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)