Αυτό το ιστολόγιο βασίζεται στην προσέγγιση διαίρεσης και κατάκτησης. Το Merge Sort είναι ένας αλγόριθμος 'διαίρεση και κατάκτηση' όπου το πρόβλημα χωρίζεται σε υποπροβλήματα και στη συνέχεια συγχωνεύεται για να κατακτήσει τη λύση. Αυτό το ιστολόγιο στο Merge Sort in θα σας καθοδηγήσει λεπτομερώς στα παρακάτω θέματα -
- Τι είναι το Merge Sort στο Python;
- Η προσέγγιση Divide and Conquer
- Εφαρμογή ταξινόμησης συγχώνευσης στο Python
- Διάγραμμα ροής για την εφαρμογή του Merge Sort
- Πλεονεκτήματα και χρήση
Τι είναι το Merge Sort στο Python;
Το Merge Sort βασίζεται στον αλγόριθμο διαίρεσης και κατάκτησης όπου ο πίνακας εισόδου χωρίζεται σε δύο μισά, στη συνέχεια ταξινομούνται ξεχωριστά και συγχωνεύονται ξανά για να φτάσουν στη λύση. Η συνάρτηση συγχώνευσης () χρησιμοποιείται για τη συγχώνευση της ταξινομημένης .
Η προσέγγιση Divide and Conquer
- Ο πίνακας χωρίζεται στο μισό και η διαδικασία επαναλαμβάνεται με κάθε μισό έως ότου κάθε μισό έχει μέγεθος 1 ή 0.
- Ο πίνακας του μεγέθους 1 ταξινομείται ασήμαντα.
- Τώρα οι δύο ταξινομημένες συστοιχίες συνδυάζονται σε έναν μεγάλο πίνακα. Και αυτό συνεχίζεται μέχρι να συνδυαστούν όλα τα στοιχεία και να ταξινομηθεί ο πίνακας.
Ακολουθεί μια απεικόνιση της ταξινόμησης συγχώνευσης για να καθαρίσετε την εικόνα για εσάς
Σειρά εισόδου = [3,1,4,1,5,9,2,6,5,4]
Τώρα, ας προχωρήσουμε στην εφαρμογή.
typecast double to int java
Εφαρμογή ταξινόμησης συγχώνευσης στο Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (righthalf) i = j = k = 0 ενώ i Παραγωγή:
$ python main.py
(«Διαχωρισμός», [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(«Διαχωρισμός», [3, 1, 4, 1, 5])
(«Διαχωρισμός», [3, 1])
(«Διαχωρισμός», [3])
(«Συγχώνευση», [3])
(«Διαχωρισμός», [1])
(«Συγχώνευση», [1])
(«Συγχώνευση», [1, 3])
(«Διαχωρισμός», [4, 1, 5])
(«Διαχωρισμός», [4])
(«Συγχώνευση», [4])
(«Διαχωρισμός», [1, 5])
(«Διαχωρισμός», [1])
(«Συγχώνευση», [1])
(«Διαχωρισμός», [5])
(«Συγχώνευση», [5])
(«Συγχώνευση», [1, 5])
(«Συγχώνευση», [1, 4, 5])
(«Συγχώνευση», [1, 1, 3, 4, 5])
(«Διαχωρισμός», [9, 2, 6, 5, 4])
(«Διαχωρισμός», [9, 2])
(«Διαχωρισμός», [9])
(«Συγχώνευση», [9])
(«Διαχωρισμός», [2])
(«Συγχώνευση», [2])
(«Συγχώνευση», [2, 9])
(«Διαχωρισμός», [6, 5, 4])
(«Διαχωρισμός», [6])
(«Συγχώνευση», [6])
(«Διαχωρισμός», [5, 4])
(«Διαχωρισμός», [5])
(«Συγχώνευση», [5])
(«Διαχωρισμός», [4])
(«Συγχώνευση», [4])
(«Συγχώνευση», [4, 5])
(«Συγχώνευση», [4, 5, 6])
(«Συγχώνευση», [2, 4, 5, 6, 9])
(«Συγχώνευση», [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
μετασχηματισμούς στην πληροφορική με παράδειγμα
Διάγραμμα ροής για την εφαρμογή του Merge Sort
Πλεονεκτήματα και χρήση του Merge Sort
Οι περισσότεροι από τους άλλους αλγόριθμους έχουν κακή απόδοση με διαδοχικές δομές δεδομένων, όπως αρχεία και συνδεδεμένες λίστες. Σε αυτές τις δομές η πρόσβαση σε ένα τυχαίο στοιχείο απαιτεί γραμμικό χρόνο, όχι κανονικό σταθερό χρόνο. Και η φύση του είδους συγχώνευσης το καθιστά εύκολο και γρήγορο για τέτοιες δομές δεδομένων.Ένα από τα καλύτερα χαρακτηριστικά του είδους συγχώνευσης είναι ο χαμηλός αριθμός συγκρίσεων. Κάνει O (n * log (n)) αριθμός συγκρίσεων, αλλά ο σταθερός παράγοντας είναι καλός σε σύγκριση με το quicksort, γεγονός που το καθιστά χρήσιμο όταν η λειτουργία σύγκρισης είναι αργή λειτουργία.Επίσης, η προσέγγιση διαίρεσης και κατάκτησης της συγχώνευσης διευκολύνει την παράλληλη επεξεργασία.
Με αυτό, φτάνουμε στο τέλος αυτού του ιστολογίου με θέμα «Πώς να εφαρμόσετε το Merge Sort στο Python». Ελπίζω το περιεχόμενο να προσθέσει κάποια αξία στις γνώσεις σας στο Python. Για να μάθετε σε βάθος την Python μαζί με τις διάφορες εφαρμογές της, μπορείτε να εγγραφείτε ζωντανά με υποστήριξη 24/7 και πρόσβαση σε όλη τη διάρκεια ζωής.