Αλγόριθμος Ταξινόμησης Shell με Παράδειγμα

Τι είναι η ταξινόμηση Shell;

Η ταξινόμηση Shell, που ονομάζεται επίσης μέθοδος Shell, είναι ένας αποτελεσματικός αλγόριθμος ταξινόμησης που βασίζεται σε επιτόπια σύγκριση. Πήρε το όνομά της από τον Donald Shell, ο οποίος εισήγαγε την ιδέα το 1959, και είναι μια γενικευμένη επέκταση της ταξινόμησης με εισαγωγή που ξεπερνά την τετραγωνική συμπεριφορά της σε διάσπαρτα δεδομένα.

Η βασική ιδέα είναι να ομαδοποιήσετε στοιχεία που βρίσκονται σε μεγάλη απόσταση μεταξύ τους, να ταξινομήσετε κάθε ομάδα χρησιμοποιώντας ταξινόμηση με εισαγωγή και να συρρικνώσετε το κενό βήμα προς βήμα μέχρι να φτάσει στο ένα. Μέχρι τότε, ο πίνακας είναι σχεδόν ταξινομημένος.

Αυτό το κενό, το διάστημα, ακολουθεί μια επιλεγμένη ακολουθία όπως η αρχική ακολουθία του Shell, του Knuth, του Hibbard ή του Sedgewick. Η αρχική ακολουθία του Shell είναι n/2, n/4, ..., 1.

Αλγόριθμος ταξινόμησης κελύφους

Βήμα 1) Αρχικοποιήστε την τιμή διαστήματος h = n/2, όπου n είναι το μέγεθος του πίνακα.

Βήμα 2) Τοποθετήστε όλα τα στοιχεία εντός μιας απόστασης από το διάστημα h σε μια υπολίστα.

Βήμα 3) Ταξινομήστε κάθε υπολίστα χρησιμοποιώντας ταξινόμηση με εισαγωγή.

Βήμα 4) Ορίστε ένα νέο διάστημα h = h/2.

Βήμα 5) Εάν h > 0, επιστρέψτε στο Βήμα 2. Διαφορετικά, προχωρήστε στο Βήμα 6.

Βήμα 6) Ο πίνακας που προκύπτει είναι πλέον πλήρως ταξινομημένος.

Πώς λειτουργεί η ταξινόμηση κελύφους

Στην ταξινόμηση με εισαγωγή, τα στοιχεία μετακινούνται μόνο κατά μία θέση κάθε φορά. Η ταξινόμηση με κέλυφος διαιρεί τον πίνακα σε υπολίστες με μεγάλη απόσταση μεταξύ τους με βάση το διάστημα και εκτελεί ταξινόμηση με εισαγωγή σε κάθε υπολίστα.

Καθώς το διάστημα συρρικνώνεται, το μέγεθος της υπολίστας αυξάνεται. Επειδή τα πρώτα περάσματα αφήνουν τα δεδομένα μερικώς ταξινομημένα, τα μικρότερα διαστήματα απαιτούν πολύ λιγότερες εναλλαγές από την εκτέλεση είδος εισαγωγής από την αρχή. Το παρακάτω σχήμα απεικονίζει ένα πέρασμα Shell Sort.

Λειτουργία του Αλγορίθμου Ταξινόμησης Shell με Παράδειγμα

Ας ταξινομήσουμε τον παρακάτω πίνακα χρησιμοποιώντας Shell Sort.

Βήμα 1) Το μέγεθος του πίνακα είναι 8, επομένως η αρχική τιμή διαστήματος είναι h = 8/2 = 4.

Βήμα 2) Ομαδοποιήστε τα στοιχεία με απόσταση τεσσάρων θέσεων μεταξύ τους. Υπολίστες: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Βήμα 3) Ταξινομήστε κάθε υπολίστα χρησιμοποιώντας ταξινόμηση εισαγωγής. Μια προσωρινή μεταβλητή διατηρεί την τιμή που τοποθετείται ενώ τα στοιχεία μετακινούνται. Μετά τις εναλλαγές, ο πίνακας μοιάζει με αυτό.

Βήμα 4) Μειώστε το διάστημα. Το νέο διάστημα είναι h = 4/2 = 2.

Βήμα 5) Επειδή 2 > 0, επιστρέψτε στο Βήμα 2 και ομαδοποιήστε τα στοιχεία σε δύο θέσεις μεταξύ τους: {1, 5, 8, 7} και {4, 2, 6, 3}.

Ταξινομήστε την πρώτη υπολίστα. Ο πίνακας γίνεται:

Μετά την ταξινόμηση της δεύτερης υπολίστας:

Μειώστε ξανά το διάστημα σε h = 2/2 = 1. Με κενό ίσο με ένα, η Ταξινόμηση με Φλοιό εκτελεί ένα τελικό πέρασμα ταξινόμησης με εισαγωγή σε ολόκληρο τον πίνακα, όπως φαίνεται παρακάτω.

Βήμα 6) Διαιρώντας ξανά το διάστημα προκύπτει 0. Ο πίνακας είναι πλέον πλήρως ταξινομημένος:

Ψευδής-Code για ταξινόμηση με κέλυφος

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

Πρόγραμμα ταξινόμησης κελύφους σε C/C++

εισόδου:

//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";
}

Παραγωγή:

Sorted Output:

1 2 3 4 5 6 7 8

Παράδειγμα ταξινόμησης κελύφους σε Python

εισόδου:

#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)

Παραγωγή:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Εφαρμογές Shell Sort

Η ταξινόμηση με κέλυφος εξακολουθεί να εμφανίζεται σε σύγχρονα συστήματα όπου ο χώρος στοίβας ή η απλότητα έχουν σημασία.

• The Πυρήνα του Linux χρησιμοποιεί την Ταξινόμηση με Κέλυφος σε σημεία όπου η αποφυγή μιας στοίβας κλήσεων έχει σημασία.
• Η ενσωματωμένη βιβλιοθήκη C του uClibc χρησιμοποιεί ταξινόμηση με κέλυφος για να διατηρεί χαμηλή τη χρήση μνήμης.
• Το bzip2 χρησιμοποιεί Shell Sort για να αποφύγει την βαθιά αναδρομή κατά την ταξινόμηση σε μπλοκ.
• Το ενσωματωμένο υλικολογισμικό ευνοεί την ταξινόμηση Shell για μικρά σύνολα δεδομένων όπου η αναδρομή είναι περιορισμένη.

Πλεονεκτήματα και μειονεκτήματα της ταξινόμησης με κέλυφος

Ανάλυση πολυπλοκότητας ταξινόμησης κελύφους

Χρονική πολυπλοκότητα της ταξινόμησης κελύφους

Η χρονική πολυπλοκότητα της Ταξινόμησης με Φλοιό εξαρτάται από την ακολουθία κενών που χρησιμοποιείται.

Στην καλύτερη περίπτωση, όταν ο πίνακας είναι ήδη σχεδόν διατεταγμένος, κάθε πέρασμα χρειάζεται μόνο έναν λογαριθμικό αριθμό δοκιμών, δίνοντας O(n log n).

Στη χειρότερη περίπτωση, ο πίνακας είναι διατεταγμένος έτσι ώστε τα στοιχεία να χρειάζονται τις μέγιστες συγκρίσεις και η τελική αύξηση να κυριαρχεί στο O(n^2) με την αρχική ακολουθία της Shell.

1. καλυτερα-case complexity: O(n log n)
2. Πολυπλοκότητα μέσης περίπτωσης: O(n log n) έως O(n^(4/3)) ανάλογα με την ακολουθία κενών
3. Χειρότερης περίπτωσης πολυπλοκότητας: O(n^2) με την αρχική ακολουθία της Shell

Η καλύτερη ακολουθία κενών γενικής χρήσης εξακολουθεί να αποτελεί ανοιχτό ερευνητικό ερώτημα, αν και οι ακολουθίες Sedgewick και Ciura έχουν καλή απόδοση στην πράξη.

Πολυπλοκότητα χώρου ταξινόμησης κελύφους

Η ταξινόμηση Shell δεν απαιτεί βοηθητικούς πίνακες, επομένως η πολυπλοκότητα του χώρου είναι O(1) ανεξάρτητα από το μέγεθος εισόδου, το οποίο είναι ένα από τα ισχυρότερα πρακτικά πλεονεκτήματά της.

Συχνές Ερωτήσεις