Αλγόριθμος QuickSort in JavaΣενάριο με παράδειγμα

Τι είναι η Γρήγορη Ταξινόμηση;

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

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

Τρεις ιδιότητες ορίζουν τη Γρήγορη Ταξινόμηση:

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

Τι είναι η ταξινόμηση;

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

Η ταξινόμηση έχει σημασία επειδή τα ταξινομημένα δεδομένα ξεκλειδώνουν ταχύτερες λειτουργίες. Μια δυαδική αναζήτηση εκτελείται σε χρόνο O(log n), αλλά μόνο σε ταξινομημένη είσοδο. Οι λειτουργίες αφαίρεσης διπλότυπων δεδομένων, τα ερωτήματα εύρους, η κατάταξη και η συγχώνευση γίνονται πολύ φθηνότερες μόλις τα δεδομένα είναι σε τάξη, γι' αυτό και κάθε γλώσσα παρέχει τουλάχιστον μία ρουτίνα ταξινόμησης.

Προεπιλεγμένη ταξινόμηση σε JavaΓραφή

Οπως αναφέρθηκε νωρίτερα, JavaΤο σενάριο παρέχει είδος()Πάρτε έναν μικρό πίνακα όπως [5,3,7,6,2,9] που θέλετε σε αύξουσα σειρά. Κλήση είδος() στον πίνακα φαίνεται να κάνει ακριβώς αυτό.

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

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

Παραγωγή:

[ 2, 3, 5, 6, 7, 9 ]

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

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Παραγωγή:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Ποιον αλγόριθμο χρησιμοποιεί η συνάρτηση sort();

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

• V8 (Chrome, Edge, Node.js) έχει χρησιμοποιήσει TimSort από την έκδοση V8 7.0, διατίθεται σε Chrome 70.
• SpiderMonkey (Firefox) χρήσεις συγχώνευση είδος.
• JavaScriptCore (Safari) χρησιμοποιεί επίσης συγχώνευση είδος.

Από το ES2019 η γλώσσα εγγυάται ότι sort() is σταθερός, το οποίο αποκλείει μια απλή Γρήγορη Ταξινόμηση μέσα στη μηχανή. Η ταξινόμηση που βασίζεται σε συγχώνευση χρειάζεται βοηθητική μνήμη O(n) και πρέπει να καλέσει το JavaΣυγκριτής σεναρίων για κάθε σύγκριση. Μια χειρόγραφη αριθμητική Γρήγορη Ταξινόμηση συγκρίνει τους αριθμούς απευθείας και ταξινομεί στη θέση τους, ώστε να μπορεί να κερδίσει σε μεγάλους αριθμητικούς πίνακες. Η ταξινόμηση 1,000,000 τυχαίων ακεραίων στο Node.js 22 χρειάστηκε περίπου... ms 100 με την παρακάτω Γρήγορη Ταξινόμηση και περίπου ms 210 μαζί σου, sort((a, b) => a - b).

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

Πώς λειτουργεί η Γρήγορη Ταξινόμηση;

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

1. Βρείτε το άξονας περιστροφής στοιχείο στον πίνακα.
2. Ξεκινήστε τον αριστερό δείκτη από το πρώτο στοιχείο του εύρους.
3. Ξεκινήστε τον δεξιό δείκτη από το τελευταίο στοιχείο του εύρους.
4. Συγκρίνετε το στοιχείο στον αριστερό δείκτη με τον άξονα περιστροφής. Εάν είναι μικρότερο από τον άξονα περιστροφής, μετακινήστε τον αριστερό δείκτη ένα βήμα προς τα δεξιά. Συνεχίστε μέχρι το αριστερό στοιχείο να είναι μεγαλύτερο ή ίσο με τον άξονα περιστροφής.
5. Συγκρίνετε το στοιχείο στον δεξιό δείκτη με τον άξονα περιστροφής. Εάν είναι μεγαλύτερο από τον άξονα περιστροφής, μετακινήστε τον δεξιό δείκτη ένα βήμα προς τα αριστερά. Συνεχίστε μέχρι το δεξί στοιχείο να είναι μικρότερο ή ίσο με τον άξονα περιστροφής.
6. Εάν ο αριστερός δείκτης εξακολουθεί να είναι μικρότερος ή ίσος με τον δεξιό δείκτη, ανταλλάξτε τα δύο στοιχεία.
7. Αυξήστε τον αριστερό δείκτη και μειώστε τον δεξιό δείκτη.
8. Εάν ο αριστερός δείκτης εξακολουθεί να είναι μικρότερος ή ίσος με τον δεξιό δείκτη, επαναλάβετε από το βήμα 4. Διαφορετικά, επιστρέψτε τον δείκτη του αριστερού δείκτη.

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

Πώς να προσδιορίσετε το στοιχείο περιστροφής

Η επιλογή του pivot είναι η μόνη απόφαση που διαχωρίζει μια γρήγορη Γρήγορη Ταξινόμηση από μια αργή. Αν πάντα επιλέγετε το πρώτα στοιχείο, ένας ήδη ταξινομημένος πίνακας παράγει τη χειρότερη δυνατή διαίρεση: μία κενή πλευρά και μία πλευρά με κάθε εναπομείναν στοιχείο. Αυτό μετατρέπει τον αλγόριθμο σε O(n²). Λαμβάνοντας το μέσο Το στοιχείο (το μήκος του πίνακα διαιρούμενο με το δύο) αποφεύγει αυτήν την παγίδα για ταξινομημένη και αντίστροφα ταξινομημένη είσοδο, γι' αυτό και ο παρακάτω κώδικας το χρησιμοποιεί.

Κοινές στρατηγικές pivot:

• Πρώτο ή τελευταίο στοιχείο: απλούστερο στην κωδικοποίηση, αλλά O(n²) σε ταξινομημένα δεδομένα.
• Μεσαίο στοιχείο: μια καλή προεπιλογή που χειρίζεται ταξινομημένους και αντίστροφα ταξινομημένους πίνακες σε O(n log n).
• Τυχαίο στοιχείο: καθιστά αδύνατη την εκ των προτέρων κατασκευή της χειρότερης περίπτωσης εισόδου.
• Διάμεσος των τριών: λαμβάνει τη διάμεση τιμή της πρώτης, της μεσαίας και της τελευταίας τιμής· η τυπική επιλογή στις βιβλιοθήκες παραγωγής.

Τώρα, προχωρήστε στη Γρήγορη Ταξινόμηση στον πίνακα [5,3,7,6,2,9].

ΒΗΜΑ 1: Το στοιχείο pivot είναι το μεσαίο. Με αριστερά = 0 και δεξιά = 5, Math.floor((5 + 0) / 2) δίνει δείκτη 2, επομένως η τιμή pivot είναι 7.

ΒΗΜΑ 2: Ξεκινήστε τους δείκτες από τα άκρα του πίνακα. Ο αριστερός δείκτης βρίσκεται στον δείκτη 0 (τιμή 5) και ο δεξιός δείκτης βρίσκεται στον δείκτη 5 (τιμή 9).

ΒΗΜΑ 3: Συγκρίνετε την αριστερή τιμή με την περιστροφή. 5 < 7, άρα μετακινηθείτε δεξιά στον δείκτη 1. 3 < 7, άρα μετακινηθείτε δεξιά στον δείκτη 2. Η τιμή εκεί είναι 7, η οποία δεν είναι μικρότερη από την περιστροφή, άρα ο αριστερός δείκτης σταματά στον δείκτη 2.

ΒΗΜΑ 4: Συγκρίνετε τη δεξιά τιμή με τον άξονα περιστροφής. 9 > 7, επομένως μετακινηθείτε αριστερά στον δείκτη 4. Η τιμή εκεί είναι 2, η οποία δεν είναι μεγαλύτερη από τον άξονα περιστροφής, επομένως ο δεξιός δείκτης σταματά στον δείκτη 4.

ΒΗΜΑ 5: Ο αριστερός δείκτης (2) είναι μικρότερος ή ίσος με τον δεξιό δείκτη (4), επομένως ανταλλάξτε τις δύο τιμές. Ο πίνακας γίνεται [5,3,2,6,7,9].

ΒΗΜΑ 6: Μετακινήστε και τους δύο δείκτες ένα βήμα προς τα μέσα. Ο αριστερός δείκτης βρίσκεται τώρα στο δείκτη 3 και ο δεξιός δείκτης στο δείκτη 3.

ΒΗΜΑ 7: Επαναλάβετε τη σάρωση. Η τιμή στον δείκτη 3 είναι 6 και 6 < 7, επομένως ο αριστερός δείκτης προχωρά στον δείκτη 4. Η τιμή στον δείκτη 3 δεν είναι μεγαλύτερη από την περιστροφή, επομένως ο δεξιός δείκτης παραμένει στον δείκτη 3.

ΒΗΜΑ 8: Ο αριστερός δείκτης (4) είναι πλέον μεγαλύτερος από τον δεξιό δείκτη (3), επομένως ο βρόχος τερματίζεται και η συνάρτηση επιστρέφει 4Όλα όσα βρίσκονται πριν από τον δείκτη 4 είναι μικρότερα ή ίσα με τον άξονα περιστροφής και όλα όσα βρίσκονται από τον δείκτη 4 και μετά είναι μεγαλύτερα ή ίσα με αυτόν.

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

Code να ανταλλάξω δύο Numbers in JavaΓραφή

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

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Παραγωγή:

[ 9, 3, 7, 6, 2, 5 ]

Code για να εκτελέσετε τη διαμέριση

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

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Παραγωγή:

[ 5, 3, 2, 6, 7, 9 ]
4

Η έξοδος ταιριάζει ακριβώς με την χειροκίνητη αναλυτική παρουσίαση: μετά από μία διέλευση διαμερίσματος, ο πίνακας είναι [5,3,2,6,7,9] και ο επιστρεφόμενος δείκτης διαίρεσης είναι 4.

Εκτελέστε την Αναδρομική Operaσμού

Μόλις η διαμέριση επιστρέψει τον δείκτη διαίρεσης, χρησιμοποιήστε τον για να διαιρέσετε το εύρος και εκτελέστε την Γρήγορη Ταξινόμηση σε κάθε μισό. Γι' αυτό ονομάζεται αλγόριθμος Διαίρει και Βασίλευε. Η αναδρομή συνεχίζεται μέχρι κάθε υποεύρος να περιέχει ένα μόνο στοιχείο, οπότε ταξινομείται ολόκληρος ο πίνακας.

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

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

Παρατηρήστε τις δύο συνθήκες προστασίας που επισημαίνονται στο στιγμιότυπο οθόνης. left < index - 1 επιβεβαιώνει ότι τουλάχιστον δύο στοιχεία παραμένουν στην αριστερή πλευρά, και index < right επιβεβαιώνει το ίδιο και για τη δεξιά πλευρά. Χωρίς αυτούς τους προφυλακτήρες, η συνάρτηση θα καλούσε τον εαυτό της για πάντα σε εύρη ενός στοιχείου.

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Παραγωγή:

[ 2, 3, 5, 6, 7, 9 ]

Ολοκλήρωση γρήγορης ταξινόμησης Code

Η συνένωση των κομματιών swap, partition και recursion δίνει την πλήρη υλοποίηση:

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

Παραγωγή:

[ 2, 3, 5, 6, 7, 9 ]

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

Χρονική και χωρική πολυπλοκότητα της γρήγορης ταξινόμησης

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

Η πολυπλοκότητα του χώρου είναι O(log n) για αυτήν την έκδοση που είναι τοποθετημένη στη θέση της. Δεν εκχωρείται δεύτερος πίνακας, επομένως η μόνη επιπλέον μνήμη είναι η στοίβα αναδρομής, και ο ισορροπημένος διαχωρισμός διατηρεί αυτή τη στοίβα περίπου σε log₂(n) πλαίσια βάθος. Στη χειρότερη περίπτωση εκφυλισμού, η στοίβα μεγαλώνει σε O(n) πλαίσια, γι' αυτό και πολύ μεγάλοι πίνακες μπορούν να υπερχειλίσουν τη στοίβα κλήσεων.

Δύο αριθμοί το καθιστούν συγκεκριμένο. Η ταξινόμηση 4,096 τυχαίων τιμών με τον παραπάνω κώδικα χρησιμοποίησε περίπου 65,000 συγκρίσεις έναντι ενός θεωρητικού n·log₂(n) 49,152, και η βαθύτερη αναδρομή έφτασε τα 24 καρέ, ενώ το log₂(4096) είναι 12. Και τα δύο στοιχεία εμπίπτουν στον μικρό σταθερό παράγοντα που αναμένεται από έναν αλγόριθμο O(n log n).

Γρήγορη ταξινόμηση έναντι άλλης ταξινόμησης Algorithms

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

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

Πώς να ταξινομήσετε γρήγορα αντικείμενα και συμβολοσειρές

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

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

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Παραγωγή:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Αξίζει να σημειωθούν τρεις λεπτομέρειες. Ο φρουρός αναδρομής είναι τώρα left >= right, το οποίο είναι σωστό για οποιοδήποτε εύρος και δεν εξαρτάται από το μήκος του εξωτερικού πίνακα. Η σύγκριση συμβολοσειρών χρησιμοποιεί localeCompare() έτσι ώστε οι τονισμένοι χαρακτήρες και τα πεζά-κεφαλαία να αντιμετωπίζονται σωστά αντί για τα σημεία του ακατέργαστου κώδικα. Και επειδή η Γρήγορη Ταξινόμηση δεν είναι σταθερή, οι εγγραφές που μοιράζονται έναν μισθό ενδέχεται να αλλάζουν θέσεις. Ταξινομήστε κατά ένα δεύτερο κλειδί που να διακόπτει την ισοπαλία, εάν η αρχική σειρά έχει σημασία για εσάς.

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

Συχνές Ερωτήσεις