Shell sort

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. července 2020; kontroly vyžadují 23 úprav .

Shell sort
Seřaďte podle kroků 23, 10, 4, 1.
Autor	Shell, Donald [1]
účel	Algoritmus řazení
Datová struktura	pole
nejhorší čas	O( n 2 )
Nejlepší čas	O( n log 2 n )
Průměrný čas	záleží na zvolených krocích
Náklady na paměť	O(n) celkem, O(1) navíc

Shell sort je třídicí algoritmus , který je vylepšenou verzí řazení vkládání . Myšlenkou metody Shell je porovnat prvky, které jsou nejen vedle sebe, ale také v určité vzdálenosti od sebe. Jinými slovy, jedná se o vkládání třídění s předběžnými „hrubými“ průchody. Podobné vylepšení bublinkového třídění se nazývá hřebenové třídění .

Popis

Při řazení Shell se hodnoty nejprve porovnávají a třídí mezi sebou, stojí jedna od druhé v určité vzdálenosti ( výběr hodnoty viz níže ). Poté se postup opakuje pro některé menší hodnoty a řazení Shell je dokončeno řazením prvků na (tj. obvyklé řazení vložení ). Efektivita Shell řazení je v určitých případech zajištěna tím, že prvky „rychleji“ zapadají (u jednoduchých metod třídění, např. bubble sort , každá permutace dvou prvků snižuje počet inverzí v seznamu o max. z 1 a při řazení Shell může být toto číslo více). $d$ $d$ $d$ $d=1$

Přestože je Shellsort v mnoha případech pomalejší než quicksort , má řadu výhod:

není potřeba zásobníková paměť;
žádná degradace u špatných datových sad – Quicksort se snadno degraduje na O(n²), což je horší než nejhorší zaručený čas pro Shellsort.

Historie

Shell sort byl pojmenován po svém vynálezci Donaldu Shellovi , který algoritmus publikoval v roce 1959 .

Příklad

Nechť je dán seznam a setřídí se metodou Shell a . $A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)$ $d$ $5,3,1$

První krok seřadí podseznamy složené ze všech prvků , které se liší o 5 pozic, tedy podseznamy , , , , . $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)$

Ve výsledném seznamu jsou ve druhém kroku podseznamy opět setříděny z prvků s odstupem 3 pozic.

Proces končí obvyklým způsobem vložení výsledného seznamu.

Výběr délky mezer

Průměrná doba běhu algoritmu závisí na délce intervalů - , které budou obsahovat seřazené prvky původního pole s kapacitou v každém kroku algoritmu. Existuje několik přístupů k výběru těchto hodnot: $d$ $N$

sekvence délek mezer původně používaná Shellem: v nejhorším případě bude složitost algoritmu ; $d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1$ $O(N^{2})$
Hibbardova navrhovaná sekvence: všechny hodnoty ; takový sled kroků vede k algoritmu složitosti ; $2^{i}-1\leq N,i\in \mathbb {N}$ $O(N^{{3/}})$
sekvence navržená Sedgwickem : je-li i sudé a je- li i liché. Při použití takových přírůstků je průměrná složitost algoritmu: a v nejhorším případě řádově . Při použití Sedgwickova vzorce byste se měli zastavit na hodnotě inc[s-1], pokud 3*inc[s] > size. [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/}})$
sekvence navržená Prattem: všechny hodnoty ; v tomto případě je složitost algoritmu ; $2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N}$ $O(N(logN)^{2})$
empirická sekvence Marcina Ciura (sekvence A102549 v OEIS ): ; je jedním z nejlepších pro třídění pole až do přibližně 4000 prvků. [3] ; ${\displaystyle d\in \left\{1,4,10,23,57,132,301,701,1750\right\))$
empirická posloupnost založená na Fibonacciho číslech : ; $d\in \left\{F_{n}\right\}$
všechny hodnoty $(3^{j}-1)\leq N$ , ; takový sled kroků vede k algoritmu složitosti . $j\in {\mathbb N}$ $O(N^{{3/}})$

Implementace v C++

template < typename RandomAccessIterator , typename Compare > void shell_sort ( RandomAccessIterator první , RandomAccessIterator poslední , Porovnat komp ) { pro ( auto d = ( poslední - první ) / 2 ; d != 0 ; d / = 2 ) //potřebuji smyčku pro první = a[0..d-1] for ( auto i = první + d ; i != poslední ; ++ i ) for ( auto j = i ; j - první >= d && comp ( * j , * ( j - d ) ); j -= d ) std :: swap ( * j , * ( j - d ) ); }

Implementace v C

void shell_sort ( int * pole , int velikost ) { for ( int s = velikost / 2 ; s > 0 ; s / = 2 ) { for ( int i = s ; i < velikost ; ++ i ) { for ( int j = i - s ; j >= 0 && pole [ j ] > pole [ j + s ]; j -= s ) { inttemp = pole [ j ] ; pole [ j ] = pole [ j + s ]; pole [ j + s ] = temp ; } } } }

Implementace v Javě

public class ShellSort { public static void ShellSort ( int [] pole ) { int h = 1 ; while ( h <= pole . délka / 3 ) { h = h * 3 + 1 ; } while ( h > 0 ) { for ( int vnější = h ; vnější < pole . délka ; vnější ++ ) { int tmp = pole [ vnější ] ; int vnitřní = vnější ; while ( vnitřní > h - 1 && pole [ vnitřní - h ] > tmp ) { pole [ vnitřní ] = pole [ vnitřní - h ] ; vnitřní -= h ; } pole [ vnitřní ] = tmp ; } h = ( h - 1 ) / 3 ; } } }

Implementace v Pythonu

def shell_sort ( data : seznam [ int ]) -> seznam [ int ]: poslední_index = len ( data ) krok = len ( data ) // 2 zatímco krok > 0 : pro i v rozsahu ( krok , poslední_index , 1 ): j = i delta = j - krok , zatímco delta >= 0 a data [ delta ] > data [ j ]: data [ delta ], data [ j ] = data [ j ], data [ delta ] j = delta delta = j - krok krok //= 2 návrat dat

Poznámky

↑ Shell D. L. A vysokorychlostní třídicí postup // Commun . ACM - [New York] : Association for Computing Machinery , 1959. - Sv. 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 Nejlepší přírůstky za průměrný případ Shellsortu . Získáno 15. září 2009. Archivováno z originálu 30. srpna 2011. (neurčitý)

Odkazy

D. Knut . Umění programování. Svazek 3. Třídění a vyhledávání, 2. vyd. Ch. 5.2.1. ISBN 5-8459-0082-4
Animovaná reprezentace algoritmu řazení Shell
Taneční reprezentace algoritmu řazení Shell (video)

Algoritmy řazení
Teorie	Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna	bublina Míchání Trpaslíci Rychle Hřeben Řazení sudé-liché bitový
Výběr	Výběr Pyramidový Hladký
vložky	vložky shella strom
fúze	fúze
Žádné srovnání	Počítací blok
hybridní	introsort Timsort
jiný	Topologické sítí biton
nepraktický	Bogosort Stooge řazení lívanec pomalý