Shell Sort

I denne opplæringen lærer du hvordan skallsortering fungerer. Du finner også arbeidseksempler på skallsortering i C, C ++, Java og Python.

Shell sort er en algoritme som først sorterer elementene langt fra hverandre og suksessivt reduserer intervallet mellom elementene som skal sorteres. Det er en generalisert versjon av innsettingssortering.

I skallsortering sorteres elementer med et bestemt intervall. Intervallet mellom elementene reduseres gradvis basert på sekvensen som brukes. Ytelsen til skallsorteringen avhenger av typen sekvens som brukes for et gitt inndatamat.

Noen av de optimale sekvensene som brukes er:

  • Shells opprinnelige sekvens: N/2 , N/4 ,… , 1
  • Knuths trinn: 1, 4, 13,… , (3k - 1) / 2
  • Sedgewicks trinn: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Hibbards trinn: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernov og Stasevich økning: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Hvordan fungerer Shell Sort?

  1. Anta at vi må sortere følgende matrise. Innledende matrise
  2. Vi bruker skallets opprinnelige sekvens (N/2, N/4,… 1) som intervaller i algoritmen vår.
    I den første sløyfen, hvis matrisestørrelsen er N = 8da, blir elementene som ligger i intervallet N/2 = 4, sammenlignet og byttet ut hvis de ikke er i orden.
    1. Det 0. Elementet sammenlignes med det fjerde elementet.
    2. Hvis det 0te elementet er større enn det fjerde, lagres det fjerde elementet først i tempvariabel og 0thelementet (dvs. større element) lagres i 4thposisjonen og elementet som er lagret i templagres i 0thposisjonen. Omorganisere elementene i intervallet n / 2
      Denne prosessen fortsetter for alle gjenværende elementer. Omorganiser alle elementene i n / 2-intervallet
  3. I den andre sløyfen N/4 = 8/4 = 2tas et intervall på, og igjen sorteres elementene som ligger ved disse intervallene. Omorganisere elementene i n / 4-intervallet.
    Du kan bli forvirret på dette punktet. Alle elementene i matrisen som ligger i det nåværende intervallet sammenlignes.
    Elementene på 4. og 2ndposisjon sammenlignes. Elementene på 2. og 0thposisjon blir også sammenlignet. Alle elementene i matrisen som ligger i det nåværende intervallet sammenlignes.
  4. Den samme prosessen fortsetter for gjenværende elementer. Omorganiser alle elementene i intervallet n / 4
  5. Til slutt, når intervallet er N/8 = 8/8 =1, blir matriseelementene som ligger i intervallet 1 sortert. Matrisen er nå fullstendig sortert. Omorganiser elementene med n / 8-intervall

Skalsorteringsalgoritme

 shellSort (array, størrelse) for intervall i <- størrelse / 2n ned til 1 for hvert intervall "i" i array sorterer alle elementene i intervallet "i" end shellSort

Python, Java og C / C ++ eksempler

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); )

Kompleksitet

Skalsortering er en ustabil sorteringsalgoritme fordi denne algoritmen ikke undersøker elementene som ligger mellom intervallene.

Tidskompleksitet

  • Verste sakskompleksitet : mindre enn eller lik Kompleksitet i verste fall for skallsortering er alltid mindre enn eller lik . Ifølge Poonen Theorem, worst case kompleksitet for skall liksom er eller eller eller noe i mellom.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Best case kompleksitet : O(n*log n)
    Når matrisen allerede er sortert, er det totale antallet sammenligninger for hvert intervall (eller inkrement) lik størrelsen på matrisen.
  • Gjennomsnittlig sakskompleksitet : O(n*log n)
    Det er rundt .O(n1.25)

Kompleksiteten avhenger av det valgte intervallet. Ovennevnte kompleksiteter er forskjellige for forskjellige valgte sekvenser. Beste økningssekvens er ukjent.

Romkompleksitet:

Plasskompleksiteten for skallsortering er O(1).

Shell Sort applikasjoner

Skalsortering brukes når:

  • å ringe en stabel er overhead. uClibc-biblioteket bruker denne typen.
  • rekursjon overstiger en grense. bzip2 kompressor bruker den.
  • Innsettingssortering fungerer ikke bra når de nære elementene er langt fra hverandre. Shell sort hjelper til med å redusere avstanden mellom de nære elementene. Dermed vil det være færre antall bytter som skal utføres.

Interessante artikler...