Skalsortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 juli 2020; kontroller kräver 23 redigeringar .

Skalsortering
Sortera med steg 23, 10, 4, 1.
Författare	Shell, Donald [1]
ändamål	Sorteringsalgoritm
Datastruktur	array
värsta tiden	O( n 2 )
Lämpligast tid	O( n log 2 n )
Snittid	beror på de valda stegen
Minneskostnad	O(n) totalt, O(1) extra

Skalsortering är en sorteringsalgoritm som är en förbättrad version av infogningssortering . Tanken med Shell-metoden är att jämföra element som inte bara ligger bredvid varandra, utan också på ett visst avstånd från varandra. Detta är med andra ord insättningssortering med preliminära "grova" pass. En liknande förbättring av bubbelsortering kallas kamsortering .

Beskrivning

Vid sortering av Shell jämförs och sorteras värden först sinsemellan, stående från varandra på ett visst avstånd ( se nedan för val av värde ). Därefter upprepas proceduren för några mindre värden på , och Shell-sorteringen slutförs genom att beställa elementen på (det vill säga den vanliga insättningssorteringen ). Effektiviteten av Shell-sorteringen säkerställs i vissa fall av det faktum att elementen "snabbare" faller på plats (i enkla sorteringsmetoder, till exempel bubbelsortering , reducerar varje permutation av två element antalet inversioner i listan med ett maximum av 1, och med Shell-sort kan detta antal vara fler ). $d$ $d$ $d$ $d=1$

Även om Shellsort i många fall är långsammare än quicksort , har det ett antal fördelar:

inget behov av stackminne;
ingen försämring på dåliga datauppsättningar - Quicksort försämras lätt till O(n²), vilket är sämre än den sämsta garanterade tiden för Shellsort.

Historik

Shell sorten fick sitt namn efter sin uppfinnare, Donald Shell , som publicerade algoritmen 1959 .

Exempel

Låt en lista ges och den sorteras efter Shell-metoden, och . $A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)$ $d$ $5,3,1$

Det första steget sorterar underlistor som består av alla element som skiljer sig åt med 5 positioner, det vill säga underlistor , , , , . $A$ $A$ $A_{{5,1}}=(32,66,40)$ $A_{{5,2}}=(95,35,43)$ $A_{{5,3}}=(16,19,93)$ $A_{{5,4}}=(82,75,68)$ $A_{{5,5}}=(24,54)$

I den resulterande listan, i det andra steget, sorteras sublistor igen från element åtskilda med 3 positioner.

Processen avslutas med den vanliga infogningen av den resulterande listan.

Välja längden på luckor

Den genomsnittliga körtiden för algoritmen beror på längden på intervallen - , som kommer att innehålla de sorterade elementen i den ursprungliga arrayen med en kapacitet vid varje steg i algoritmen. Det finns flera sätt att välja dessa värden: $d$ $N$

sekvensen av gaplängder som ursprungligen användes av Shell: i värsta fall kommer komplexiteten hos algoritmen att vara ; $d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1$ $O(N^{2})$
Hibbards föreslagna sekvens: alla värden ; en sådan sekvens av steg leder till en komplexitetsalgoritm ; $2^{i}-1\leq N,i\in \mathbb {N}$ $O(N^{{3/2}})$
sekvens föreslagen av Sedgwick : om i är jämnt och om i är udda. När du använder sådana inkrement är den genomsnittliga komplexiteten för algoritmen: , och i värsta fall av storleksordningen . När du använder Sedgwick-formeln bör du stanna vid värdet inc[s-1] om 3*inc[s] > storlek. [2] ; $d_{i}=9\cdot 2^{i}-9\cdot 2^{i/2}+1$ $d_{i}=8\cdot 2^{i}-6\cdot 2^{(i+1)/2}+1$ $O(n^{{7/6}})$ $O(n^{{4/3}})$
sekvens föreslagen av Pratt: alla värden ; i detta fall är algoritmens komplexitet ; $2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N}$ $O(N(logN)^{2})$
empirisk sekvens av Marcin Ciur (sekvens A102549 i OEIS ): ; är en av de bästa för att sortera en array upp till cirka 4000 element. [3] ; ${\displaystyle d\in \left\{1,4,10,23,57,132,301,701,1750\right\))$
empirisk sekvens baserad på Fibonacci-tal : ; $d\in \left\{F_{n}\right\}$
alla värden $(3^{j}-1)\leq N$ , ; en sådan sekvens av steg leder till en komplexitetsalgoritm . $j\in {\mathbb N}$ $O(N^{{3/2}})$

Implementering i C++

mall < typnamn RandomAccessIterator , typnamn Jämför > void shell_sort ( RandomAccessIterator först , RandomAccessIterator sist , Jämför jämför ) { för ( auto d = ( sista - första ) / 2 ; d != 0 ; d /= 2 ) //behöver en slinga för första = a[0..d-1] för ( auto i = första + d ; i != sist ; ++ i ) för ( auto j = i ; j - första >= d && komp ( * j , * ( j - d ) ); j - = d ) std :: swap ( * j , * ( j - d ) ); }

Implementering i C

void shell_sort ( int * array , int size ) { for ( int s = storlek / 2 ; s > 0 ; s /= 2 ) { for ( int i = s ; i < storlek ; ++ i ) { för ( int j = i - s ; j >= 0 && array [ j ] > array [ j + s ]; j -= s ) { intemp = array [ j ] ; array [ j ] = array [ j + s ]; array [ j + s ] = temp ; } } } }

Implementering i Java

public class ShellSort { public static void shellSort ( int [ ] array ) { int h = 1 ; while ( h <= matris . längd / 3 ) { h = h * 3 + 1 ; } while ( h > 0 ) { for ( int yttre = h ; yttre < array . längd ; yttre ++ ) { int tmp = array [ outer ] ; int inre = yttre ; while ( inre > h - 1 && array [ inner - h ] > tmp ) { array [ inre ] = array [ inner - h ] ; inre -= h ; } array [ inre ] = tmp ; } h = ( h - 1 ) / 3 ; } } }

Implementering i Python

def shell_sort ( data : list [ int ]) -> list [ int ]: last_index = len ( data ) steg = len ( data ) // 2 medan steg > 0 : för i inom intervallet ( step , last_index , 1 ): j = i delta = j - steg medan delta >= 0 och data [ delta ] > data [ j ]: data [ delta ], data [ j ] = data [ j ], data [ delta ] j = delta delta = j - steg steg //= 2 returnera data

Anteckningar

↑ Shell D. L. A high-speed sorting procedure // Commun . ACM - [New York] : Association for Computing Machinery , 1959. - Vol. 2, Iss. 7. - S. 30-32. — ISSN 0001-0782 ; 1557-7317 - doi:10.1145/368370.368387
↑ J. Incerpi, R. Sedgewick , "Improved Upper Bounds for Shellsort", J. Computer and System Sciences 31, 2, 1985.
↑ Marcin Ciura Bästa ökningar för det genomsnittliga fallet för Shellsort . Hämtad 15 september 2009. Arkiverad från originalet 30 augusti 2011. (obestämd)

Länkar

D. Knut . Konsten att programmera. Volym 3. Sortering och sökning, 2:a uppl. Ch. 5.2.1. ISBN 5-8459-0082-4
Animerad representation av Shell-sorteringsalgoritmen
Dansrepresentation av skalsorteringsalgoritmen (video)

Sorteringsalgoritmer
Teori	Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta	bubbla Omrörning Dvärgar Snabb Hårkam Sortering jämnt-udda Bitvis
Val	Val Pyramidformad Slät
Insatser	Insatser shella träd
fusion	fusion
Inga jämförelser	Räkning blockera
hybrid	introsort Timsort
Övrig	Topologiska nätverk biton
opraktisk	Bogosort Stooge sort pannkaka långsam