Shell-sorteeralgoritme met VOORBEELD
Wat is Shell-sortering
De methode van Shell, of Shell sort in Data structure, is een efficiënt in-place sorteeralgoritme voor vergelijkingen. Het is vernoemd naar Donald Shell toen hij het oorspronkelijke idee in 1959 voorstelde. Shell sort is een algemene uitbreiding van het invoegsorteeralgoritme.
Het fundamentele idee van dit sorteeralgoritme is om de elementen die ver uit elkaar liggen te groeperen en ze dienovereenkomstig te sorteren. Vervolgens wordt de kloof ertussen geleidelijk kleiner. Shell sort overwint de gemiddelde case time complexiteit van insertion sort door elementen die ver uit elkaar liggen te vergelijken en uit te wisselen.
Deze kloof, bekend als het interval, wordt verkleind volgens enkele optimale reeksen tussenruimten. De looptijd van shell-sortering is ook afhankelijk van deze reeksen. Er zijn verschillende gap-reeksen, zoals de originele reeks van Shell, de formule van Knuth, de stappen van Hibbard, enz. De originele gap-reeks van Shell is - n/2, n/4, n/8, ……….1
Shell-sorteeralgoritme
De stappen of procedure voor het shell-sorteeralgoritme zijn als volgt:
Stap 1) Initialiseer de intervalwaarde, h = n/2. (In dit voorbeeld is n de grootte van de array)
Stap 2) Plaats alle elementen binnen een afstand van het interval h in een sublijst.
Stap 3) Sorteer deze sublijsten met behulp van invoegsortering.
Stap 4) Stel een nieuw interval in, h=h/2.
Stap 5) Indien h>0, ga naar stap 2. Ga anders naar stap 6.
Stap 6) De resulterende uitvoer is de gesorteerde array.
Hoe Shell Sorteren werkt
Bij invoegsortering worden elementen slechts één positie tegelijk verplaatst. Integendeel, shell sort verdeelt de array in kleinere stukken op basis van de intervalwaarde en voert een invoegsortering uit op die stukken.
Geleidelijk neemt de intervalwaarde af en neemt de grootte van de verdeelde stukken toe. Omdat de stukken vooraf afzonderlijk worden gesorteerd, vereist het samenvoegen van deze stukken minder stappen dan het samenvoegen van de stukken invoegsoort.
De volgende GIF toont een demonstratie van shell sort. In deze demo worden de rood en blauw aangegeven waarden vergeleken en verwisseld op basis van insertion sort. Vervolgens neemt het interval af en start shell sort insertion sort in die bijna gesorteerde data.
Werking van het Shell Sort-algoritme
Laten we eens kijken naar het volgende voorbeeld van een shell sort-algoritme. In dit voorbeeld sorteren we de volgende array met shell sort:
Stap 1) Hier is de arraygrootte 8. De intervalwaarde is dus h = 8/2 of 4.
Stap 2) Nu slaan we alle elementen op een afstand van 4 op. Voor ons geval zijn de sublijsten: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Stap 3) Deze sublijsten worden nu gesorteerd met behulp van invoegsortering, waarbij een tijdelijke variabele wordt gebruikt om beide getallen te vergelijken en dienovereenkomstig te sorteren.
De array zou er na het wisselen van de bewerkingen als volgt uitzien:
Stap 4) Nu zullen we de beginwaarde van het interval verlagen. Het nieuwe interval wordt h=h/2 of 4/2 of 2.
Stap 5) Als 2>0 gaan we naar stap 2 om alle elementen op een afstand van 2 op te slaan. Voor deze keer zijn de sublijsten:
{1, 5, 8, 7}, {4, 2, 6, 3}
Vervolgens worden deze sublijsten gesorteerd met behulp van insertion sort. Na het vergelijken en verwisselen van de eerste sublijst, zou de array er als volgt uitzien.
Na het sorteren van de tweede sublijst zal de originele array er als volgt uitzien:
Vervolgens wordt het interval opnieuw verkleind. Nu zal het interval h=h/2 of 2/1 of 1 zijn. Daarom zullen we het invoeg-sorteeralgoritme gebruiken om de gewijzigde array te sorteren.
Hieronder vindt u een stapsgewijze beschrijving van de procedure voor invoegsortering.
Het interval wordt opnieuw gedeeld door 2. Tegen die tijd wordt het interval 0. We gaan dus naar stap 6.
Stap 6) Omdat het interval 0 is, wordt de array op dit tijdstip gesorteerd. De gesorteerde array is-
Pseudo-code
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
Shell-sorteerprogramma in C/C++
Input:
//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"; }
Output:
Sorted Output: 1 2 3 4 5 6 7 8
Voorbeeld van shell-sortering in Python
Input:
#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)
Output:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Toepassingen van Shell Sort
Hier zijn belangrijke toepassingen van Shell Sort:
- Shell-sortering wordt gebruikt in de Linux kernel omdat het geen call-stack gebruikt.
- uClibc-bibliotheek gebruikt Shell-sortering.
- bzip2-compressor gebruikt Shell-sortering om overschrijding van recursie te voorkomen.
Voordelen en nadelen van Shell-sortering
Voordelen | Nadelen |
---|---|
Er is geen stapeloproep vereist. | Niet efficiënt voor grote arraygroottes. |
Eenvoudige implementatie. | Inefficiënt voor wijdverspreide elementen. |
Efficiënt voor minder ver uit elkaar geplaatste elementen. |
Complexiteitsanalyse van shellsortering
Tijdscomplexiteit van shellsortering
De tijdcomplexiteit van het shell sort-algoritme is O(n^2). De redenering is als volgt:
Voor het beste scenario is het totale aantal tests voor alle intervallen wanneer de array eerder was gerangschikt gelijk aan log n. De complexiteit zou dus O(n*log n) zijn.
Laten we, in het slechtste geval, ervan uitgaan dat de array zo is samengesteld dat de elementen het grootste aantal vergelijkingen vereisen. Dan worden pas bij de laatste iteratie alle elementen vergeleken en geschakeld. Daarom zijn de totale vergelijkingen die nodig zijn voor de laatste stap O(n^2).
Concluderend zouden de tijdscomplexiteiten zijn:
- Beste geval complexiteit: O(n*log n)
- Gemiddelde casuscomplexiteit: O(n*log n)
- Complexiteit in het ergste geval: O(n^2)
De complexiteit van de uitvoeringstijd van shell sort hangt sterk af van de gebruikte gap increment sequences. De beste increment sequence voor shell sort is echter nog onbekend.
Complexiteit van de shell-sorteerruimte
In deze vergelijkingssortering hebben we geen extra hulpruimte nodig. De ruimtecomplexiteit van dit soort algoritme is dus O(1).