compsci-notes-spring-2024/notes/fund-prog-3/some-sorts-2024-01-31.md

# Some sorts

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

## Insertion sort (for shell sort)

```py
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

```py
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

```txt
(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$

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