Skalsortering

I den här handledningen lär du dig hur skalsortering fungerar. Du hittar också arbetsexempel på skalsortering i C, C ++, Java och Python.

Skalsortering är en algoritm som först sorterar elementen långt ifrån varandra och successivt minskar intervallet mellan elementen som ska sorteras. Det är en generaliserad version av insättningssortering.

I skal sorteras sorteras element vid ett visst intervall. Intervallet mellan elementen minskas gradvis baserat på den använda sekvensen. Prestandan för skalsorteringen beror på vilken typ av sekvens som används för en given inmatningsmatris.

Några av de optimala sekvenserna som används är:

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

Hur fungerar Shell Sort?

  1. Antag att vi måste sortera följande array. Initial array
  2. Vi använder skalets ursprungliga sekvens (N/2, N/4,… 1) som intervall i vår algoritm.
    I den första slingan, om matrisstorleken är N = 8då, N/2 = 4jämförs elementen som ligger i intervallet och byter om de inte är i ordning.
    1. Det 0: e elementet jämförs med det 4: e elementet.
    2. Om 0:e elementet är större än den 4:e man då, är den 4: e elementet först lagras i tempvariabeln och 0thelementet (dvs. Större inslag) lagras i den 4thpositionen och elementet lagras i templagras i 0thpositionen. Ordna om elementen med n / 2-intervall
      Denna process fortsätter för alla återstående element. Ordna om alla element med n / 2-intervall
  3. I den andra slingan N/4 = 8/4 = 2tas ett intervall av och igen sorteras elementen som ligger vid dessa intervall. Ordna om elementen med n / 4-intervall
    Du kan bli förvirrad vid denna tidpunkt. Alla element i matrisen som ligger vid det aktuella intervallet jämförs.
    Elementen på 4: e och 2ndposition jämförs. Elementen vid 2: a och 0thposition jämförs också. Alla element i matrisen som ligger vid det aktuella intervallet jämförs.
  4. Samma process fortsätter för återstående element. Ordna om alla element i intervallet n / 4
  5. Slutligen, när intervallet är, N/8 = 8/8 =1sorteras arrayelementen som ligger i intervallet 1. Arrayen är nu helt sorterad. Ordna om elementen i intervallet n / 8

Skalsorteringsalgoritm

 shellSort (array, storlek) för intervall i <- storlek / 2n ner till 1 för varje intervall "i" i arrayen sortera alla element vid intervallet "i" end shellSort

Python, Java och C / C ++ exempel

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

Komplexitet

Skalsortering är en instabil sorteringsalgoritm eftersom denna algoritm inte undersöker elementen som ligger mellan intervallen.

Tidskomplexitet

  • Värsta fallets komplexitet : mindre än eller lika med värsta fallets komplexitet för skalsortering är alltid mindre än eller lika med . Enligt Poonen Sats är värsta fall komplexiteten för shell sort eller eller eller något däremellan.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Bästa fallskomplexitet : O(n*log n)
    När matrisen redan är sorterad är det totala antalet jämförelser för varje intervall (eller steg) lika med storleken på matrisen.
  • Genomsnittlig fallkomplexitet : O(n*log n)
    Det är runt .O(n1.25)

Komplexiteten beror på det valda intervallet. Ovanstående komplexiteter skiljer sig åt för olika valda steg. Bästa stegvisa sekvensen är okänd.

Rymdkomplexitet:

Utrymmets komplexitet för skalsortering är O(1).

Shell Sortera applikationer

Skalsortering används när:

  • att kalla en stack är overhead. uClibc-biblioteket använder den här typen.
  • rekursion överskrider en gräns. bzip2 kompressor använder den.
  • Insättningssortering fungerar inte bra när de nära elementen ligger långt ifrån varandra. Skalsortering hjälper till att minska avståndet mellan de nära elementen. Således blir det mindre antal byten som ska utföras.

Intressanta artiklar...