Sortare Shell

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 iulie 2020; verificările necesită 23 de modificări .

Sortare Shell
Sortați cu pașii 23, 10, 4, 1.
Autor	Shell, Donald [1]
scop	Algoritm de sortare
Structură de date	matrice
cel mai rău moment	O( n 2 )
Cel mai bun timp	O( n log 2 n )
Timp mediu	depinde de etapele alese
Costul memoriei	O(n) total, O(1) în plus

Shell sort este un algoritm de sortare care este o versiune îmbunătățită a sortării prin inserție . Ideea metodei Shell este de a compara elemente care nu sunt doar unul lângă celălalt, ci și la o anumită distanță unul de celălalt. Cu alte cuvinte, aceasta este sortarea prin inserție cu treceri preliminare „aspre”. O îmbunătățire similară cu sortarea cu bule se numește sortare pieptene .

Descriere

Când sortați Shell, valorile sunt mai întâi comparate și sortate între ele, stând una de cealaltă la o anumită distanță ( vezi mai jos pentru alegerea unei valori ). După aceea, procedura se repetă pentru unele valori mai mici ale , iar sortarea Shell este finalizată prin ordonarea elementelor la (adică sortarea obișnuită de inserare ). Eficiența sortării Shell în anumite cazuri este asigurată de faptul că elementele se încadrează „mai rapid” (în metodele simple de sortare, de exemplu, sortarea cu bule , fiecare permutare a două elemente reduce numărul de inversiuni din listă cu maximum). de 1, iar cu sortarea Shell acest număr poate fi mai mare). $d$ $d$ $d$ $d=1$

Deși Shellsort este mai lent decât quicksort în multe cazuri , are o serie de avantaje:

nu este nevoie de memorie stivă;
nicio degradare pe seturile de date proaste - Quicksort se degradează cu ușurință la O(n²), ceea ce este mai rău decât cel mai prost timp garantat pentru Shellsort.

Istorie

Shell sort a fost numit după inventatorul său, Donald Shell , care a publicat algoritmul în 1959 .

Exemplu

Să fie dată o listă și sortată după metoda Shell și . $A=(32,95,16,82,24,66,35,19,75,54,40,43,93,68)$ $d$ $5,3,1$

Primul pas sortează sublistele compuse din toate elementele care diferă prin 5 poziții, adică subliste , , , , . $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)$

În lista rezultată, la al doilea pas, sublistele sunt din nou sortate din elemente distanțate cu 3 poziții.

Procesul se încheie cu tipul obișnuit de inserare a listei rezultate.

Alegerea lungimii golurilor

Timpul mediu de rulare al algoritmului depinde de lungimea intervalelor - , care va conține elementele sortate ale matricei originale cu o capacitate la fiecare pas al algoritmului. Există mai multe abordări pentru alegerea acestor valori: $d$ $N$

secvența lungimii gap-ului utilizată inițial de Shell: în cel mai rău caz, complexitatea algoritmului va fi ; $d_{1}=N/2,d_{i}=d_{i-1}/2,d_{k}=1$ $O(N^{2})$
Secvența propusă de Hibbard: toate valorile ; o astfel de secvență de pași duce la un algoritm de complexitate ; $2^{i}-1\leq N,i\in \mathbb {N}$ $O(N^{{3/2}})$
secvența propusă de Sedgwick : dacă i este par și dacă i este impar. Când se utilizează astfel de incremente, complexitatea medie a algoritmului este: , iar în cel mai rău caz de ordinul . Când utilizați formula Sedgwick, ar trebui să vă opriți la valoarea inc[s-1] dacă 3*inc[s] > dimensiune. [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}})$
secvența propusă de Pratt: toate valorile ; în acest caz, complexitatea algoritmului este ; $2^{i}\cdot 3^{j}\leq N/2,i,j\in \mathbb {N}$ $O(N(logN)^{2})$
secvența empirică a lui Marcin Ciur (secvența A102549 în OEIS ): ; este unul dintre cele mai bune pentru sortarea unui tablou de până la aproximativ 4000 de elemente. [3] ; $d\in \left\{1,4,10,23,57,132,301,701,1750\right\)$
succesiune empirică bazată pe numerele Fibonacci : ; $d\in \left\{F_{n}\right\}$
toate valorile $(3^{j}-1)\leq N$ , ; o astfel de succesiune de pași duce la un algoritm de complexitate . $j\in {\mathbb N}$ $O(N^{{3/2}})$

Implementare în C++

template < typename RandomAccessIterator , typename Compare > void shell_sort ( RandomAccessIterator primul , RandomAccessIterator ultimul , Compare comp ) { pentru ( auto d = ( ultimul - primul ) / 2 ; d != 0 ; d /= 2 ) //am nevoie de o buclă pentru primul = a[0..d-1] pentru ( auto i = primul + d ; i != ultimul ; ++ i ) pentru ( auto j = i ; j - primul >= d && comp ( * j , * ( j - d ) ); j -= d ) std :: swap ( * j , * ( j - d ) ); }

Implementare în C

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

Implementare în Java

public class ShellSort { public static void shellSort ( int [] matrice ) { int h = 1 ; în timp ce ( h <= matrice . lungime / 3 ) { h = h * 3 + 1 ; } while ( h > 0 ) { for ( int exterior = h ; exterior < matrice . lungime ; exterior ++ ) { int tmp = matrice [ exterior ] ; int interior = exterior ; while ( inner > h - 1 && array [ inner - h ] > tmp ) { array [ inner ] = matrice [ inner - h ] ; interior -= h ; } matrice [ interior ] = tmp ; } h = ( h - 1 ) / 3 ; } } }

Implementare în Python

def shell_sort ( data : list [ int ]) -> list [ int ]: last_index = len ( date ) step = len ( data ) // 2 while step > 0 : for i in range ( step , last_index , 1 ): j = i delta = j - pas în timp ce delta >= 0 și date [ delta ] > date [ j ]: date [ delta ], data [ j ] = date [ j ], date [ delta ] j = delta delta = j - pas pas //= 2 returnează date

Note

↑ Shell D. L. O procedură de sortare de mare viteză // 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 Cele mai bune creșteri pentru cazul mediu Shellsort . Consultat la 15 septembrie 2009. Arhivat din original la 30 august 2011. (nedefinit)

Link -uri

D. Knut . Arta de a programa. Volumul 3. Sortare și căutare, ed. a II-a. Ch. 5.2.1. ISBN 5-8459-0082-4
Reprezentare animată a algoritmului de sortare Shell
Reprezentarea dansului a algoritmului de sortare Shell (video)

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet