Shell Sort

V tomto výučbe sa dozviete, ako funguje triedenie škrupín. Nájdete tiež pracovné príklady triedenia shell v jazykoch C, C ++, Java a Python.

Shell sort je algoritmus, ktorý najskôr triedi prvky ďaleko od seba a postupne skracuje interval medzi prvkami, ktoré sa majú triediť. Je to zovšeobecnená verzia druhu vkladania.

Pri škrupinovom triedení sú triedené prvky v konkrétnom intervale. Interval medzi prvkami sa postupne zmenšuje na základe použitej postupnosti. Výkon triedenia shellu závisí od typu sekvencie použitej pre dané vstupné pole.

Niektoré z optimálnych použitých sekvencií sú:

  • Pôvodná sekvencia spoločnosti Shell: N/2 , N/4 ,… , 1
  • Knuthove prírastky: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewickove prírastky: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibardove prírastky: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Prírastok Papernova a Staseviča: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Ako funguje triedenie škrupiny?

  1. Predpokladajme, že musíme zoradiť nasledujúce pole. Počiatočné pole
  2. V (N/2, N/4,… 1našom algoritme používame pôvodnú postupnosť škrupiny ) ako intervaly.
    V prvej slučke, ak je veľkosť poľa N = 8potom, sa prvky ležiace v intervale N/2 = 4porovnávajú a zamieňajú, ak nie sú v poriadku.
    1. 0. element sa porovnáva so 4. elementom.
    2. Ak je 0. element väčší ako 4. element, potom sa 4. element najskôr uloží do temppremennej a 0thelement (tj. Väčší element) sa uloží na 4thpozíciu a element uložený v tempsa uloží na 0thpozíciu. Usporiadanie prvkov v intervale n / 2
      Tento proces pokračuje pre všetky zostávajúce prvky. Usporiadajte všetky prvky v intervale n / 2
  3. V druhej slučke N/4 = 8/4 = 2sa berie interval a a opäť sa triedia prvky ležiace v týchto intervaloch. Usporiadajte prvky znova v intervale n / 4.
    V tomto okamihu môžete byť zmätení. Porovnajú sa všetky prvky v poli ležiace v aktuálnom intervale.
    Porovnajú sa prvky na 4. 2ndpozícii. 0thPorovnávajú sa tiež prvky na 2. a pozícii. Porovnajú sa všetky prvky v poli ležiace v aktuálnom intervale.
  4. Rovnaký proces pokračuje pre zvyšné prvky. Usporiadajte všetky prvky v intervale n / 4
  5. Nakoniec, keď je interval N/8 = 8/8 =1potom, sú zoradené prvky poľa ležiace v intervale 1. Pole je teraz úplne zoradené. Usporiadajte prvky v intervale n / 8

Algoritmus škrupinového triedenia

 shellSort (pole, veľkosť) pre interval i <- veľkosť / 2n až 1 pre každý interval „i“ v poli zoradiť všetky prvky v intervale „i“ koniec shellSort

Príklady jazyka Python, Java a C / C ++

Python Java C C ++ 
# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 
// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 
// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); )

Zložitosť

Shell sort je nestabilný algoritmus triedenia, pretože tento algoritmus neskúma prvky ležiace medzi intervalmi.

Časová zložitosť

  • Worst Case Zložitosť : menej než alebo rovné najhoršom prípade zložitosť pre plášťa triedenie je vždy menší ako alebo rovná . Podľa Poonen Vety, v najhoršom prípade zložitosť pre shell druhu je alebo alebo alebo niečo medzi tým.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Najlepšia zložitosť prípadu : O(n*log n)
    Keď je pole už zoradené, celkový počet porovnaní pre každý interval (alebo prírastok) sa rovná veľkosti poľa.
  • Priemerná zložitosť prípadu : O(n*log n)
    je to okolo .O(n1.25)

Zložitosť závisí od zvoleného intervalu. Vyššie uvedené zložitosti sa líšia pre rôzne zvolené prírastkové sekvencie. Najlepšia prírastková sekvencia nie je známa.

Zložitosť priestoru:

Komplexnosť priestoru pre triedenie škrupín je O(1).

Aplikácie Shell Sort

Shell shell sa používa, keď:

  • volanie stohu je réžia. Knižnica uClibc používa tento druh.
  • rekurzia presahuje limit. používa to kompresor bzip2.
  • Triedenie vloženia nefunguje dobre, ak sú blízke prvky ďaleko od seba. Triedenie pomocou škrupiny pomáha znižovať vzdialenosť medzi blízkymi prvkami. Bude teda potrebné vykonať menší počet výmen.

Zaujímavé články...