Αλγόριθμος QuickSort σε JavaScript

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

Ο αλγόριθμος Quick Sort ακολουθεί την προσέγγιση Divide and Conquer. Διαιρεί στοιχεία σε μικρότερα μέρη με βάση κάποια κατάσταση και εκτελεί τις λειτουργίες ταξινόμησης σε αυτά τα διαιρεμένα μικρότερα μέρη.

Ο αλγόριθμος Quick Sort είναι ένας από τους πιο δημοφιλείς και δημοφιλείς αλγόριθμους σε οποιαδήποτε γλώσσα προγραμματισμού. Ωστόσο, εάν είστε προγραμματιστής JavaScript, τότε ίσως έχετε ακούσει για είδος () που είναι ήδη διαθέσιμο σε JavaScript. Τότε, ίσως σκεφτόσασταν ποια είναι η ανάγκη αυτού του αλγορίθμου γρήγορης ταξινόμησης. Για να το καταλάβουμε αυτό, πρώτα χρειαζόμαστε τι είναι η ταξινόμηση και ποια είναι η προεπιλεγμένη ταξινόμηση στο JavaScript.

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

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

Προεπιλεγμένη ταξινόμηση σε JavaScript

Όπως αναφέρθηκε προηγουμένως, το JavaScript έχει είδος () . Ας πάρουμε ένα παράδειγμα με λίγους πίνακες στοιχείων όπως [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]

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

Αν και το είδος () δίνει το αποτέλεσμα που θέλουμε, το πρόβλημα έγκειται στον τρόπο ταξινόμησης των στοιχείων του πίνακα. Η προεπιλεγμένη ταξινόμηση () στο JavaScript χρησιμοποιεί ταξινόμηση εισαγωγής κατά V8 Engine του Chrome και ταξινόμηση συγχώνευσης κατά Mozilla Firefox και Safari .

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

Επομένως, για να καταλάβετε πλήρως, πρέπει να γνωρίζετε πώς λειτουργεί το Quick sort και ας το δούμε λεπτομερώς τώρα.

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

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

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

Αυτό είναι λοιπόν το βασικό περίγραμμα της γρήγορης ταξινόμησης. Εδώ είναι τα βήματα που πρέπει να ακολουθήσετε ένα προς ένα για να πραγματοποιήσετε γρήγορη ταξινόμηση.

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

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

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

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

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

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

ΒΗΜΑ 1: Προσδιορίστε τον άξονα ως μεσαίο στοιχείο. Έτσι, το 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, μετακινήστε τους δείκτες σε ένα ακόμη βήμα και σταματήστε καθώς ο αριστερός δείκτης διασχίζει το δεξί δείκτη και επιστρέψτε το δείκτη του αριστερού δείκτη.

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

Κωδικός για εναλλαγή δύο αριθμών σε JavaScript:

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 elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;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 partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar 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 elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]