Shell-sorteringsalgoritm med exempel

Vad är Shell-sortering?

Shell Sort, även kallad Shells metod, är en effektiv sorteringsalgoritm baserad på jämförelse på plats. Uppkallad efter Donald Shell, som introducerade idén 1959, är det en generaliserad utvidgning av insertion sortering som övervinner dess kvadratiska beteende på spridda data.

Grundtanken är att gruppera element som är långt ifrån varandra, sortera varje grupp med hjälp av insättningssortering och minska gapet steg för steg tills det når ett. Vid det laget är arrayen nästan sorterad.

Detta mellanrum, intervallet, följer en vald sekvens såsom Shells original, Knuths, Hibbards eller Sedgewicks. Shells original är n/2, n/4, ..., 1.

Skalsorteringsalgoritm

Steg 1) Initiera intervallvärdet h = n/2, där n är arrayens storlek.

Steg 2) Placera alla element inom ett avstånd från intervallet h i en dellista.

Steg 3) Sortera varje dellista med hjälp av insättningssortering.

Steg 4) Sätt ett nytt intervall h = h/2.

Steg 5) Om h > 0, återgå till steg 2. Annars, gå till steg 6.

Steg 6) Den resulterande arrayen är nu helt sorterad.

Hur Shell Sortering fungerar

Vid insättningssortering flyttas elementen endast en position åt gången. Shell Sort delar istället upp arrayen i dellistor med brett mellanrum baserat på intervallet och kör insättningssortering på varje dellista.

Allt eftersom intervallet krymper, växer dellistan. Eftersom tidigare intervall lämnar data delvis sorterade, kräver kortare intervall betydligt färre byten än att köra insättningssortering från grunden. Figuren nedan illustrerar ett Shell Sort-pass.

Funktionssätt för Shell Sort-algoritmen med exempel

Låt oss sortera arrayen nedan med hjälp av Shell Sort.

Steg 1) Arraystorleken är 8, så det initiala intervallvärdet är h = 8/2 = 4.

Steg 2) Gruppera element fyra positioner ifrån varandra. Dellistor: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Steg 3) Sortera varje dellista med hjälp av insättningssortering. En temporär variabel håller det värde som placeras medan elementen flyttas. Efter bytena ser arrayen ut så här.

Steg 4) Minska intervallet. Det nya intervallet är h = 4/2 = 2.

Steg 5) Eftersom 2 > 0, återgå till steg 2 och gruppera elementen två positioner ifrån varandra: {1, 5, 8, 7} och {4, 2, 6, 3}.

Sortera den första dellistan. Arrayen blir:

Efter sortering av den andra dellistan:

Minska intervallet igen till h = 2/2 = 1. Med ett mellanrum på ett kör Shell Sort en sista insättningssorteringsprocess över hela arrayen, som visas nedan.

Steg 6) Att dividera intervallet igen ger 0. Arrayen är nu helt sorterad:

Pseudo-Code för Shell-sortering

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

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

Shell Sort förekommer fortfarande i moderna system där stackutrymme eller enkelhet är viktigt.

• Ocuco-landskapet Linuxkärnan använder Shell Sort på platser där det är viktigt att undvika en anropsstack.
• uClibc inbäddade C-bibliotek använder Shell Sort för att hålla minnesanvändningen låg.
• bzip2 använder Shell Sort för att undvika djup rekursion under blocksortering.
• Inbäddad firmware gynnar Shell Sort för små datamängder där rekursion är begränsad.

Fördelar och nackdelar med skalsortering

Skalsorteringskomplexitetsanalys

Tidskomplexitet för skalsortering

Tidskomplexiteten för Shell Sort beror på vilken gapsekvens som används.

I bästa fall, när arrayen redan är nästan arrangerad, behöver varje genomgång endast ett logaritmiskt antal tester, vilket ger O(n log n).

I värsta fall är arrayen arrangerad så att elementen behöver maximalt antal jämförelser, och det slutliga inkrementet dominerar vid O(n^2) med Shells ursprungliga sekvens.

1. Bästa tänkbara komplexitet: O(n log n)
2. Genomsnittlig komplexitet i fallet: O(n log n) till O(n^(4/3)) beroende på gapsekvensen
3. Värsta tänkbara komplexitet: O(n^2) med Shells ursprungliga sekvens

Den bästa generella gapsekvensen är fortfarande en öppen forskningsfråga, även om Sedgewick- och Ciura-sekvenser fungerar väl i praktiken.

Skalsortering Space Complexity

Shell Sort kräver inga hjälpmatriser, så rymdkomplexiteten är O(1) oavsett inmatningsstorlek, vilket är en av dess starkaste praktiska fördelar.

Vanliga frågor