tag

#gap-sequence

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Shell Sort with Shell Gaps

Shell Sort with Shell Gaps Shell sort with Shell gaps uses the original gap sequence proposed for Shell sort. The sequence starts with roughly half the array length and repeatedly halves the gap until it reaches 1. This version is simple and easy to implement, but its worst-case behavior remains quadratic. Problem Given a sequence $A$ of length $n$, reorder it such that $$ A[0] \le A[1] \le \cdots \le...
algorithms sorting shell-sort gap-sequence
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Shell Sort with Hibbard Gaps

Shell Sort with Hibbard Gaps Shell sort with Hibbard gaps replaces the simple halving sequence with a more structured progression: $$ g_k = 2^k - 1 $$ This sequence produces gaps such as: $$ 1, 3, 7, 15, 31, \dots $$ In practice, you use the largest value less than $n$, then proceed in decreasing order down to 1. This improves performance over the basic Shell gap sequence by reducing...
algorithms sorting shell-sort gap-sequence
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Shell Sort with Sedgewick Gaps

Shell Sort with Sedgewick Gaps Shell sort with Sedgewick gaps uses a carefully designed sequence that improves both theoretical and practical performance over earlier sequences such as Shell and Hibbard. Two common Sedgewick sequences are used in practice. A widely cited version is: $$ g_k = \begin{cases} 9 \cdot 2^k - 9 \cdot 2^{k/2} + 1 & \text{if } k \text{ even} 8 \cdot 2^k - 6 \cdot 2^{(k+1)/2} +...
algorithms sorting shell-sort gap-sequence