Αλγόριθμοι ταξινόμησης: Μάθετε γιατί δεν πρέπει να χρησιμοποιείτε το Bubblesort

Αποκάλυψη: Η υποστήριξή σας βοηθά στη διατήρηση της λειτουργίας του ιστότοπου! Κερδίζουμε ένα τέλος παραπομπής για ορισμένες από τις υπηρεσίες που προτείνουμε σε αυτήν τη σελίδα.


Αναρωτηθήκατε ποτέ πώς ένας υπολογιστής τακτοποιεί τα πράγματα; Όταν κάνετε κλικ στο κουμπί A-Z στο Excel, τι συμβαίνει πραγματικά?

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

Εδώ είναι οι πιο δημοφιλείς αλγόριθμοι ταξινόμησης.

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

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

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

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

Πότε να χρησιμοποιήσετε το Bubble Sort

Ποτέ, εκτός από την επίδειξη.

Περισσότερες πληροφορίες σχετικά με το Bubble Sort

  • Bubble Sort εξήγηση από τον Αλγόριθμο, με παράδειγμα κώδικα;
  • Ο αλγόριθμος Bubble Sort κωδικοποιείται σε περισσότερες από 100 διαφορετικές γλώσσες προγραμματισμού.
  • Bubble Sort εικονογραφημένο με Legos.
  • Το Bubble Sort απεικονίζεται με ουγγρικό λαϊκό χορό.

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

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

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

Πότε να χρησιμοποιήσετε το Ταξινόμηση εισαγωγής

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

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

Περισσότερες πληροφορίες σχετικά με την ταξινόμηση εισαγωγής

  • Επεξήγηση εισαγωγής ταξινόμησης και άσκηση κωδικοποίησης, στο Khan Academy;
  • Εισαγωγή Αλγόριθμος Ταξινόμησης κωδικοποιημένος σε σχεδόν 100 διαφορετικές γλώσσες προγραμματισμού.
  • Εισαγωγή Ταξινόμηση εικονογραφημένη με φελιζόλ κύπελλα και αφηγήθηκε από φοιτητή του Χάρβαρντ CS.
  • Εισαγωγή Ταξινόμηση εικονογραφημένη με ουγγρικό λαϊκό χορό.

Ταξινόμηση σωρού

Το είδος σωρού είναι ένα είδος δύο μερών που χρησιμοποιεί μια δυαδική δομή δεδομένων σωρού ως ενδιάμεσος κάτοχος για τα στοιχεία στη λίστα.

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

Πότε να χρησιμοποιήσετε το Heap Sort

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

Περισσότερες πληροφορίες για Heap Sort

  • Λεπτομερής επεξήγηση του Heap Sort από καθηγητή CS στο Kent State.
  • Διαλέξεις βίντεο με σωρούς και σωρούς από το MIT.
  • Για μια εις βάθος κατανόηση των σωρών και των σωρών, δείτε αυτήν τη σειρά βίντεο πέντε μερών.

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

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

Για να ξεκινήσετε ένα είδος συγχώνευσης, μια λίστα χωρίζεται σε ένα σύνολο “λιστών” 1 στοιχείου. Στη συνέχεια, ζευγάρια αυτών των λιστών συγχωνεύονται σε λίστες 2 στοιχείων, οι οποίες στη συνέχεια συγχωνεύονται σε λίστες 4 στοιχείων και ούτω καθεξής έως ότου ολόκληρη η λίστα συγχωνευτεί ξανά.

Πότε να χρησιμοποιήσετε το Merge Sort

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

Περισσότερες πληροφορίες σχετικά με το Merge Sort

  • Το Merge Sort από το Khan Academy είναι ένα εξαιρετικό μάθημα έξι μερών που περιλαμβάνει ασκήσεις προγραμματισμού.
  • Merge Sort κωδικοποιημένο σε περισσότερες από 80 διαφορετικές γλώσσες προγραμματισμού.
  • Το Merge Sort with German Folk Dance παρέχει μια ρουτίνα χορού που δείχνει τον αλγόριθμο ταξινόμησης.

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

Το γρήγορο είδος δεν είναι πολύ διαισθητικό. Είναι, ωστόσο, πολύ αποτελεσματικό.

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

Πότε να χρησιμοποιήσετε τη γρήγορη ταξινόμηση

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

Περισσότερες πληροφορίες σχετικά με τη γρήγορη ταξινόμηση

  • Γρήγορη ταξινόμηση κωδικοποιημένη σε περισσότερες από 100 γλώσσες προγραμματισμού.
  • Η γρήγορη ταξινόμηση εξηγείται με μπλοκ από την κατηγορία CS-50 του Χάρβαρντ.
  • Το Quick Sort Tutorial από το Tutorials Point έχει πολλές λεπτομέρειες, δείγμα κώδικα και κινούμενες εικόνες.

Γενικοί πόροι αλγορίθμου ταξινόμησης

  • Δομή δεδομένων – Οι τεχνικές ταξινόμησης είναι μια πολύ λεπτομερής σειρά από το Tutorials Point.
  • Η ταξινόμηση των αλγορίθμων έχει απεικονίσεις κάθε είδους, υπό διαφορετικές συνθήκες – μπορείτε ακόμη και να παρακολουθήσετε διαφορετικούς αλγόριθμους να ανταγωνίζονται μεταξύ τους.
  • 15 Η ταξινόμηση των αλγορίθμων σε 6 λεπτά είναι μια συναρπαστική οπτικοποίηση βίντεο.
  • Η επιλογή Ταξινόμηση είναι βίντεο που διερευνά το πρόβλημα της μηχανογραφημένης ταξινόμησης.
  • Αυτό που οι διαφορετικοί αλγόριθμοι ταξινόμησης Sound Like είναι ένα απίστευτο βίντεο “audibilization” που μεταφράζει διάφορους αλγόριθμους ταξινόμησης σε ήχο.

Περίληψη

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

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

Περαιτέρω ανάγνωση και πόροι

Έχουμε περισσότερους οδηγούς, σεμινάρια και γραφήματα που σχετίζονται με την κωδικοποίηση και την ανάπτυξη:

  • Πόροι προγραμματιστών C ++: μία από τις πιο δημοφιλείς γλώσσες προγραμματισμού, κατάλληλη για τα περισσότερα είδη εφαρμογών.
  • Εισαγωγή και πόροι Unicode: μάθετε τα πάντα για την κωδικοποίηση χαρακτήρων.
  • MantisBT Εισαγωγή και πόροι: Το MantisBT είναι ένα από τα πιο δημοφιλή προγράμματα εντοπισμού σφαλμάτων.

Τι κώδικα πρέπει να μάθετε?

Μπερδεμένοι με ποια γλώσσα προγραμματισμού πρέπει να μάθετε να κωδικοποιείτε; Ρίξτε μια ματιά στο infographic μας, τι κώδικα πρέπει να μάθετε; Δεν συζητά μόνο διαφορετικές πτυχές των γλωσσών, αλλά απαντά σε σημαντικές ερωτήσεις όπως, “Πόσα χρήματα θα κάνω προγραμματισμό Java για τα προς το ζην;”

Τι κώδικα πρέπει να μάθετε;
Τι κώδικα πρέπει να μάθετε?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map