Shell Sort and Quick Sort

Question 1

Define

Shellsort

Answer 1

Based on insertion sort.
1. Insertion sort widely spaced items.
2. Insertion sort less widely spaced items, and so on
For example, do a sort on items four spaces apart, then 1 space apart.
O(N (logN)^2).

Question 2

Define

Interval/gap sequence

Answer 2

The sequence of numbers used to generte the intervals between the numbers sorted in shellsort. Popular method is Knuth’s interval sequence, h = 3 x h +1. Important that these numbers are relatively prime, more likely to intermingle items sorted on previous pass

Question 3

Define

Quicksort

Answer 3

Most popular, O(NlogN).
Partitions an array into two subarrays then calls itself recursively to quick sort