File ShellSort.h

↰ Parent directory (ADS/sort)

Shell Sort (section 15.1), a local search that lowers the number of inversions: an insertion sort of the items h apart, for decreasing gaps h down to 1, so that the far items move first and the last pass, the insertion sort, finds the vector almost sorted.

Definition (ADS/sort/ShellSort.h)

Detailed Description

In place, iterative, not stable; its time depends on the gaps:

  • knuthGaps(), the h = ( 3^i - 1 ) / 2 = 1 , 4 , 13 , 40 , 121 , … of the book, :math:` O( n^{1.5} ) ` in the worst case;

  • shellGaps(), the n / 2 , n / 4 , … , 1 of Shell, :math:` Theta( n^2 ) ` in the worst case;

  • hibbardGaps(), the :math:` 2^k - 1 ` = 1 , 3 , 7 , 15 , … of Hibbard, which unlike those of Shell are coprime, :math:` O( n^{1.5} ) ` in the worst case;

  • prattGaps(), all the 3^i 2^j up to n, :math:` O( n log^2 n ) ` in the worst case;

  • ciuraGaps(), 1 , 4 , 10 , 23 , 57 , 132 , 301 , 701 and then :math:` times 2.25 `, found by experiment and among the fastest in practice.

The contracts [see File Contract.h]: the four generators give gaps that start from 1 and increase; shellSort() needs positive increasing gaps, and the vector ends with the same items, sorted when the first gap is 1 (with a single gap h it is only h-sorted, as in Figura 15.4), an audit. The functions are defined in ShellSort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 15.1, https://algoritmicamente.it/materiali/libro/capitoli/cap15.pdf

    1. Shell, A high-speed sorting procedure, Communications of the ACM 2(7), 30-32, 1959, doi:10.1145/368370.368387

    1. Hibbard, An empirical study of minimal storage sorting, Communications of the ACM 6(5), 206-213, 1963, doi:10.1145/366552.366557

    1. Pratt, Shellsort and sorting networks, PhD thesis, Stanford University, 1971

  1. Ciura, Best increments for the average case of Shellsort, FCT 2001, LNCS 2138, 106-117, doi:10.1007/3-540-44669-9_12

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions