Shell Sort

Ebben az oktatóanyagban megtudhatja, hogyan működik a shell rendezés. Ezenkívül találhat működő példákat a shell rendezésre C, C ++, Java és Python.

A héjfajta rendezés olyan algoritmus, amely először egymástól távolabb rendezi az elemeket, és egymás után csökkenti a rendezendő elemek közötti intervallumot. Ez egy általánosított változata a beszúrási rendezésnek.

A héjfajta rendezésében a meghatározott időközönként található elemek rendezve vannak. Az elemek közötti intervallum az alkalmazott sorrend alapján fokozatosan csökken. A héjfajta teljesítménye az adott bemeneti tömbhöz használt szekvencia típusától függ.

Néhány alkalmazott optimális szekvencia:

  • A Shell eredeti sorrendje: N/2 , N/4 ,… , 1
  • Knuth növekményei: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewick növekményei: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbard növekményei: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernov és Stasevich növekmény: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Hogyan működik a Shell Sort?

  1. Tegyük fel, hogy a következő tömböt kell rendezni. Kezdeti tömb
  2. (N/2, N/4,… 1Algoritmusunkban intervallumként használjuk a shell eredeti szekvenciáját ).
    Az első ciklusban, ha a tömb mérete N = 8ekkor, az intervallumban fekvő elemeket N/2 = 4összehasonlítjuk és felcseréljük, ha nincsenek rendben.
    1. A 0. elemet összehasonlítjuk a 4. elemmel.
    2. Ha a 0. elem nagyobb, mint a 4., akkor a 4. elemet először tempváltozóban tároljuk, és az 0thelemet (azaz nagyobb elemet) a 4thpozícióban tároljuk, és a tárolt elemet tempabban a 0thhelyzetben tároljuk . Az elemek átrendezése n / 2 időközönként
      Ez a folyamat az összes többi elemre vonatkozik. Rendezze át az összes elemet n / 2 intervallumban
  3. A második ciklusban egy intervallumot N/4 = 8/4 = 2veszünk fel, és ismét az ezen intervallumokban fekvő elemeket rendezzük. Átrendezze az elemeket n / 4 intervallumban
    . Ezen a ponton összezavarodhat. A tömb összes elemét összehasonlítjuk az aktuális intervallumon. Összehasonlítjuk
    a 4. és a 4. elemeket 2nd. A 2. és a 0thpozíció elemeit is összehasonlítjuk. A tömb összes elemét összehasonlítjuk az aktuális intervallumon.
  4. Ugyanez a folyamat zajlik a többi elem esetében is. Rendezze át az összes elemet n / 4 intervallumban
  5. Végül, amikor az intervallum lesz N/8 = 8/8 =1, az 1-es intervallumban fekvő tömb elemek rendezésre kerülnek. A tömb most teljesen rendezve van. Rendezze át az elemeket n / 8 intervallumban

Shell rendezési algoritmus

 shellSort (tömb, méret) az i intervallumra <- size / 2n 1-ig minden egyes "i" intervallumnál a tömbben rendezi az összes elemet az "i" intervallumon belül

Példák Python, Java és 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); )

Bonyolultság

A héjfajta rendezése instabil rendezési algoritmus, mert ez az algoritmus nem vizsgálja az intervallumok között elhelyezkedő elemeket.

Az idő komplexitása

  • A legrosszabb eset komplexitása : kisebb vagy egyenlő a legrosszabb eset komplexitása a héjfajta esetében mindig kisebb vagy egyenlő . Szerint Poonen tétel, legrosszabb esetben összetettsége héj rendezés vagy vagy vagy valami a kettő között.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Legjobb bonyolultság : O(n*log n)
    Ha a tömb már rendezve van, akkor az egyes intervallumok (vagy növekmények) összehasonlításainak teljes száma megegyezik a tömb méretével.
  • Átlagos esetbonyolultság : O(n*log n)
    Körülbelül van .O(n1.25)

A bonyolultság a választott intervallumtól függ. A fenti bonyolultságok különböznek a kiválasztott inkrement szekvenciáktól. A legjobb növekménysorozat ismeretlen.

Tér összetettsége:

A tér összetettsége héj rendezés O(1).

Shell Rendezés alkalmazások

A héjfajta rendezése akkor használható, ha:

  • egy verem hívása fölött van. Az uClibc könyvtár ezt a fajtát használja.
  • a rekurzió meghaladja a korlátot. A bzip2 kompresszor használja.
  • A beillesztés rendezése nem teljesít jól, ha a közeli elemek messze vannak egymástól. A héjfajta rendezése segít csökkenteni a közeli elemek közötti távolságot. Így kevesebb lesz az elvégzendő csere.

érdekes cikkek...