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.

Shell Sorteerwerken

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:

Werking van het Shell Sort-algoritme

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}.

Werking van het Shell Sort-algoritme

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:

Werking van het Shell Sort-algoritme

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}

Werking van het Shell Sort-algoritme

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.

Werking van het Shell Sort-algoritme

Na het sorteren van de tweede sublijst zal de originele array er als volgt uitzien:

Werking van het Shell Sort-algoritme

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.

Werking van het Shell Sort-algoritme

Werking van het Shell Sort-algoritme

Werking van het Shell Sort-algoritme

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-

Werking van het Shell Sort-algoritme

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:

  1. Beste geval complexiteit: O(n*log n)
  2. Gemiddelde casuscomplexiteit: O(n*log n)
  3. 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).