Shell fajta

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. július 9-én felülvizsgált verziótól ; az ellenőrzések 23 szerkesztést igényelnek .

Shell fajta
Rendezés a 23., 10., 4., 1. lépésekkel.
Szerző	Shell, Donald [1]
célja	Rendezési algoritmus
Adatstruktúra	sor
legrosszabb idő	O( n 2 )
Legjobb idő	O( n log 2 n )
Átlagos idő	a választott lépésektől függ
A memória költsége	O(n) összesen, O(1) extra

A Shell - rendezés egy rendezési algoritmus , amely a beillesztési rendezés továbbfejlesztett változata . A Shell módszer lényege, hogy olyan elemeket hasonlítson össze, amelyek nemcsak egymás mellett, hanem egymástól bizonyos távolságra is vannak. Más szóval, ez egy beszúrásos rendezés előzetes „durva” áthaladással. A buborékos rendezéshez hasonló fejlesztést fésűs rendezésnek nevezünk .

Leírás

A Shell rendezése során az értékeket először összehasonlítják és rendezik egymás között, egymástól bizonyos távolságra ( az érték kiválasztásához lásd alább ). Ezt követően az eljárás megismétlődik néhány kisebb értéknél , és a Shell rendezés az elemek sorrendjével fejeződik be (vagyis a szokásos beszúrási rendezés ). A Shell rendezés hatékonyságát bizonyos esetekben az biztosítja, hogy az elemek „gyorsabban” kerülnek a helyükre (egyszerű rendezési módszereknél, például buborékos rendezésnél két elem minden permutációja maximummal csökkenti az inverziók számát a listában 1-ből, és a Shell rendezésével ez a szám több is lehet). $d$ $d$ $d$ $d=1$

Bár a Shellsort sok esetben lassabb, mint a gyorsrendezés, számos előnnyel rendelkezik:

nincs szükség verem memóriára;
nem romlik a rossz adatkészletek – A Quicksort könnyen lebomlik O(n²-re), ami rosszabb, mint a Shellsort garantált legrosszabb ideje.

Történelem

A Shell sort feltalálójáról, Donald Shellről nevezték el , aki 1959 -ben publikálta az algoritmust .

Példa

Adjunk meg egy listát, amelyet Shell metódussal rendezünk, és . $A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)$ $d$ $5,3,1$

Az első lépés az összes olyan elemből álló allistákat rendezi , amelyek 5 pozícióban különböznek egymástól, azaz allistákat , , , , . $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)$

Az eredményül kapott listában a második lépésben az allistákat ismét a 3 pozícióval elhelyezett elemekből rendezzük.

A folyamat a kapott lista szokásos beszúrási módjával zárul.

A hézagok hosszának kiválasztása

Az algoritmus átlagos futási ideje függ az intervallumok hosszától - , amelyek az eredeti tömb rendezett elemeit tartalmazzák majd kapacitással az algoritmus minden lépésében. Számos megközelítés létezik ezen értékek kiválasztására: $d$ $N$

a Shell által eredetileg használt hézaghossz-sorozat: a legrosszabb esetben az algoritmus bonyolultsága ; $d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1$ $O(N^{2})$
Hibbard által javasolt sorrend: minden érték ; a lépések ilyen sorozata egy bonyolultságú algoritmushoz vezet ; $2^{i}-1\leq N,i\in \mathbb {N}$ $O(N^{{3/2}})$
Sedgwick által javasolt sorozat : ha i páros és ha i páratlan. Ilyen növekmények használatakor az algoritmus átlagos bonyolultsága: , és a legrosszabb esetben a sorrend . A Sedgwick-képlet használatakor meg kell állnia az inc[s-1] értéknél, ha 3*inc[s] > méret. [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}})$
Pratt által javasolt sorrend: minden érték ; ebben az esetben az algoritmus összetettsége ; $2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N}$ $O(N(logN)^{2})$
Marcin Ciur empirikus szekvenciája ( A102549 szekvencia az OEIS -ben ): ; az egyik legjobb egy körülbelül 4000 elemből álló tömb rendezéséhez. [3] ; ${\displaystyle d\in \left\{1,4,10,23,57,132,301,701,1750\jobbra\))$
empirikus sorozat Fibonacci-számok alapján : ; $d\in \left\{F_{n}\right\}$
minden értéket $(3^{j}-1)\leq N$ , ; egy ilyen lépéssorozat egy bonyolultságú algoritmushoz vezet . $j\in {\mathbb N}$ $O(N^{{3/2}})$

Megvalósítás C++ nyelven

sablon < típusnév RandomAccessIterator , típusnév Összehasonlítás > void shell_sort ( RandomAccessIterator először , RandomAccessIterator utolsó , Compare comp ) { for ( auto d = ( utolsó - első ) / 2 ; d ! = 0 ; d / = 2 ) //kell egy ciklus az első = a[0..d-1] for ( auto i = első + d ; i != utolsó ; ++ i ) for ( auto j = i ; j - első > = d && comp ( * j , * ( j - d ) ); j - = d ) std :: csere ( * j , * ( j - d ) ); }

Megvalósítás C-ben

void shell_sort ( int * tömb , int méret ) { for ( int s = méret / 2 ; s > 0 ; s / = 2 ) { for ( int i = s ; i < méret ; ++ i ) { for ( int j = i - s ; j >= 0 && array [ j ] > array [ j + s ]; j -= s ) { inttemp = tömb [ j ] ; tömb [ j ] = tömb [ j + s ]; tömb [ j + s ] = hőmérséklet ; } } } }

Implementáció Java nyelven

public class ShellSort { public static void shellSort ( int [] array ) { int h = 1 ; while ( h <= tömb . hossza / 3 ) { h = h * 3 + 1 ; } while ( h > 0 ) { for ( int külső = h ; külső < tömb . hossza ; külső ++ ) { int tmp = tömb [ külső ] ; int belső = külső ; while ( inner > h - 1 && array [ inner - h ] > tmp ) { array [ inner ] = array [ inner - h ] ; belső -= h ; } tömb [ belső ] = tmp ; } h = ( h - 1 ) / 3 ; } } }

Megvalósítás Pythonban

def shell_sort ( data : list [ int ]) -> list [ int ]: last_index = len ( data ) step = len ( data ) // 2 while step > 0 : for i in range ( step , last_index , 1 ): j = i delta = j - lépés , míg delta >= 0 és adat [ delta ] > adat [ j ]: adat [ delta ], adat [ j ] = adat [ j ], adat [ delta ] j = delta delta = j - lépés lépés //= 2 visszaadja az adatokat

Jegyzetek

↑ Shell D. L. A nagy sebességű válogatási eljárás // Commun . ACM - [New York] : Association for Computing Machinery , 1959. - Vol. 2, Iss. 7. - P. 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 a Shellsort átlagos esetének legjobb növekményei . Letöltve: 2009. szeptember 15. Az eredetiből archiválva : 2011. augusztus 30.. (határozatlan)

Linkek

D. Knut . A programozás művészete. 3. kötet. Rendezés és keresés, 2. kiadás. Ch. 5.2.1. ISBN 5-8459-0082-4
A Shell rendezési algoritmus animált ábrázolása
A Shell rendezési algoritmus táncos ábrázolása (videó)

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú