Skal sortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. juli 2020; checks kræver 23 redigeringer .

Skal sortering
Sorter med trin 23, 10, 4, 1.
Forfatter	Shell, Anders [1]
formål	Sorteringsalgoritme
Datastruktur	array
værste tid	O( n 2 )
Bedste tid	O( n log 2 n )
Gennemsnitlig tid	afhænger af de valgte trin
Hukommelsesomkostninger	O(n) i alt, O(1) ekstra

Shell sortering er en sorteringsalgoritme , der er en forbedret version af indsættelsessortering . Ideen med Shell-metoden er at sammenligne elementer, der ikke kun er ved siden af hinanden, men også i en vis afstand fra hinanden. Dette er med andre ord indsættelsessortering med foreløbige "grove" gennemløb. En lignende forbedring til boblesortering kaldes kamsortering .

Beskrivelse

Ved sortering af Shell bliver værdierne først sammenlignet og sorteret indbyrdes, idet de står fra hinanden i en vis afstand ( se nedenfor for valg af værdi ). Derefter gentages proceduren for nogle mindre værdier på , og Shell-sorteringen afsluttes ved at bestille elementerne på (det vil sige den sædvanlige indsættelsessort ). Effektiviteten af Shell-sortering i visse tilfælde sikres ved, at elementerne "hurtigere" falder på plads (i simple sorteringsmetoder, for eksempel boblesortering , reducerer hver permutation af to elementer antallet af inversioner i listen med et maksimum af 1, og med Shell-sortering kan dette tal være mere ). $d$ $d$ $d$ $d=1$

Selvom Shellsort i mange tilfælde er langsommere end quicksort , har det en række fordele:

intet behov for stakhukommelse;
ingen nedbrydning på dårlige datasæt - Quicksort nedbrydes nemt til O(n²), hvilket er værre end den værste garanterede tid for Shellsort.

Historie

Shell sort blev opkaldt efter dens opfinder, Donald Shell , som offentliggjorde algoritmen i 1959 .

Eksempel

Lad en liste blive givet, og den er sorteret efter Shell-metoden, og . $A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)$ $d$ $5,3,1$

Det første trin sorterer underlister sammensat af alle elementer , der adskiller sig med 5 positioner, det vil sige underlister , , , , . $EN$ $EN$ $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 resulterende liste, i det andet trin, sorteres underlister igen fra elementer fordelt på 3 positioner.

Processen slutter med den sædvanlige indsættelsessortering af den resulterende liste.

Valg af længde på mellemrum

Den gennemsnitlige køretid for algoritmen afhænger af længden af intervallerne - , som vil indeholde de sorterede elementer i det originale array med en kapacitet på hvert trin i algoritmen. Der er flere tilgange til at vælge disse værdier: $d$ $N$

rækkefølgen af mellemrumslængder oprindeligt brugt af Shell: i værste fald vil kompleksiteten af algoritmen være ; $d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1$ $O(N^{2})$
Hibbards foreslåede sekvens: alle værdier ; en sådan sekvens af trin fører til en kompleksitetsalgoritme ; $2^{i}-1\leq N,i\in \mathbb {N}$ $O(N^{{3/2}})$
sekvens foreslået af Sedgwick : hvis i er lige og hvis i er ulige. Når du bruger sådanne trin, er den gennemsnitlige kompleksitet af algoritmen: , og i værste tilfælde af størrelsesordenen . Når du bruger Sedgwick-formlen, bør du stoppe ved værdien inc[s-1], hvis 3*inc[s] > størrelse. [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 foreslået af Pratt: alle værdier ; i dette tilfælde er kompleksiteten af algoritmen ; $2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N}$ $O(N(logN)^{2})$
empirisk sekvens af Marcin Ciur (sekvens A102549 i OEIS ): ; er en af de bedste til at sortere et array op til ca. 4000 elementer. [3] ; ${\displaystyle d\in \left\{1,4,10,23,57,132,301,701,1750\right\))$
empirisk sekvens baseret på Fibonacci-tal : ; $d\in \left\{F_{n}\right\}$
alle værdier $(3^{j}-1)\leq N$ dage ,; en sådan sekvens af trin fører til en kompleksitetsalgoritme . $j\in {\mathbb N}$ $O(N^{{3/2}})$

Implementering i C++

skabelon < typenavn RandomAccessIterator , typenavn Sammenlign > void shell_sort ( RandomAccessIterator først , RandomAccessIterator sidst , Sammenlign comp ) { for ( auto d = ( sidste - først ) / 2 ; d != 0 ; d /= 2 ) //brug for en løkke for først = a[0..d-1] for ( auto i = første + d ; i != sidste ; ++ i ) for ( auto j = i ; j - først >= d && comp ( * j , * ( j - d ) ); j - = d ) std :: swap ( * j , * ( j - d ) ); }

Implementering i C

void shell_sort ( int * matrix , int size ) { for ( int s = størrelse / 2 ; s > 0 ; s /= 2 ) { for ( int i = s ; i < størrelse ; ++ i ) { for ( int j = i - s ; j >= 0 && array [ j ] > array [ j + s ]; j -= s ) { intemp = matrix [ 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 <= matrix . længde / 3 ) { h = h * 3 + 1 ; } while ( h > 0 ) { for ( int ydre = h ; ydre < array . længde ; ydre ++ ) { int tmp = array [ ydre ] ; int indre = ydre ; while ( indre > h - 1 && matrix [ indre - h ] > tmp ) { matrix [ indre ] = matrix [ indre - h ] ; indre -= h ; } array [ indre ] = tmp ; } h = ( h - 1 ) / 3 ; } } }

Implementering i Python

def shell_sort ( data : liste [ int ]) -> liste [ int ]: sidste_indeks = len ( data ) step = len ( data ) // 2 mens trin > 0 : for i i rækkevidde ( trin , sidste_indeks , 1 ): j = i delta = j - step mens delta >= 0 og data [ delta ] > data [ j ]: data [ delta ], data [ j ] = data [ j ], data [ delta ] j = delta delta = j - step trin //= 2 returner data

Noter

↑ Shell D. L. En højhastighedssorteringsprocedure // 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 bedste stigninger for det gennemsnitlige tilfælde af Shellsort . Hentet 15. september 2009. Arkiveret fra originalen 30. august 2011. (ubestemt)

Links

D. Knut . Kunsten at programmere. Bind 3. Sortering og søgning, 2. udg. Ch. 5.2.1. ISBN 5-8459-0082-4
Animeret repræsentation af Shell-sorteringsalgoritmen
Danserepræsentation af Shell-sorteringsalgoritmen (video)

Sorteringsalgoritmer
Teori	Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling	boble Omrøring Dværge Hurtig Kam Sortering lige-ulige Bitvis
Valg	Valg Pyramideformet Glat
indsætter	indsætter shella træ
fusion	fusion
Ingen sammenligninger	Tæller blok
hybrid	introsort Timsort
Andet	Topologisk netværk biton
upraktisk	Bogosort Stooge sort pandekage langsom