Sorting

Question 1

Describe how insertion sort works

Answer 1

start off from the left
sort ONE element first, then sort TWO elements
we'll have a SORTED list on the left
Adv:
- less swaps
- works well on mostly sorted lists

Question 2

Describe how selection sort works

Answer 2

Choose the largest number and swap it with the last element
Repeat for next largest number and the unsorted subset
Adv:
- less comparisons

Question 3

Describe how bubble sort works

Answer 3

start from left
swap element if the element is larger than the adjacent right element
repeat until (no swaps in one traversal) or until the end

Question 4

Describe how shell sort works

Answer 4

a.k.a diminishing increment sort
c.f insertion sort, except insertion sort for larger increments
Divide list into smaller sub-lists by choosing every nth element
sort smaller lists using insertion sort
Decrease the increment
worst case ==> O(n^2)

Question 5

Describe how merge sort works

Answer 5

Split list into two, repeatedly
Merge and sort the small lists together
O(n log n)

Question 6

Describe how quick sort works

Answer 6

Choose a pivot point
Sort elements (smaller values to pivot to the left, larger values to pivot to the right)

Question 7

Describe how Timsort works

Answer 7

Hybrid sort
Finds runs of sorted elements using insertion sort
Merges them together using merge sort