Shell sort
Also known as Shell's method, Shellsort, Shell sort, Shell's method
thumb|alt=The steps of Shellsort.|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1 Shellsort, also known as Shell sort or '''Shell's method''', is an in-place comparison sort. It can be understood as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neigh
Key facts
- Algorithm.class
- Sorting algorithm
- Algorithm.image
- Step-by-step visualisation of Shellsort
- Algorithm.caption
- Shellsort with gaps 23, 10, 4, 1 in action
- Algorithm.data
- Array
- Algorithm.time
- O(n2) (worst known worst case gap sequence)O(n log2n) (best known worst case gap sequence)
- Algorithm.best time
- O(n log n) (most gap sequences)O(n log2n) (best known worst-case gap sequence)
- Algorithm.average time
- depends on gap sequence
- Algorithm.space
- О(n) total, O(1) auxiliary
- Algorithm.optimal
- No
via Wikipedia infobox
Wikidata facts
- Image
- Sorting shellsort anim.gif
Sources (3)
Article · Svenska
Shell Sort är en sorteringsalgoritm som uppfanns 1959 av . Algoritmen kan ses som en förbättring av andra enklare sorteringsalgoritmer, vanligtvis Insättningssortering. Det som gör att Shell Sort är effektivare än vanlig insättningssortering är att algoritmen tillåter jämförelse mellan två element som ligger långt ifrån varandra.
Abstract from DBpedia / Wikipedia · CC BY-SA