Αλγόριθμος QuickSort in JavaΓραφή

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

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

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

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

Κώδικας:

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

Ποιος είναι ο λόγος για να επιλέξετε Γρήγορη ταξινόμηση σε σχέση με την προεπιλεγμένη ταξινόμηση(). JavaΓραφή

Αν και η sort() δίνει το αποτέλεσμα που θέλουμε, το πρόβλημα έγκειται στον τρόπο που ταξινομεί τα στοιχεία του πίνακα. Προεπιλεγμένη ταξινόμηση() σε JavaΧρήσεις σεναρίου είδος εισαγωγής by Μηχανή V8 του Chrome και Συγχώνευση ταξινόμησης by Mozilla Firefox και Safari.

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

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

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

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

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

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

Πώς λειτουργεί το QuickSort

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

Ας δούμε λοιπόν αυτά τα βήματα με ένα παράδειγμα. Ας θεωρήσουμε ότι ο πίνακας στοιχείων που πρέπει να ταξινομήσουμε είναι [5,3,7,6,2,9].

Προσδιορίστε το στοιχείο Pivot

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

Ακολουθούν τα βήματα για την εκτέλεση Γρήγορης ταξινόμησης που παρουσιάζονται με ένα παράδειγμα [5,3,7,6,2,9].

ΒΗΜΑ 1: Προσδιορίστε το pivot ως μεσαίο στοιχείο. Ετσι, 7 είναι το στοιχείο περιστροφής.

ΒΗΜΑ 2: Ξεκινήστε τον αριστερό και τον δεξιό δείκτη ως πρώτο και τελευταίο στοιχείο του πίνακα αντίστοιχα. Έτσι, ο αριστερός δείκτης δείχνει προς 5 στο δείκτη 0 και ο δεξιός δείκτης δείχνει προς 9 στον δείκτη 5.

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

ΒΗΜΑ 4: Τώρα, ακόμα 3 <6, οπότε μετακινήστε τον αριστερό δείκτη σε ένα ακόμη ευρετήριο προς τα δεξιά. Έτσι τώρα 7 > 6 σταματά να αυξάνει τον αριστερό δείκτη και τώρα ο αριστερός δείκτης βρίσκεται στο δείκτη 2.

ΒΗΜΑ 5: Τώρα, συγκρίνετε την τιμή στο δεξιό δείκτη με το στοιχείο περιστροφής. Από 9 > 6 μετακινήστε τον δεξιό δείκτη προς τα αριστερά. Τώρα ως 2 < 6 σταματήστε να μετακινείτε τον δεξιό δείκτη.

ΒΗΜΑ 6: Αλλάξτε και τις δύο τιμές που υπάρχουν στον αριστερό και τον δεξιό δείκτη μεταξύ τους.

ΒΗΜΑ 7: Μετακινήστε και τους δύο δείκτες ένα ακόμη βήμα.

ΒΗΜΑ 8: Αφού 6 = 6, μετακινήστε τους δείκτες σε ένα ακόμη βήμα και σταματήστε καθώς ο αριστερός δείκτης διασχίζει τον δεξιό δείκτη και επιστρέψτε το ευρετήριο του αριστερού δείκτη.

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

Κωδικός για εναλλαγή δύο αριθμών JavaΓραφή

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); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

Εκτελέστε την αναδρομική λειτουργία

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

Έτσι, η Γρήγορη ταξινόμηση εκτελείται μέχρι να ταξινομηθούν όλα τα στοιχεία στον αριστερό πίνακα και στον δεξιό πίνακα.

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

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

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 result = quickSort(items, 0, items.length - 1);

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

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); //sawpping 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); //prints [2,3,5,6,7,9]

ΣΗΜΕΊΩΣΗ: Η γρήγορη ταξινόμηση εκτελείται με την πολυπλοκότητα χρόνου του O(nlogn).