Επεξήγηση αλγορίθμων ταξινόμησης

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

Τα είδη είναι συνήθως σε αριθμητική ή αλφαβητική (λεξικογραφική) σειρά και μπορούν να είναι σε αύξουσα (AZ, 0-9) ή φθίνουσα (ZA, 9-0).

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

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

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

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

  • Ταξινόμηση επιλογής
  • Ταξινόμηση φυσαλίδων
  • Ταξινόμηση εισαγωγής
  • Συγχώνευση ταξινόμησης
  • Γρήγορη ταξινόμηση
  • Ταξινόμηση σωρού
  • Καταμέτρηση Ταξινόμηση
  • Ταξινόμηση Radix
  • Ταξινόμηση κάδου

Ταξινόμηση του Αλγόριθμου Ταξινόμησης

Οι αλγόριθμοι ταξινόμησης μπορούν να κατηγοριοποιηθούν με βάση τις ακόλουθες παραμέτρους:

  1. Με βάση τον αριθμό ανταλλαγών ή αντιστροφής. Αυτός είναι ο αριθμός των φορών που ο αλγόριθμος ανταλλάσσει στοιχεία για να ταξινομήσει την εισαγωγή. Selection Sortαπαιτεί τον ελάχιστο αριθμό ανταλλαγών.
  2. Με βάση τον αριθμό συγκρίσεων Αυτός είναι ο αριθμός των φορών που ο αλγόριθμος συγκρίνει στοιχεία για να ταξινομήσει την είσοδο. Χρησιμοποιώντας τη σημείωση Big-O, τα παραδείγματα αλγορίθμου ταξινόμησης που αναφέρονται παραπάνω απαιτούν τουλάχιστον O(nlogn)συγκρίσεις στην καλύτερη περίπτωση και O(n^2)συγκρίσεις στη χειρότερη περίπτωση για τις περισσότερες από τις εξόδους.
  3. Με βάση την αναδρομή ή τη μη επανάληψη Ορισμένοι αλγόριθμοι ταξινόμησης, όπως Quick Sort, χρησιμοποιούν αναδρομικές τεχνικές για να ταξινομήσετε την είσοδο. Άλλοι αλγόριθμοι ταξινόμησης, όπως Selection Sortή Insertion Sort, χρησιμοποιούν μη αναδρομικές τεχνικές. Τέλος, κάποιος αλγόριθμος ταξινόμησης, όπως Merge Sort, χρησιμοποιεί τόσο τις αναδρομικές όσο και τις μη αναδρομικές τεχνικές για να ταξινομήσει την είσοδο.
  4. Με βάση τη σταθερότητα, οι αλγόριθμοι ταξινόμησης λέγονται ότι stableεάν ο αλγόριθμος διατηρεί τη σχετική σειρά στοιχείων με ίσα κλειδιά. Με άλλα λόγια, δύο ισοδύναμα στοιχεία παραμένουν στην ίδια σειρά στην ταξινομημένη έξοδο όπως ήταν στην είσοδο.
  5. Insertion sort, Merge Sortκαι Bubble Sortείναι σταθερές
  6. Heap Sortκαι Quick Sortδεν είναι σταθερά
  7. Με βάση τις απαιτήσεις επιπλέον χώρου, οι αλγόριθμοι ταξινόμησης λέγονται in placeότι απαιτούν σταθερό O(1)επιπλέον χώρο για ταξινόμηση.
  8. Insertion sortκαι Quick-sortείναι in placeτο είδος καθώς προχωράμε τα στοιχεία σχετικά με τον άξονα και δεν χρησιμοποιούν πραγματικά μια ξεχωριστή σειρά η οποία δεν είναι η περίπτωση συγχώνευσης του είδους, όπου το μέγεθος της εισόδου πρέπει να διατεθεί εκ των προτέρων για να αποθηκεύσετε την έξοδο κατά τη διάρκεια της ταξινόμησης.
  9. Merge Sortείναι ένα παράδειγμα του out placeείδους που απαιτεί επιπλέον χώρο μνήμης για τις λειτουργίες του.

Η καλύτερη δυνατή χρονική πολυπλοκότητα για οποιαδήποτε ταξινόμηση βάσει σύγκρισης

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