Sortowanie Shella
Also known as Shell sort, Shell's method, Shellsort, Shell sort, Shell's method
algorytm sortowania
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 · Polski
Sortowanie Shella (ang. Shellsort) – jeden z algorytmów sortowania działających w miejscu i korzystających z porównań elementów. Można go traktować jako uogólnienie sortowania przez wstawianie lub sortowania bąbelkowego, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Na początku sortuje on elementy tablicy położone daleko od siebie, a następnie stopniowo zmniejsza odstępy między sortowanymi elementami. Dzięki temu może je przenieść w docelowe położenie szybciej niż zwykłe sortowanie przez wstawianie. Pierwszą wersję tego algorytmu, której zawdzięcza on swoją nazwę, opublikował w 1959 roku Donald Shell. Złożoność czasowa sortowania Shella w dużej mierze zależy od użytego w nim ciągu odstępów. Wyznaczenie jej dla wielu stosowanych w praktyce wariantów tego algorytmu pozostaje problemem otwartym.
Abstract from DBpedia / Wikipedia · CC BY-SA