Όλοι γνωρίζουν πολύ καλά ότι από την κατηγορία των ειδών ανταλλαγής, τα περισσότερα γρήγορη μέθοδοςείναι το λεγόμενο γρήγορη ταξινόμηση. Γράφονται διατριβές σχετικά με αυτό, πολλά άρθρα για το Habré είναι αφιερωμένα σε αυτό, σύνθετοι υβριδικοί αλγόριθμοι επινοούνται βάσει του. Αλλά σήμερα δεν μιλάμε για γρήγορη ταξινόμηση, αλλά για μια άλλη μέθοδο ανταλλαγής - την παλιά καλή είδος φούσκαςκαι τις βελτιώσεις, τις τροποποιήσεις, τις μεταλλάξεις και τις παραλλαγές του.

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

εικόνα: φυσαλίδες

Σήμερα θα μιλήσουμε για τα πιο απλά διαλογή ανταλλαγών.

Αν ενδιαφέρεται κάποιος, θα πω ότι υπάρχουν και άλλες τάξεις - επιλογή ταξινόμησης, ταξινόμηση εισαγωγής, συγχώνευση ταξινόμησης, κατανομή ταξινόμησης, υβριδικά είδηκαι παράλληλων ειδών. Παρεμπιπτόντως, υπάρχουν εσωτερικές διαλογές. Αυτοί είναι διάφοροι ψεύτικοι, βασικά απραγματοποίητοι, κωμικοί και άλλοι ψευδοαλγόριθμοι, για τους οποίους θα γράψω κάπως μερικά άρθρα στο IT-humor hub.

Αλλά αυτό δεν έχει καμία σχέση με τη σημερινή διάλεξη, τώρα μας ενδιαφέρουν μόνο τα απλά είδη ανταλλαγής. Υπάρχουν επίσης αρκετά είδη ανταλλαγής από μόνα τους (ξέρω πάνω από δώδεκα), οπότε θα εξετάσουμε το λεγόμενο είδος φούσκαςκαι κάποια άλλα που σχετίζονται στενά με αυτό.

Θα σας προειδοποιήσω εκ των προτέρων ότι σχεδόν όλες οι παραπάνω μέθοδοι είναι πολύ αργές και δεν θα υπάρξει σε βάθος ανάλυση της χρονικής πολυπλοκότητάς τους. Κάποιοι είναι πιο γρήγοροι, άλλοι πιο αργοί, αλλά, χοντρικά, μπορούμε να το πούμε αυτό κατά μέσο όρο Ο(ν 2). Επίσης, δεν βλέπω λόγο να γεμίζω το άρθρο με υλοποιήσεις σε οποιαδήποτε γλώσσα προγραμματισμού. Όσοι ενδιαφέρονται μπορούν εύκολα να βρουν παραδείγματα κώδικα στη Rosetta, στη Wikipedia ή κάπου αλλού.

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

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

Ανόητο είδος

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

«Άρα κάθε ανόητος ξέρει να ταξινομεί» - θα πεις και θα έχεις απόλυτο δίκιο. Γι' αυτό η διαλογή ονομάζεται "ηλίθια". Σε αυτή τη διάλεξη, θα βελτιώνουμε και θα τροποποιούμε συνεχώς με αυτόν τον τρόπο. Τώρα έχει πολυπλοκότητα χρόνου Ο(ν 3), έχοντας κάνει μία διόρθωση, θα φέρουμε ήδη στο Ο(ν 2), μετά επιταχύνουμε λίγο περισσότερο, μετά λίγο περισσότερο, και στο τέλος έχουμε Ο(nκούτσουρο n) - και δεν θα είναι καθόλου "Quick Sort"!

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

Στην προκειμένη περίπτωση δεν έχουμε μπροστά μας τίποτα περισσότερο από το γνωστό ...

είδος φούσκας

Ή ταξινόμηση με απλές ανταλλαγές. Ένα αθάνατο κλασικό του είδους. Η αρχή της δράσης είναι απλή: περνάμε γύρω από τη συστοιχία από την αρχή μέχρι το τέλος, ενώ ταυτόχρονα ανταλλάσσουμε μη ταξινομημένα γειτονικά στοιχεία. Ως αποτέλεσμα του πρώτου περάσματος, το μέγιστο στοιχείο θα "ανέβει" στην τελευταία θέση. Τώρα πάλι παρακάμπτουμε το μη ταξινομημένο τμήμα του πίνακα (από το πρώτο στοιχείο στο προτελευταίο) και αλλάζουμε τους μη ταξινομημένους γείτονες στην πορεία. Το δεύτερο μεγαλύτερο στοιχείο θα βρίσκεται στην προτελευταία θέση. Συνεχίζοντας στο ίδιο πνεύμα, θα παρακάμψουμε το διαρκώς μειούμενο μη ταξινομημένο τμήμα του πίνακα, ωθώντας τα μέγιστα που βρέθηκαν μέχρι το τέλος.

Αν όχι μόνο σπρώξουμε τα ψηλά μέχρι το τέλος, αλλά και μετακινήσουμε τα χαμηλά στην αρχή, τότε παίρνουμε ...

παλινδρομική ταξινόμιση

Αυτή είναι ανακάτεμα ταξινόμηση, αυτή είναι διαλογή κοκτέιλ. Η διαδικασία ξεκινά σαν σε μια «φούσκα»: πιέζουμε το μέγιστο στις ίδιες τις αυλές. Μετά από αυτό, στρίβουμε γύρω στα 180 0 και πηγαίνουμε προς την αντίθετη κατεύθυνση, ενώ ήδη κυλάμε στην αρχή όχι ένα μέγιστο, αλλά ένα ελάχιστο. Έχοντας ταξινομήσει το πρώτο και το τελευταίο στοιχείο στον πίνακα, κάνουμε ξανά τούμπα. Έχοντας γυρίσει πολλές φορές μπρος-πίσω, στο τέλος τελειώνουμε τη διαδικασία, όντας στη μέση της λίστας.

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

Όπως μπορείτε να δείτε, εάν προσεγγίσετε δημιουργικά τη διαδικασία επανάληψης, τότε η ώθηση βαριών (ελαφρών) στοιχείων στα άκρα του πίνακα είναι πιο γρήγορη. Ως εκ τούτου, οι τεχνίτες πρότειναν έναν άλλο μη τυποποιημένο «οδικό χάρτη» για να παρακάμψει τη λίστα.

Ζυγός-περιττός τύπος

Αυτή τη φορά δεν θα τρέξουμε γύρω από τον πίνακα μπρος-πίσω, αλλά και πάλι θα επιστρέψουμε στην ιδέα μιας συστηματικής παράκαμψης από αριστερά προς τα δεξιά, αλλά θα κάνουμε μόνο ένα ευρύτερο βήμα. Στο πρώτο πέρασμα, στοιχεία με περιττό κλειδί συγκρίνονται με γείτονες βάσει ζυγών θέσεων (το 1ο συγκρίνεται με το 2ο, μετά το 3ο με το 4ο, το 5ο με το 6ο κ.ο.κ.). Στη συνέχεια, αντίστροφα - τα "ζυγά" στοιχεία συγκρίνονται / αλλάζουν με "μονά". Μετά πάλι «μονός-ζυγός», μετά πάλι «ζυγός-μονός». Η διαδικασία σταματά όταν, μετά από δύο διαδοχικά περάσματα από τον πίνακα («μονός-άρτιος» και «ζυγός-μονός»), δεν έχει πραγματοποιηθεί ανταλλαγή. Λοιπόν, τακτοποιήθηκε.

Στη συνηθισμένη «φούσκα» κατά τη διάρκεια κάθε πέρασμα, συμπιέζουμε συστηματικά το τρέχον μέγιστο μέχρι το τέλος του πίνακα. Αν παρακάμψουμε τους άρτιους και τους περιττούς δείκτες, τότε όλα τα περισσότερο ή λιγότερο μεγάλα στοιχεία του πίνακα ωθούνται ταυτόχρονα προς τα δεξιά κατά μία θέση σε μία διαδρομή. Έτσι γίνεται πιο γρήγορα.

Ας αναλύσουμε το τελευταίο ανακαίνιση* Για Ταξινόμηση λαμπτήρων** - Ταξινόμηση κατά χτένα***. Αυτή η μέθοδος οργανώνεται πολύ γρήγορα, Ο(ν 2) είναι η χειρότερη πολυπλοκότητά του. Κατά μέσο όρο διαχρονικά, έχουμε Ο(nκούτσουρο n), και το καλύτερο ακόμη, μην το πιστεύετε Ο(n). Δηλαδή, ένας πολύ άξιος ανταγωνιστής κάθε "γρήγορης ταξινόμησης" και αυτό, προσέξτε, χωρίς τη χρήση αναδρομής. Ωστόσο, υποσχέθηκα ότι δεν θα εμβαθύνουμε σε ταχύτητες πλεύσης σήμερα, οπότε θα σιωπήσω και θα πάω κατευθείαν στον αλγόριθμο.

Για όλα φταίνε οι χελώνες

Μια μικρή ιστορία. Το 1980, ο Włodzimierz Dobosiewicz εξήγησε γιατί η ταξινόμηση με φυσαλίδες και τα παράγωγά της είναι τόσο αργά. Είναι όλα για τις χελώνες. Οι «χελώνες» είναι μικροαντικείμενα που βρίσκονται στο τέλος της λίστας. Όπως ίσως έχετε παρατηρήσει, τα είδη φυσαλίδων επικεντρώνονται στα "κουνέλια" (δεν πρέπει να συγχέονται με τα "κουνέλια" του Babushkin) - μεγάλα στοιχεία σε αξία στην αρχή της λίστας. Προχωρούν πολύ γρήγορα στη γραμμή του τερματισμού. Αλλά τα αργά ερπετά σέρνονται στην αρχή απρόθυμα. Μπορείτε να προσαρμόσετε το "tortillo" χρησιμοποιώντας χτένες.

εικόνα: ένοχη χελώνα

Ταξινόμηση με χτένα

Στο "bubble", "shaker" και "jout-odd", κατά την επανάληψη σε έναν πίνακα, συγκρίνονται τα γειτονικά στοιχεία. Η κύρια ιδέα της "χτένας" είναι να πάρει αρχικά αρκετό μεγάλη απόστασημεταξύ των συγκριτικών στοιχείων και καθώς ταξινομείται ο πίνακας, περιορίστε αυτήν την απόσταση στο ελάχιστο. Έτσι, εμείς, όπως ήταν, χτενίζουμε τη συστοιχία, εξομαλύνοντάς την σταδιακά σε όλο και πιο ακριβείς κλωστές.

Είναι καλύτερο να λαμβάνεται το αρχικό κενό μεταξύ των συγκριτικών στοιχείων όχι ούτως ή άλλως, αλλά λαμβάνοντας υπόψη μια ειδική τιμή που ονομάζεται μειωτικός παράγοντας, η βέλτιστη τιμή του οποίου είναι περίπου 1,247. Πρώτον, η απόσταση μεταξύ των στοιχείων είναι ίση με το μέγεθος του πίνακα διαιρούμενο με συντελεστής μείωσης(το αποτέλεσμα στρογγυλοποιείται φυσικά στον πλησιέστερο ακέραιο). Στη συνέχεια, αφού περάσουμε από τον πίνακα με αυτό το βήμα, διαιρούμε ξανά το βήμα με συντελεστής μείωσηςκαι περάστε ξανά από τη λίστα. Αυτό συνεχίζεται έως ότου η διαφορά του δείκτη φτάσει το ένα. Σε αυτήν την περίπτωση, ο πίνακας ταξινομείται εκ νέου με μια κανονική φυσαλίδα.

Η βέλτιστη τιμή έχει καθοριστεί πειραματικά και θεωρητικά συντελεστής μείωσης:

Όταν εφευρέθηκε αυτή η μέθοδος, λίγοι άνθρωποι της έδωσαν προσοχή στις αρχές της δεκαετίας του '70 και του '80. Μια δεκαετία αργότερα, όταν ο προγραμματισμός έπαψε να είναι η παρτίδα των επιστημόνων και των μηχανικών της IBM και αποκτούσε ήδη μαζικό χαρακτήρα, η μέθοδος ανακαλύφθηκε εκ νέου, ερευνήθηκε και διαδόθηκε το 1991 από τους Stephen Lacey και Richard Box.

Αυτό είναι στην πραγματικότητα το μόνο που ήθελα να σας πω για την ταξινόμηση με φυσαλίδες και άλλα παρόμοια.

- Σημειώσεις

* συντομευμένο ( Ουκρανός) - βελτίωση
** Ταξινόμηση με λάμπα ( Ουκρανός) – Ταξινόμηση με φυσαλίδες
*** Ταξινόμηση κατά χτένα ( Ουκρανός) – Διαλογή με χτένα

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

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

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

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

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

Ταξινόμηση επιλογής

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

Κωδικός C++

void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i δεδομένα[k])( j = k; ) ) tmp = δεδομένα[i]; data[i] = δεδομένα[j]; δεδομένα[j] = tmp; ) )

Ταξινόμηση φυσαλίδων

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

Κωδικός C++

void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)(αν (δεδομένα[j]

Ταξινόμηση εισαγωγής

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

Σε κάθε πέρασμα, το μέγεθος της διατεταγμένης περιοχής αυξάνεται κατά 1 και το μέγεθος της μη ταξινομημένης περιοχής μειώνεται κατά 1.

Ο κύριος βρόχος εκτείνεται στην περιοχή από 1 έως N-1. Στην jη επανάληψη, το στοιχείο [i] εισάγεται στη σωστή θέση στην τακτοποιημένη περιοχή. Αυτό γίνεται μετατοπίζοντας όλα τα στοιχεία της διατεταγμένης περιοχής που είναι μεγαλύτερα από [i] μία θέση προς τα δεξιά. Το [i] παρεμβάλλεται στο διάστημα μεταξύ εκείνων των στοιχείων που είναι μικρότερα από [i] και εκείνων που είναι μεγαλύτερα από [i].

Κωδικός C++

void SortAlgo::insertionSort(int data, int lenD) ( int key = 0; int i = 0; for (int j = 1; j =0 && data[i]>key)( data = data[i]; i = i-1; data=key; ) ) )

Συγχώνευση ταξινόμησης

Κωδικός C++

void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i

Γρήγορη ταξινόμηση

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

Κωδικός C++

void SortAlgo::quickSort(int * δεδομένα, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; εάν (lenD>1) ( int * L = new int ; int * R = new int ; pivot = δεδομένα; ​​για (i=0;i

Γεια σε όλους!

Σήμερα θα αναλύσουμε την ταξινόμηση με τη μέθοδο «φούσκα». Αυτός ο αλγόριθμος περνάει συχνά σε σχολεία και πανεπιστήμια, επομένως θα χρησιμοποιήσουμε τη γλώσσα Pascal. Λοιπόν, τι είναι η ταξινόμηση; Ταξινόμηση είναι η σειρά των στοιχείων από το μικρότερο στο μεγαλύτερο (αύξουσα ταξινόμηση) ή από το μεγαλύτερο στο μικρότερο στοιχείο (φθίνουσα ταξινόμηση). Οι πίνακες συνήθως ταξινομούνται.

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

Πλεονεκτήματα:

• Ευκολία υλοποίησης του αλγορίθμου
• Ωραίο όνομα

Μειονεκτήματα:

• Μία από τις πιο αργές μεθόδους ταξινόμησης (Ο χρόνος εκτέλεσης εξαρτάται τετραγωνικά από το μήκος του πίνακα n 2)
• Σχεδόν ποτέ δεν χρησιμοποιείται στην πραγματική ζωή (χρησιμοποιείται κυρίως για εκπαιδευτικούς σκοπούς)

Ας υποθέσουμε ότι έχουμε έναν πίνακα: 3 1 4 2

Αλγόριθμος: Παίρνουμε ένα στοιχείο πίνακα, το συγκρίνουμε με το επόμενο, αν το στοιχείο μας είναι μεγαλύτερο από το επόμενο στοιχείο, τότε τα ανταλλάσσουμε. Αφού περάσουμε από ολόκληρο τον πίνακα, μπορούμε να είμαστε σίγουροι ότι το μέγιστο στοιχείο θα "σκάσει" - και θα είναι το τελευταίο. Έτσι, έχουμε ήδη ένα στοιχείο ακριβώς στη θέση του. Επειδή Πρέπει να τα βάλουμε όλα στη θέση τους, επομένως, πρέπει να επαναλάβουμε αυτή τη λειτουργία όσες φορές έχουμε στοιχεία πίνακα μείον 1. Το τελευταίο στοιχείο θα εμφανιστεί αυτόματα εάν τα υπόλοιπα βρίσκονται στη θέση τους.

Ας επιστρέψουμε στον πίνακα μας: 3 1 4 2
Παίρνουμε το πρώτο στοιχείο "3" και το συγκρίνουμε με το επόμενο "1". Επειδή "3" > "1" και μετά αλλάξτε:
1 3 4 2
Τώρα συγκρίνουμε το "3" και το "4", τα τρία δεν είναι περισσότερα από τέσσερα, οπότε δεν κάνουμε τίποτα. Στη συνέχεια, συγκρίνουμε το "4" και το "2". Τέσσερα είναι περισσότερα από δύο - επομένως ανταλλάσσουμε θέσεις: 1 3 2 4. Ο κύκλος τελείωσε. Άρα το μεγαλύτερο στοιχείο θα έπρεπε να είναι ήδη στη θέση του!! Βλέπουμε ότι αυτό έγινε. Όπου κι αν βρίσκεται το "4" (το μεγαλύτερο στοιχείο μας) - θα εξακολουθεί να είναι το τελευταίο μετά από κύκλους σε ολόκληρο τον πίνακα. Αναλογία - ακριβώς όπως μια φυσαλίδα αέρα επιπλέει στο νερό - έτσι και το στοιχείο μας επιπλέει σε μια διάταξη. Επομένως, ο αλγόριθμος ονομάζεται "Ταξινόμηση με φυσαλίδες". Για να τοποθετήσετε το επόμενο στοιχείο, είναι απαραίτητο να ξεκινήσετε ξανά τον κύκλο, αλλά το τελευταίο στοιχείο δεν μπορεί πλέον να ληφθεί υπόψη, επειδή βρίσκεται στη θέση του.

Συγκρίνουμε το "1" και το "3" - δεν αλλάζουμε τίποτα.
Συγκρίνετε "3" και "2" - Το τρία είναι περισσότερα από δύο, οπότε αλλάζουμε θέσεις. Αποδεικνύεται: 1 2 3 4. Ο δεύτερος κύκλος έχει τελειώσει. Έχουμε ήδη κάνει δύο κύκλους - πράγμα που σημαίνει ότι μπορούμε να πούμε με σιγουριά ότι έχουμε ήδη ταξινομήσει τα δύο τελευταία στοιχεία. Μένει να ταξινομήσουμε το τρίτο στοιχείο και το τέταρτο θα πέσει αυτόματα στη σωστή θέση. Για άλλη μια φορά, συγκρίνουμε το πρώτο στοιχείο και το δεύτερο - βλέπουμε ότι έχουμε ήδη τα πάντα στη θέση τους, πράγμα που σημαίνει ότι ο πίνακας μπορεί να θεωρηθεί ταξινομημένος σε αύξουσα σειρά στοιχείων.

Τώρα απομένει να προγραμματίσουμε αυτόν τον αλγόριθμο σε Pascal. const n = 4; (Ξεκινάμε μια σταθερά, θα είναι το μήκος του πίνακα) var i, j, k:integer; (Δύο μεταβλητές για ένθετο βρόχο, μία για εναλλαγή στοιχείων) m:πίνακας ακεραίων; (Δημιουργήστε έναν πίνακα) ξεκινήστε (Θα ζητήσουμε έναν πίνακα από το πληκτρολόγιο:) Writeln("Εισαγάγετε έναν πίνακα:"); για i:=1 έως n ξεκινάμε Writeln(i, "στοιχείο:"); readln(m[i]); τέλος; (Ο εξωτερικός βρόχος είναι υπεύθυνος για το γεγονός ότι πρέπει να επαναλάβουμε τον εσωτερικό βρόχο όσες φορές έχουμε στοιχεία πίνακα μείον 1.) γιατί το i:=1 έως το n-1 αρχίζει (Ο εσωτερικός βρόχος επαναλαμβάνεται ήδη πάνω από τα στοιχεία και συγκρίνει μεταξύ τους.) για j :=1 έως n-i αρχίζουν (Εάν το στοιχείο είναι μεγαλύτερο από το επόμενο, τότε αλλάξτε.) Αν m[j]>m τότε ξεκινήστε k:=m[j]; m[j]:=m; m:=k; τέλος; τέλος; τέλος; (Εκτύπωση αποτελέσματος:) για i:=1 έως n do Write(m[i], " "); τέλος.
Ιδού το αποτέλεσμα:

Και εδώ είναι το εκπαιδευτικό βίντεο

Όταν εργάζεστε με πίνακες δεδομένων, δεν είναι ασυνήθιστο να το κάνουν ταξινόμηση με αύξουσα ή φθίνουσα σειρά, δηλ. εξορθολογισμός. Αυτό σημαίνει ότι τα στοιχεία του ίδιου πίνακα πρέπει να είναι διατεταγμένα αυστηρά στη σειρά. Για παράδειγμα, στην περίπτωση ταξινόμησης με αύξουσα σειρά, το προηγούμενο στοιχείο πρέπει να είναι μικρότερο (ή ίσο) με το επόμενο στοιχείο.

Λύση

Υπάρχουν πολλές μέθοδοι ταξινόμησης. Μερικά από αυτά είναι πιο αποτελεσματικά, άλλα είναι πιο εύκολα κατανοητά. Αρκετά απλό για να καταλάβεις είναι η ταξινόμηση μέθοδος φούσκας, που λέγεται και απλή μέθοδος ανταλλαγής. Τι είναι και γιατί έχει ένα τόσο περίεργο όνομα: "μέθοδος φούσκας";

Όπως γνωρίζετε, ο αέρας είναι ελαφρύτερος από το νερό, επομένως οι φυσαλίδες αέρα επιπλέουν. Είναι απλώς μια αναλογία. Στην αύξουσα ταξινόμηση με φυσαλίδες, τα ελαφρύτερα (χαμηλότερης τιμής) στοιχεία «επιπλέουν» σταδιακά στην αρχή του πίνακα, ενώ τα βαρύτερα ένα-ένα βυθίζονται στο κάτω μέρος (στο τέλος του πίνακα).

Ο αλγόριθμος και τα χαρακτηριστικά αυτού του είδους είναι τα εξής:

1. Κατά το πρώτο πέρασμα μέσα από τον πίνακα, τα στοιχεία συγκρίνονται σε ζεύγη: το πρώτο με το δεύτερο, μετά το δεύτερο με το τρίτο, μετά το τρίτο με το τέταρτο και ούτω καθεξής. Εάν το προηγούμενο στοιχείο είναι μεγαλύτερο από το επόμενο, τότε ανταλλάσσονται.
2. Δεν είναι δύσκολο να μαντέψει κανείς ότι σταδιακά ο μεγαλύτερος αριθμός είναι ο τελευταίος. Ο υπόλοιπος πίνακας παραμένει αταξινόμητος, αν και παρατηρείται κάποια μετακίνηση στοιχείων χαμηλότερης τιμής στην αρχή του πίνακα.
3. Στο δεύτερο πέρασμα, δεν χρειάζεται να συγκρίνετε το τελευταίο στοιχείο με το προτελευταίο. Το τελευταίο στοιχείο είναι ήδη στη θέση του. Αυτό σημαίνει ότι ο αριθμός των συγκρίσεων θα είναι ένας λιγότερος.
4. Στο τρίτο πέρασμα, δεν χρειάζεται πλέον να συγκρίνουμε το προτελευταίο και το τρίτο στοιχείο από το τέλος. Επομένως, ο αριθμός των συγκρίσεων θα είναι δύο λιγότεροι από ό,τι στο πρώτο πέρασμα.
5. Εξάλλου, κατά την επανάληψη μέσω του πίνακα, όταν απομένουν μόνο δύο στοιχεία για σύγκριση, εκτελείται μόνο μία σύγκριση.
6. Μετά από αυτό, το πρώτο στοιχείο δεν έχει τίποτα να συγκριθεί και επομένως δεν χρειάζεται το τελευταίο πέρασμα μέσα από τον πίνακα. Με άλλα λόγια, ο αριθμός των διελεύσεων από τον πίνακα είναι m-1, όπου m είναι ο αριθμός των στοιχείων του πίνακα.
7. Ο αριθμός των συγκρίσεων σε κάθε πέρασμα είναι m-i, όπου i είναι ο αριθμός πέρασμα του πίνακα (πρώτος, δεύτερος, τρίτος κ.λπ.).
8. Κατά την ανταλλαγή στοιχείων πίνακα, χρησιμοποιείται συνήθως μια μεταβλητή "buffer" (τρίτη), όπου τοποθετείται προσωρινά η τιμή ενός από τα στοιχεία.

Πρόγραμμα Pascal:

const m = 10 ; var arr: πίνακας [ 1 .. m ] ακέραιου αριθμού ; i, j, k: ακέραιος ; έναρξη τυχαιοποίησης? γράφω ( "Πίνακας πηγών: ") ; for i : = 1 έως m do start arr[ i] : = random(256 ) ; γράφω (arr[ i] : 4 ); τέλος ; γράφω ; γράφω ; for i : = 1 έως m- 1 do for j : = 1 έως m- i do if arr[ j] > arr[ j+ 1 ] then start k : = arr[ j] ; arr[ j] := arr[ j+ 1 ] ; arr[ j+ 1 ] : = k end ; γράφω ( "Ταξινομημένος πίνακας:") ; for i := 1 έως m do write (arr[ i] : 4 ) ; γράφω ; διαβάστε στο τέλος.

Ας τακτοποιήσουμε τον πίνακα από πάνω προς τα κάτω, από το μηδενικό στοιχείο μέχρι το τελευταίο.

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

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

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

Πρότυπο void bubbleSort(T a, μεγάλο μέγεθος) ( long i, j; T x; for(i=0; i< size; i++) { // i - αριθμός εισόδου for(j = μέγεθος-1; j > i; j--) ( // βρόχος εσωτερικής διέλευσηςαν (a > a[j]) ( x=a; a=a[j]; a[j]=x; ) ) )

Ο μέσος αριθμός συγκρίσεων και ανταλλαγών έχει μια τετραγωνική τάξη ανάπτυξης: Θήτα(n 2), επομένως μπορούμε να συμπεράνουμε ότι ο αλγόριθμος φυσαλίδων είναι πολύ αργός και αναποτελεσματικός.
Ωστόσο, έχει ένα τεράστιο πλεονέκτημα: είναι απλό και μπορεί να βελτιωθεί με κάθε τρόπο. Τι θα κάνουμε τώρα.

Αρχικά, εξετάστε την κατάσταση όταν δεν έχει γίνει ανταλλαγή σε κανένα από τα πάσο. Τι σημαίνει?

Αυτό σημαίνει ότι όλα τα ζεύγη είναι στη σωστή σειρά, επομένως ο πίνακας είναι ήδη ταξινομημένος. Και δεν έχει νόημα να συνεχίσετε τη διαδικασία (ειδικά αν ο πίνακας ήταν ταξινομημένος από την αρχή!).

Έτσι, η πρώτη βελτίωση του αλγορίθμου είναι να θυμάστε εάν έγινε οποιαδήποτε ανταλλαγή σε ένα δεδομένο πάσο. Εάν όχι, ο αλγόριθμος τερματίζεται.

Η διαδικασία βελτίωσης μπορεί να συνεχιστεί εάν θυμόμαστε όχι μόνο το γεγονός της ίδιας της ανταλλαγής, αλλά και τον δείκτη της τελευταίας ανταλλαγής k. Πράγματι: όλα τα ζεύγη γειτονικών στοιχείων με δείκτες μικρότερους από k βρίσκονται ήδη στην απαιτούμενη σειρά. Περαιτέρω περάσματα μπορούν να τελειώνουν στον δείκτη k αντί να μετακινούνται προς το προκαθορισμένο άνω όριο i.

Μια ποιοτικά διαφορετική βελτίωση του αλγορίθμου μπορεί να ληφθεί από την ακόλουθη παρατήρηση. Αν και η ελαφριά φυσαλίδα από κάτω θα ανέβει στην κορυφή με ένα πέρασμα, οι βαριές φυσαλίδες κατεβαίνουν με ελάχιστο ρυθμό ένα βήμα ανά επανάληψη. Έτσι, ο πίνακας 2 3 4 5 6 1 θα ταξινομηθεί σε 1 πέρασμα, ενώ η ταξινόμηση της ακολουθίας 6 1 2 3 4 5 θα απαιτήσει 5 περάσματα.

Για να αποφύγετε αυτό το αποτέλεσμα, μπορείτε να αλλάξετε την κατεύθυνση των διαδοχικών περασμάτων. Ο αλγόριθμος που προκύπτει αναφέρεται μερικές φορές ως " σέικερ-ταξινόμηση".

Πρότυπο void shakerSort(T a, μεγάλο μέγεθος) ( long j, k = size-1; long lb=1, ub = size-1; // όρια του μη ταξινομημένου τμήματος του πίνακα Tx; κάνω( // περάστε από κάτω προς τα πάνω for(j=ub; j>0; j--) ( if (a > a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) lb =k+1; // περάστε από πάνω προς τα κάτωγια (j=1; j<=ub; j++) { if (a >a[j]) ( x=a; a=a[j]; a[j]=x; k=j; ) ) ub = k-1; ) ενώ (lb< ub); }

Σε ποιο βαθμό οι περιγραφόμενες αλλαγές επηρέασαν την αποτελεσματικότητα της μεθόδου; Ο μέσος αριθμός συγκρίσεων, αν και έχει μειωθεί, παραμένει O(n 2), ενώ ο αριθμός των ανταλλαγών δεν έχει αλλάξει καθόλου. Ο μέσος (είναι και ο χειρότερος) αριθμός πράξεων παραμένει τετραγωνικός.

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

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