Ταξινόμηση κελύφους

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η ταξινόμηση κελύφους. Επίσης, θα βρείτε λειτουργικά παραδείγματα ταξινόμησης κελύφους σε C, C ++, Java και Python.

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

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

Μερικές από τις βέλτιστες ακολουθίες που χρησιμοποιούνται είναι:

• Η αρχική ακολουθία της Shell: N/2 , N/4 ,… , 1
• Αυξήσεις του Knuth: 1, 4, 13,… , (3k - 1) / 2
• Οι αυξήσεις του Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• Οι αυξήσεις του Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Αύξηση Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65,…
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Πώς λειτουργεί το Shell Sort;

1. Ας υποθέσουμε, πρέπει να ταξινομήσουμε τον ακόλουθο πίνακα. Αρχικός πίνακας
2. Χρησιμοποιούμε την αρχική ακολουθία του κελύφους (N/2, N/4,… 1) ως διαστήματα στον αλγόριθμό μας.
   Στον πρώτο βρόχο, εάν το μέγεθος του πίνακα είναι N = 8τότε, τα στοιχεία που βρίσκονται στο διάστημα του N/2 = 4συγκρίνονται και ανταλλάσσονται εάν δεν είναι σωστά.
   1. Το 0ο στοιχείο συγκρίνεται με το 4ο στοιχείο.
   2. Εάν το 0ο στοιχείο είναι μεγαλύτερο από το 4ο τότε, το 4ο στοιχείο αποθηκεύεται πρώτα σε tempμεταβλητή και το 0thστοιχείο (δηλ. Μεγαλύτερο στοιχείο) αποθηκεύεται στη 4thθέση και το στοιχείο που tempείναι αποθηκευμένο αποθηκεύεται στη 0thθέση. Αναδιάταξη των στοιχείων σε διάστημα n / 2
      Αυτή η διαδικασία συνεχίζεται για όλα τα υπόλοιπα στοιχεία. Αναδιάταξη όλων των στοιχείων σε διάστημα n / 2
3. Στο δεύτερο βρόχο, N/4 = 8/4 = 2λαμβάνεται ένα διάστημα και πάλι ταξινομούνται τα στοιχεία που βρίσκονται σε αυτά τα διαστήματα. Αναδιάταξη των στοιχείων σε διάστημα n / 4
   Μπορεί να μπερδευτείτε σε αυτό το σημείο. Συγκρίνονται όλα τα στοιχεία του πίνακα που βρίσκονται στο τρέχον διάστημα.
   Συγκρίνονται τα στοιχεία στο 4ο και η 2ndθέση. Τα στοιχεία στο 2ο και τη 0thθέση συγκρίνονται επίσης. Συγκρίνονται όλα τα στοιχεία του πίνακα που βρίσκονται στο τρέχον διάστημα.
4. Η ίδια διαδικασία συνεχίζεται για τα υπόλοιπα στοιχεία. Αναδιάταξη όλων των στοιχείων σε διάστημα n / 4
5. Τέλος, όταν το διάστημα είναι N/8 = 8/8 =1τότε τα στοιχεία του πίνακα που βρίσκονται στο διάστημα 1 ταξινομούνται. Ο πίνακας έχει πλέον ταξινομηθεί πλήρως. Αναδιάταξη των στοιχείων σε διάστημα n / 8

Αλγόριθμος Shell Sort

 shellSort (πίνακας, μέγεθος) για διάστημα i <- size / 2n έως 1 για κάθε διάστημα "i" σε πίνακα ταξινομήστε όλα τα στοιχεία στο διάστημα "i" end shellSort

Παραδείγματα Python, Java και C / C ++

Python Java C C ++

# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)

// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 

// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 

// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); ) 

Περίπλοκο

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

Χρόνος πολυπλοκότητας

• Χειρότερη περίπτωση πολυπλοκότητας : μικρότερη ή ίση με την χειρότερη περίπλοκη περίπτωση για είδος κελύφους είναι πάντα μικρότερη ή ίση με . Σύμφωνα με Poonen θεώρημα, πολυπλοκότητα χειρότερης περίπτωσης για το κέλυφος του είδους είναι ή ή ή κάτι στο μεταξύ.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Best Case Complexity: O(n*log n)
  When the array is already sorted, the total number of comparisons for each interval (or increment) is equal to the size of the array.
• Average Case Complexity: O(n*log n)
  It is around O(n1.25).

The complexity depends on the interval chosen. The above complexities differ for different increment sequences chosen. Best increment sequence is unknown.

Space Complexity:

The space complexity for shell sort is O(1).

Shell Sort Applications

Shell sort is used when:

• calling a stack is overhead. uClibc library uses this sort.
• recursion exceeds a limit. bzip2 compressor uses it.
• Το είδος εισαγωγής δεν αποδίδει καλά όταν τα στοιχεία κλεισίματος βρίσκονται σε απόσταση. Το είδος κελύφους βοηθά στη μείωση της απόστασης μεταξύ των στενών στοιχείων. Έτσι, θα υπάρχει λιγότερος αριθμός ανταλλαγών που θα εκτελεστούν.