Some sorts

In pseudocode, but python syntax highlighting fits decently so that's what I'm using.

Insertion sort (for shell sort)

InsertionSortForShell(array, start, gap)
    for i = start + gap to len(array) - 1 # inclusive
        j = i
        while (j - gap >= start) and (array[j] < array[j - gap])
            swap(array[j], array[j - gap])
            j = j - gap

Shell sort

ShellSort(array, gapList)
    for gap in gapList
        for i = = 0 to gap - 1
            InsertionSortForShell(array, i, gap)

Hibbard

2^k - 1 where k is 1 to p where └ k^p ┐ = N

editor's (now-future me) note: idk why those weird bracket things are there lol, but they were written on the board for some reason and i just don't remember it

Pratt

For a Z-tuples for (0, 0) -> (k, k) create all the cartesian pairs

(0, 0), (0, 1), (0, 2), ..., (0, k)
(1, 0), (1, 1), (1, 2), ..., (1, k)
(2, 0), (2, 1), (2, 2), ..., (2, k)
...
(k, 0), (k, 1), (k, 2), ..., (k, k)

Naive gap values

N/2^k, k = 1 to p where N/2^p=> 1

for i, j in S
    value = 2<sup>i</sup> * 3<sup>j</sup>
    gapList.append(value)
    sort(gapList)
    gapValues[0 ... N]

1.2 KiB Raw Permalink Blame History