Shell Sort-algoritme met voorbeeld

Wat is Shell Sort?

Shell Sort, ook wel Shells methode genoemd, is een efficiënt sorteeralgoritme dat in-place sorteert op basis van vergelijkingen. Het is vernoemd naar Donald Shell, die het idee in 1959 introduceerde, en is een gegeneraliseerde uitbreiding van insertion sort die het kwadratische gedrag van insertion sort bij verspreide data overwint.

Het basisidee is om elementen die ver uit elkaar liggen te groeperen, elke groep te sorteren met behulp van invoegsortering en de afstand tussen de elementen stap voor stap te verkleinen totdat deze één is. Tegen die tijd is de array bijna gesorteerd.

Deze kloof, het interval, volgt een gekozen volgorde, zoals het origineel van Shell, Knuth, Hibbard of Sedgewick. Het origineel van Shell is n/2, n/4, ..., 1.

Shell-sorteeralgoritme

Stap 1) Initialiseer de intervalwaarde h = n/2, waarbij n de grootte van de array is.

Stap 2) Plaats alle elementen binnen een afstand van het interval h in een sublijst.

Stap 3) Sorteer elke sublijst met behulp van invoegsortering.

Stap 4) Stel een nieuw interval in: h = h/2.

Stap 5) Als h > 0, ga dan terug naar stap 2. Anders ga je naar stap 6.

Stap 6) De resulterende array is nu volledig gesorteerd.

Hoe Shell Sorteren werkt

Bij insertion sort verschuiven elementen slechts één positie per keer. Shell Sort verdeelt de array daarentegen in sublijsten met ruime tussenruimte op basis van het interval en voert insertion sort uit op elke sublijst.

Naarmate het interval kleiner wordt, neemt de grootte van de sublijst toe. Omdat eerdere stappen de gegevens gedeeltelijk gesorteerd achterlaten, vereisen kleinere intervallen veel minder wisselingen dan een volledige verwerking. invoegsoort van begin af aan. De onderstaande afbeelding illustreert één Shell Sort-doorgang.

De werking van het Shell Sort-algoritme met een voorbeeld.

Laten we de onderstaande array sorteren met behulp van Shell Sort.

Stap 1) De arraygrootte is 8, dus de initiële intervalwaarde is h = 8/2 = 4.

Stap 2) Groepeer elementen met een tussenruimte van vier posities. Sublijsten: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Stap 3) Sorteer elke sublijst met behulp van invoegsortering. Een tijdelijke variabele slaat de waarde op die wordt ingevoegd terwijl elementen verschuiven. Na de wisselingen ziet de array er als volgt uit.

Stap 4) Verklein het interval. Het nieuwe interval is h = 4/2 = 2.

Stap 5) Omdat 2 > 0, ga terug naar stap 2 en groepeer de elementen op twee posities afstand: {1, 5, 8, 7} en {4, 2, 6, 3}.

Sorteer de eerste sublijst. De array wordt:

Na het sorteren van de tweede sublijst:

Verklein het interval opnieuw naar h = 2/2 = 1. Met een tussenruimte van één voert Shell Sort een laatste invoegsorteerbewerking uit over de hele array, zoals hieronder weergegeven.

Stap 6) Als je het interval opnieuw deelt, krijg je 0. De array is nu volledig gesorteerd.

Pseudo-Code voor Shell Sort

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > 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

Shell Sort wordt nog steeds gebruikt in moderne systemen waar stackruimte of eenvoud belangrijk zijn.

• De Linux kernel Maakt gebruik van Shell Sort op plaatsen waar het vermijden van een aanroepstack van belang is.
• De ingebedde C-bibliotheek uClibc gebruikt Shell Sort om het geheugenverbruik laag te houden.
• bzip2 gebruikt Shell Sort om diepe recursie tijdens het sorteren van blokken te vermijden.
• Ingebouwde firmware geeft de voorkeur aan Shell Sort voor kleine datasets waar recursie beperkt is.

Voordelen en nadelen van schelpsortering

Complexiteitsanalyse van shellsortering

Tijdscomplexiteit van shellsortering

De tijdscomplexiteit van Shell Sort hangt af van de gebruikte gap-sequentie.

In het beste geval, wanneer de array al bijna geordend is, heeft elke doorgang slechts een logaritmisch aantal tests nodig, wat O(n log n) oplevert.

In het slechtste geval is de array zo gerangschikt dat elementen het maximale aantal vergelijkingen nodig hebben, en de laatste incrementatie domineert met O(n^2) ten opzichte van Shells oorspronkelijke volgorde.

1. Complexiteit in het beste geval: O(n log n)
2. Gemiddelde complexiteit: O(n log n) tot O(n^(4/3)) afhankelijk van de volgorde van de gaten
3. Worst-case complexiteit: O(n^2) met Shells oorspronkelijke sequentie

De beste algemene gap-sequentie is nog steeds onderwerp van onderzoek, hoewel de sequenties van Sedgewick en Ciura in de praktijk goed presteren.

Complexiteit van de shell-sorteerruimte

Shell Sort vereist geen hulpmatrices, waardoor de ruimtecomplexiteit O(1) is, ongeacht de grootte van de invoer. Dit is een van de grootste praktische voordelen.

Veelgestelde vragen