Σε αυτό το σεμινάριο, θα μάθετε για το είδος συγχώνευσης. Επίσης, θα βρείτε λειτουργικά παραδείγματα συγχώνευσης τύπου C, C ++, Java και Python.
Το Merge Sort είναι ένας από τους πιο δημοφιλείς αλγόριθμους ταξινόμησης που βασίζεται στην αρχή του Divide and Conquer Algorithm.
Εδώ, ένα πρόβλημα χωρίζεται σε πολλά δευτερεύοντα προβλήματα. Κάθε υπο-πρόβλημα επιλύεται ξεχωριστά. Τέλος, τα υπο-προβλήματα συνδυάζονται για να σχηματίσουν την τελική λύση.
Παράδειγμα συγχώνευσης ταξινόμησης
Διαίρεση και κατάκτηση στρατηγικής
Χρησιμοποιώντας την τεχνική Divide and Conquer , διαιρούμε ένα πρόβλημα σε υποπροβλήματα. Όταν η λύση σε κάθε υποπρόβλημα είναι έτοιμη, «συνδυάζουμε» τα αποτελέσματα από τα υποπροβλήματα για να λύσουμε το κύριο πρόβλημα.
Ας υποθέσουμε ότι έπρεπε να ταξινομήσουμε έναν πίνακα Α. Ένα υποπρόβλημα θα ήταν να ταξινομήσουμε μια υποενότητα αυτού του πίνακα ξεκινώντας από το ευρετήριο p και τελειώνοντας στο ευρετήριο r, που υποδηλώνεται ως Α (p… r).
Διαίρεση
Εάν το q είναι το μισό σημείο μεταξύ p και r, τότε μπορούμε να χωρίσουμε την υποπεριοχή A (p… r) σε δύο συστοιχίες A (p… q) και A (q + 1, r).
Conquer
Στο βήμα της κατάκτησης, προσπαθούμε να ταξινομήσουμε και τις δύο υποζώνες A (p… q) και A (q + 1, r). Εάν δεν έχουμε φτάσει ακόμα στη βασική θήκη, διαιρούμε και πάλι και τα δύο αυτά subarrays και προσπαθούμε να τα ταξινομήσουμε.
Συνδυασμός
Όταν το βήμα της κατάκτησης φτάσει στο βήμα βάσης και έχουμε δύο ταξινομημένες υποζώνες A (p… q) και A (q + 1, r) για τον πίνακα A (p… r), συνδυάζουμε τα αποτελέσματα δημιουργώντας μια ταξινομημένη σειρά A ( p… r) από δύο ταξινομημένες υποζώνες A (p… q) και A (q + 1, r).
Ο αλγόριθμος MergeSort
Η συνάρτηση MergeSort χωρίζει επανειλημμένα τον πίνακα σε δύο μισά έως ότου φτάσουμε σε ένα στάδιο όπου προσπαθούμε να εκτελέσουμε το MergeSort σε μια υποπεριοχή μεγέθους 1, δηλαδή p == r.
Μετά από αυτό, η λειτουργία συγχώνευσης μπαίνει στο παιχνίδι και συνδυάζει τις ταξινομημένες συστοιχίες σε μεγαλύτερες σειρές έως ότου συγχωνευθεί ολόκληρος ο πίνακας.
MergeSort (A, p, r): if p> r return q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) συγχώνευση (A, p, q, r )
Για να ταξινομήσετε μια ολόκληρη σειρά, θα πρέπει να καλέσετε MergeSort(A, 0, length(A)-1).
Όπως φαίνεται στην παρακάτω εικόνα, ο αλγόριθμος ταξινόμησης συγχώνευσης διαιρεί αναδρομικά τον πίνακα σε μισά έως ότου φτάσουμε στη βασική περίπτωση του πίνακα με 1 στοιχείο. Μετά από αυτό, η συνάρτηση συγχώνευσης παίρνει τις ταξινομημένες υπο-σειρές και τις συγχωνεύει για να ταξινομήσει σταδιακά ολόκληρο τον πίνακα.
Συγχώνευση ταξινόμησης σε δράση
Η συγχώνευση Βήμα της συγχώνευσης Ταξινόμηση
Κάθε αναδρομικός αλγόριθμος εξαρτάται από μια βασική περίπτωση και από τη δυνατότητα συνδυασμού των αποτελεσμάτων από τις βασικές περιπτώσεις. Το είδος συγχώνευσης δεν είναι διαφορετικό. Το πιο σημαντικό μέρος του αλγορίθμου ταξινόμησης συγχώνευσης είναι, το μαντέψατε, βήμα συγχώνευσης.
Το βήμα συγχώνευσης είναι η λύση στο απλό πρόβλημα της συγχώνευσης δύο ταξινομημένων λιστών (πίνακες) για τη δημιουργία μιας μεγάλης ταξινομημένης λίστας (πίνακας).
Ο αλγόριθμος διατηρεί τρεις δείκτες, έναν για καθεμία από τις δύο συστοιχίες και έναν για τη διατήρηση του τρέχοντος δείκτη του τελικού ταξινομημένου πίνακα.
Έχουμε φτάσει στο τέλος μιας από τις συστοιχίες; Όχι: Συγκρίνετε τα τρέχοντα στοιχεία και των δύο συστοιχιών Αντιγράψτε μικρότερο στοιχείο σε ταξινομημένη συστοιχία Μετακινήστε το δείκτη του στοιχείου που περιέχει μικρότερο στοιχείο Ναι: Αντιγράψτε όλα τα υπόλοιπα στοιχεία του μη κενού πίνακα
Συγχώνευση βήμα
Σύνταξη του κώδικα για τον αλγόριθμο συγχώνευσης
Μια αξιοσημείωτη διαφορά μεταξύ του βήματος συγχώνευσης που περιγράψαμε παραπάνω και αυτού που χρησιμοποιούμε για ταξινόμηση συγχώνευσης είναι ότι εκτελούμε τη συνάρτηση συγχώνευσης μόνο σε διαδοχικές υπο-σειρές.
Γι 'αυτό χρειαζόμαστε μόνο τον πίνακα, την πρώτη θέση, τον τελευταίο δείκτη της πρώτης υποομάδας (μπορούμε να υπολογίσουμε τον πρώτο δείκτη της δεύτερης υποομάδας) και τον τελευταίο δείκτη της δεύτερης υποομάδας.
Ο στόχος μας είναι να συγχωνεύσουμε δύο υποζώνες A (p… q) και A (q + 1… r) για να δημιουργήσουμε μια ταξινομημένη συστοιχία A (p… r). Έτσι, οι είσοδοι στη συνάρτηση είναι A, p, q και r
Η συνάρτηση συγχώνευσης λειτουργεί ως εξής:
- Δημιουργήστε αντίγραφα των subarrays
L ← A(p… q)και M ← A (q + 1… r). - Δημιουργήστε τρεις δείκτες i, j και k
- διατηρώ τον τρέχοντα δείκτη του L, ξεκινώντας από το 1
- j διατηρεί τον τρέχοντα δείκτη του M, ξεκινώντας από το 1
- Το k διατηρεί τον τρέχοντα δείκτη του A (p… q), ξεκινώντας από το p.
- Μέχρι να φτάσουμε στο τέλος είτε L είτε M, επιλέξτε το μεγαλύτερο μεταξύ των στοιχείων από L και M και τοποθετήστε τα στη σωστή θέση στο A (p… q)
- Όταν εξαντλήσουμε στοιχεία είτε στο L είτε στο M, πάρτε τα υπόλοιπα στοιχεία και τοποθετήστε το στο A (p… q)
Στον κώδικα, θα μοιάζει με:
// Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Συγχώνευση () Λειτουργία που εξηγείται βήμα προς βήμα
Πολλά συμβαίνουν σε αυτήν τη λειτουργία, οπότε ας πάρουμε ένα παράδειγμα για να δούμε πώς θα λειτουργούσε.
Ως συνήθως, μια εικόνα μιλά χίλιες λέξεις.
Συγχώνευση δύο διαδοχικών υποομάδων συστοιχίας
Ο πίνακας A (0… 5) περιέχει δύο ταξινομημένες υποζώνες A (0… 3) και A (4… 5). Ας δούμε πώς η συνάρτηση συγχώνευσης θα συγχωνεύσει τις δύο συστοιχίες.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
Βήμα 1: Δημιουργήστε διπλά αντίγραφα υπο-συστοιχιών προς ταξινόμηση
// Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9) 
Δημιουργήστε αντίγραφα subarrays για συγχώνευση
Βήμα 2: Διατηρήστε τον τρέχοντα δείκτη υπο-συστοιχιών και κύριου πίνακα
int i, j, k; i = 0; j = 0; k = p; 
Διατηρήστε δείκτες αντιγράφων δευτερεύοντος πίνακα και κύριου πίνακα
Βήμα 3: Μέχρι να φτάσουμε στο τέλος είτε L ή M, επιλέξτε μεγαλύτερο μεταξύ των στοιχείων L και M και τοποθετήστε τα στη σωστή θέση στο A (p… r)
while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) 
Συγκρίνοντας μεμονωμένα στοιχεία ταξινομημένων subarrays μέχρι να φτάσουμε στο τέλος ενός
Βήμα 4: Όταν εξαντλήσουμε τα στοιχεία είτε στο L είτε στο M, πάρτε τα υπόλοιπα στοιχεία και τοποθετήστε το στο A (p… r)
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
Αντιγράψτε τα υπόλοιπα στοιχεία από τον πρώτο πίνακα στην κύρια δευτερεύουσα σειρά
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
Αντιγράψτε τα υπόλοιπα στοιχεία της δεύτερης συστοιχίας στην κύρια δευτερεύουσα σειρά
Αυτό το βήμα θα ήταν απαραίτητο εάν το μέγεθος του Μ ήταν μεγαλύτερο από το L.
Στο τέλος της συνάρτησης συγχώνευσης, η υποπεριοχή Α (p… r) ταξινομείται.
Παραδείγματα Python, Java και C / C ++
Python Java C C ++ # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array)
// Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
// Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
// Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )
Συγχώνευση πολυπλοκότητας ταξινόμησης
Χρόνος πολυπλοκότητας
Καλύτερη πολυπλοκότητα περιπτώσεων: O (n * log n)
Χειρότερη περίπτωση πολυπλοκότητας: O (n * log n)
Μέση πολυπλοκότητα περίπτωσης: O (n * log n)
Διαστημική πολυπλοκότητα
Η πολυπλοκότητα του διαστήματος συγχώνευσης είναι O (n).
Εφαρμογές συγχώνευσης ταξινόμησης
- Πρόβλημα μέτρησης αντιστροφής
- Εξωτερική ταξινόμηση
- Εφαρμογές ηλεκτρονικού εμπορίου
