Skalsorteringsalgoritm med EXEMPEL
Sarah Chen
Vad är Shell Sort
Shells metod, eller Shell-sortering i datastruktur, är en effektiv jämförelsesorteringsalgoritm på plats. Den är uppkallad efter Donald Shell när han föreslog den första idén redan 1959. Skalsortering är en generaliserad förlängning av insättningssorteringsalgoritmen.
Den grundläggande idén med denna sorteringsalgoritm är att gruppera de element som är långt ifrån varandra och sortera dem därefter. Minska sedan gradvis gapet mellan dem. Skalsortering övervinner den genomsnittliga falltidskomplexiteten för infogningssortering genom att jämföra och utbyta element som är långt borta.
Detta gap, känt som intervallet, reduceras enligt några optimala gapsekvenser. Körtiden för skalsortering är också beroende av dessa sekvenser. Det finns flera gapsekvenser, som Shells ursprungliga sekvens, Knuths formel, Hibbards inkrement, etc. Shells ursprungliga gapsekvens är – n/2, n/4, n/8, ……….1
Skalsorteringsalgoritm
Stegen eller proceduren för skalsorteringsalgoritmen är som följer-
Steg 1) Initiera intervallvärdet, h = n/2. (I det här exemplet är n storleken på arrayen)
Steg 2) Lägg alla element inom ett avstånd från intervallet h i en underlista.
Steg 3) Sortera dessa underlistor med hjälp av infogningssortering.
Steg 4) Ställ in nytt intervall, h=h/2.
Steg 5) Om h>0, gå till steg 2. Gå annars till steg 6.
Steg 6) Den resulterande utgången kommer att vara den sorterade arrayen.
Hur Shell Sortering fungerar
Vid insättningssortering flyttas element endast med en position åt gången. Tvärtom delar skalsortering upp arrayen i mindre bitar baserat på intervallvärdet och utför insättningssortering på dessa bitar.
Gradvis minskar intervallvärdet och storleken på de delade bitarna ökar. Eftersom bitarna är individuellt sorterade i förväg kräver sammanslagning av delarna färre steg än insättningssortering.
Följande GIF visar en demonstration av skalsortering. I den här demon jämförs och byts det röda och det blå värdet baserat på insättningssort. Sedan minskar intervallet, och skalsortering initierar infogningssortering i den nästan sorterade datan.
Arbetar med Shell Sort Algorithm
Låt oss se ett följande exempel på en skalsorteringsalgoritm. I det här exemplet kommer vi att sortera följande array med hjälp av skalsortering:
Steg 1) Här är matrisstorleken 8. Således blir intervallvärdet h = 8/2 eller 4.
Steg 2) Nu kommer vi att lagra alla element på ett avstånd av 4. För vårt fall är underlistorna- {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Steg 3) Nu kommer dessa underlistor att sorteras med hjälp av infogningssortering, där en temporär variabel används för att jämföra båda siffrorna och sortera därefter.
Arrayen skulle se ut som följande efter byte av operationer-
Steg 4) Nu kommer vi att minska det initiala värdet för intervallet. Det nya intervallet blir h=h/2 eller 4/2 eller 2.
Steg 5) Som 2>0 går vi till steg 2 för att lagra alla element på ett avstånd av 2. För denna tid är underlistorna-
{1, 5, 8, 7}, {4, 2, 6, 3}
Sedan kommer dessa underlistor att sorteras med hjälp av infogningssortering. Efter att ha jämfört och bytt ut den första underlistan blir arrayen följande.
Efter sortering av den andra underlistan kommer den ursprungliga arrayen att vara:
Sedan kommer intervallet att minskas igen. Nu kommer intervallet att vara h=h/2 eller 2/1 eller 1. Därför kommer vi att använda insättningssorteringsalgoritmen för att sortera den modifierade matrisen.
Följande är en steg-för-steg-procedurskildring av insättningssort.
Intervallet divideras återigen med 2. Vid det här laget blir intervallet 0. Så vi går till steg 6.
Steg 6) Eftersom intervallet är 0, sorteras matrisen efter denna tid. Den sorterade matrisen är-
Pseudo-kod
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
a[j] = a[j - interval];
a[j] = temp;
End
Skalsorteringsprogram i C/C++
Ingång:
//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
for (int interval = size / 2; interval > 0; interval /= 2) {
for (int i = interval; i < size; i += 1) {
int temp = data[i];
int j;
for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
data[j] = data[j - interval];
}
data[j] = temp;
}
}
}
int main() {
int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
int size = sizeof(data) / sizeof(data[0]);
ShellSort(data, size);
cout << "Sorted Output: \n";
for (int i = 0; i < size; i++)
cout << data[i] << " ";
cout << "\n";
}
Produktion:
Sorted Output: 1 2 3 4 5 6 7 8
Skalsorteringsexempel i Python
Ingång:
#Shell Sort Example in Python
def ShellSort(data, size):
interval = size // 2
while interval > 0:
for i in range(interval, size):
temp = data[i]
j = i
while j >= interval and data[j - interval] > temp:
data[j] = data[j - interval]
j -= interval
data[j] = temp
interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)
Produktion:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Tillämpningar av Shell Sort
Här är viktiga tillämpningar av Shell Sort:
- Skalsortering används i Linuxkärnan eftersom den inte använder en samtalsstack.
- uClibc-biblioteket använder Shell-sort.
- bzip2-kompressorn använder Shell-sortering för att sluta överskrida rekursion.
Fördelar och nackdelar med Shell Sort
| Fördelar | Nackdelar |
|---|---|
| Inget stacksamtal krävs. | Inte effektivt för stora arraystorlekar. |
| Enkel implementering. | Ineffektiv för vitt spridda element. |
| Effektivt för mindre brett placerade element. |
Skalsorteringskomplexitetsanalys
Tidskomplexitet för skalsortering
Tidskomplexiteten för skalsorteringsalgoritmen är O(n^2). Resonemanget är som följer:
För det bästa scenariot, den totala mängden tester för alla intervall när arrayen tidigare arrangerades lika med log n. Sålunda skulle komplexiteten vara O(n*log n).
För det värsta scenariot, låt oss betrakta arrayen på ett sådant sätt att elementen kräver det högsta antalet jämförelser. Då kommer inte alla element att jämföras och bytas förrän den sista iterationen. Därför är den totala jämförelsen som krävs för den slutliga ökningen O(n^2).
Sammanfattningsvis skulle tidskomplexiteten vara
- Bästa fallets komplexitet: O(n*log n)
- Genomsnittlig fallkomplexitet: O(n*log n)
- Komplexitet i värsta fall: O(n^2)
Körtidskomplexiteten för skalsorteringen beror mycket på de sekvenser som används för gapinkrement. Den bästa inkrementsekvensen för skalsortering är dock fortfarande okänd.
Skalsortering Space Complexity
I den här jämförelsesorten behöver vi inget extra utrymme. Alltså är rymdkomplexiteten för denna typ av algoritm O(1).