Αλγόριθμος ταξινόμησης κελύφους με EXAMPLE
Σάρα Τσεν
Τι είναι το Shell Sort
Η μέθοδος της Shell, ή η ταξινόμηση Shell στη δομή δεδομένων, είναι ένας αποτελεσματικός αλγόριθμος επιτόπιας σύγκρισης ταξινόμησης. Πήρε το όνομά του από τον Donald Shell όταν πρότεινε την αρχική ιδέα το 1959. Η ταξινόμηση κελύφους είναι μια γενικευμένη επέκταση του αλγόριθμου ταξινόμησης εισαγωγής.
Η θεμελιώδης ιδέα αυτού του αλγορίθμου ταξινόμησης είναι να ομαδοποιήσει τα στοιχεία που απέχουν πολύ και να τα ταξινομήσει ανάλογα. Στη συνέχεια μειώστε σταδιακά το κενό μεταξύ τους. Η ταξινόμηση κελύφους ξεπερνά τη μέση πολυπλοκότητα χρόνου περίπτωσης της ταξινόμησης εισαγωγής συγκρίνοντας και ανταλλάσσοντας στοιχεία που βρίσκονται πολύ μακριά.
Αυτό το κενό, γνωστό ως διάστημα, μειώνεται σύμφωνα με ορισμένες βέλτιστες ακολουθίες χάσματος. Ο χρόνος εκτέλεσης της ταξινόμησης κελύφους εξαρτάται επίσης από αυτές τις ακολουθίες. Υπάρχουν πολλές ακολουθίες κενού, όπως η αρχική ακολουθία του Shell, ο τύπος του Knuth, οι προσαυξήσεις του Hibbard κ.λπ. Η αρχική ακολουθία κενού του Shell είναι – n/2, n/4, n/8, ……….1
Αλγόριθμος ταξινόμησης κελύφους
Τα βήματα ή η διαδικασία για τον αλγόριθμο ταξινόμησης κελύφους είναι τα εξής:
Βήμα 1) Αρχικοποιήστε την τιμή του διαστήματος, h = n/2. (Σε αυτό το παράδειγμα, n είναι το μέγεθος του πίνακα)
Βήμα 2) Βάλτε όλα τα στοιχεία σε απόσταση από το διάστημα h σε μια υπολίστα.
Βήμα 3) Ταξινομήστε αυτές τις υπολίστες χρησιμοποιώντας ταξινόμηση εισαγωγής.
Βήμα 4) Ορίστε νέο διάστημα, h=h/2.
Βήμα 5) Εάν h>0, μεταβείτε στο βήμα 2. Διαφορετικά, μεταβείτε στο βήμα 6.
Βήμα 6) Η προκύπτουσα έξοδος θα είναι ο ταξινομημένος πίνακας.
Πώς λειτουργεί η ταξινόμηση κελύφους
Στην ταξινόμηση εισαγωγής, τα στοιχεία μετακινούνται μόνο κατά μία θέση κάθε φορά. Αντίθετα, η ταξινόμηση φλοιού διαιρεί τον πίνακα σε μικρότερα κομμάτια με βάση την τιμή του διαστήματος και εκτελεί ταξινόμηση εισαγωγής σε αυτά τα κομμάτια.
Σταδιακά, η τιμή του διαστήματος μειώνεται και το μέγεθος των διαιρεμένων τεμαχίων αυξάνεται. Καθώς τα κομμάτια ταξινομούνται ξεχωριστά εκ των προτέρων, η συγχώνευση αυτών των κομματιών απαιτεί λιγότερα βήματα από το είδος εισαγωγής.
Το παρακάτω GIF δείχνει μια επίδειξη ταξινόμησης κελύφους. Σε αυτήν την επίδειξη, η κόκκινη και η μπλε τιμή που υποδεικνύεται συγκρίνονται και ανταλλάσσονται με βάση την ταξινόμηση εισαγωγής. Στη συνέχεια, το διάστημα μειώνεται και η ταξινόμηση φλοιού ξεκινά την ταξινόμηση εισαγωγής σε αυτά τα σχεδόν ταξινομημένα δεδομένα.
Εργασία του αλγόριθμου ταξινόμησης κελύφους
Ας δούμε ένα ακόλουθο παράδειγμα αλγορίθμου ταξινόμησης κελύφους. Σε αυτό το παράδειγμα, θα ταξινομήσουμε τον ακόλουθο πίνακα χρησιμοποιώντας ταξινόμηση φλοιού:
Βήμα 1) Εδώ, το μέγεθος του πίνακα είναι 8. Έτσι, η τιμή του διαστήματος θα είναι h = 8/2 ή 4.
Βήμα 2) Τώρα, θα αποθηκεύσουμε όλα τα στοιχεία σε απόσταση 4. Για την περίπτωσή μας, οι υπολίστες είναι- {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Βήμα 3) Τώρα, αυτές οι υπολίστες θα ταξινομηθούν χρησιμοποιώντας ταξινόμηση εισαγωγής, όπου χρησιμοποιείται μια προσωρινή μεταβλητή για τη σύγκριση και των δύο αριθμών και την ανάλογη ταξινόμηση.
Ο πίνακας θα είναι όπως ο ακόλουθος μετά από πράξεις εναλλαγής-
Βήμα 4) Τώρα, θα μειώσουμε την αρχική τιμή του διαστήματος. Το νέο διάστημα θα είναι h=h/2 ή 4/2 ή 2.
Βήμα 5) Ως 2>0, θα πάμε στο βήμα 2 για να αποθηκεύσουμε όλα τα στοιχεία σε απόσταση 2. Για αυτήν τη φορά, οι υπολίστες είναι-
{1, 5, 8, 7}, {4, 2, 6, 3}
Στη συνέχεια, αυτές οι υπολίστες θα ταξινομηθούν χρησιμοποιώντας ταξινόμηση εισαγωγής. Μετά τη σύγκριση και την ανταλλαγή της πρώτης υπολίστας, ο πίνακας θα είναι ο ακόλουθος.
Μετά την ταξινόμηση της δεύτερης υπολίστας, ο αρχικός πίνακας θα είναι:
Μετά πάλι, το διάστημα θα μειωθεί. Τώρα το διάστημα θα είναι h=h/2 ή 2/1 ή 1. Ως εκ τούτου, θα χρησιμοποιήσουμε τον αλγόριθμο ταξινόμησης εισαγωγής για να ταξινομήσουμε τον τροποποιημένο πίνακα.
Ακολουθεί η βήμα προς βήμα διαδικαστική απεικόνιση της ταξινόμησης εισαγωγής.
Το διάστημα διαιρείται πάλι με το 2. Μέχρι αυτή τη στιγμή, το διάστημα γίνεται 0. Οπότε πηγαίνουμε στο βήμα 6.
Βήμα 6) Καθώς το διάστημα είναι 0, ο πίνακας ταξινομείται κατά αυτόν τον χρόνο. Ο ταξινομημένος πίνακας είναι-
Ψευδοκώδικας
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
Πρόγραμμα ταξινόμησης κελύφους σε 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
Ακολουθούν σημαντικές εφαρμογές του Shell Sort:
- Η ταξινόμηση κελύφους χρησιμοποιείται στο Πυρήνα του Linux επειδή δεν χρησιμοποιεί στοίβα κλήσεων.
- Η βιβλιοθήκη uClibc χρησιμοποιεί ταξινόμηση Shell.
- Ο συμπιεστής bzip2 χρησιμοποιεί ταξινόμηση Shell για να σταματήσει την υπέρβαση της αναδρομής.
Πλεονεκτήματα και μειονεκτήματα του Shell Sort
| Πλεονεκτήματα | Μειονεκτήματα |
|---|---|
| Δεν απαιτείται κλήση στοίβας. | Δεν είναι αποτελεσματικό για τεράστια μεγέθη συστοιχιών. |
| Εύκολη υλοποίηση. | Ανεπαρκές για ευρέως διαδεδομένα στοιχεία. |
| Αποτελεσματικό για στοιχεία με μικρότερη απόσταση. |
Ανάλυση πολυπλοκότητας ταξινόμησης κελύφους
Χρονική πολυπλοκότητα της ταξινόμησης κελύφους
Η χρονική πολυπλοκότητα του αλγόριθμου ταξινόμησης φλοιού είναι O(n^2). Το σκεπτικό έχει ως εξής:
Για το καλύτερο σενάριο, ο συνολικός αριθμός δοκιμών για όλα τα διαστήματα όταν ο πίνακας ήταν προηγουμένως διατεταγμένος ίσος με log n. Έτσι η πολυπλοκότητα θα ήταν O(n*log n).
Για το χειρότερο σενάριο, ας θεωρήσουμε ότι ο πίνακας αποτελείται κατά τέτοιο τρόπο ώστε τα στοιχεία να απαιτούν τον μεγαλύτερο αριθμό συγκρίσεων. Τότε όλα τα στοιχεία δεν θα συγκριθούν και δεν θα αλλάξουν μέχρι την τελευταία επανάληψη. Επομένως, οι συνολικές συγκρίσεις που απαιτούνται για την τελική αύξηση είναι O(n^2).
Συμπερασματικά, οι χρονικές πολυπλοκότητες θα ήταν
- πολυπλοκότητα υπόθεσης καλυτερα: O(n*log n)
- Μέση πολυπλοκότητα υπόθεσης: O(n*log n)
- Πολυπλοκότητα χειρότερης περίπτωσης: O(n^2)
Η πολυπλοκότητα του χρόνου εκτέλεσης της ταξινόμησης κελύφους εξαρτάται σε μεγάλο βαθμό από τις ακολουθίες αύξησης του χάσματος που χρησιμοποιούνται. Ωστόσο, η καλύτερη ακολουθία αύξησης για ταξινόμηση κελύφους είναι ακόμα άγνωστη.
Πολυπλοκότητα χώρου ταξινόμησης κελύφους
Σε αυτό το είδος σύγκρισης, δεν χρειαζόμαστε επιπλέον βοηθητικό χώρο. Έτσι, η χωρική πολυπλοκότητα αυτού του είδους αλγορίθμου είναι O(1).
