Assignment 3 - Shell sort

[gmertk]

Insertion sort moves elements one place at a time. This can be slow for large arrays where you may need to move the smallest element located in the end to the beginning. Shell sort (by Donald Shell) is based on insertion sort. It swaps elements that are far apart in order to create nearly sorted subsequences. Then these nearly sorted array can be sorted efficiently by insertion sort with a fewer swaps.

git checkout assignment003 to start.

1. Read about GeneratorType, AnyGenerator, anyGenerator. Complete the given ShellSequence class to generate a Shell sequence going like ⌊n/2⌋, ⌊n/4⌋, ..., 1. The generator should return nil when the value is less than 1.
2. Write a similar class to create a gap sequence of (3 ^ k - 1) / 2) going as 1, 4, 13, 40, ... We will use the elements less than n in reversed order. For example if n is 200, the sequence should be [121, 40, 13, 4, 1].
3. Write a shell sort by using one of the generators you created above. Knuth's gap sequence is more performant than Shell's. You may want to read about the performance of other gap sequences.

Due Date: Sunday 13.12.2015

[JanBorowskiES]

I think it should be git checkout assignment003 , right?

[gmertk]

@JanBorowskiES you are totally right, I've just corrected it. Thanks!