Quicksort ως μέθοδος προγραμματισμού

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

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

Quicksort είναι πολύ συχνές, μπορεί να βρεθεί παντού. Στη βάση της η μέθοδος υλοποιείται TList.Sort, παρούσα σε όλες τις εκδόσεις (εκτός από 1) Δελφοί, τη λειτουργία βιβλιοθήκης του χρόνου που χρειάστηκε για να ολοκληρωθεί, qsort σε C ++.

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

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

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

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