quick sort c with examples
Quicksort σε C ++ με εικονογράφηση.
Το Quicksort είναι ένας ευρέως χρησιμοποιούμενος αλγόριθμος ταξινόμησης που επιλέγει ένα συγκεκριμένο στοιχείο που ονομάζεται 'pivot' και χωρίζει τον πίνακα ή τη λίστα που θα ταξινομηθούν σε δύο μέρη με βάση αυτόν τον άξονα s0 ότι τα στοιχεία μικρότερα από τον άξονα βρίσκονται στα αριστερά της λίστας και τα στοιχεία μεγαλύτερο από τον άξονα που βρίσκεται στα δεξιά της λίστας.
Έτσι, η λίστα χωρίζεται σε δύο λίστες. Οι δευτερεύουσες λίστες ενδέχεται να μην είναι απαραίτητες για το ίδιο μέγεθος. Στη συνέχεια, το Quicksort καλείται αναδρομικά για να ταξινομήσει αυτές τις δύο λίστες.
=> Ανατρέξτε στον τέλειο οδηγό εκπαίδευσης C ++ εδώ.
Τι θα μάθετε:
- Εισαγωγή
- Γενικός αλγόριθμος
- Ψευδοκωδικός για Quicksort
- Απεικόνιση
- Παράδειγμα C ++
- Παράδειγμα Java
- Ανάλυση πολυπλοκότητας του αλγόριθμου Quicksort
- 3-κατευθύνσεων Quicksort
- Τυχαιοποιημένο Quicksort
- Quicksort εναντίον Merge Sort
- συμπέρασμα
- Συνιστώμενη ανάγνωση
Εισαγωγή
Το Quicksort λειτουργεί αποτελεσματικά και ταχύτερα ακόμη και για μεγαλύτερες συστοιχίες ή λίστες.
Σε αυτό το σεμινάριο, θα διερευνήσουμε περισσότερα σχετικά με τη λειτουργία του Quicksort μαζί με ορισμένα παραδείγματα προγραμματισμού του αλγορίθμου quicksort.
Ως κεντρική τιμή, μπορούμε να επιλέξουμε είτε την πρώτη, την τελευταία είτε τη μέση τιμή ή οποιαδήποτε τυχαία τιμή. Η γενική ιδέα είναι ότι τελικά η τιμή περιστροφής τοποθετείται στη σωστή θέση της στον πίνακα μετακινώντας τα άλλα στοιχεία του πίνακα προς τα αριστερά ή προς τα δεξιά.
Γενικός αλγόριθμος
Ο γενικός αλγόριθμος για το Quicksort δίνεται παρακάτω.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Ας ρίξουμε μια ματιά στον ψευδοκώδικα για την τεχνική Quicksort.
Ψευδοκωδικός για Quicksort
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Η λειτουργία του αλγορίθμου διαμέρισης περιγράφεται παρακάτω χρησιμοποιώντας ένα παράδειγμα.
Σε αυτήν την εικόνα, παίρνουμε το τελευταίο στοιχείο ως άξονα. Μπορούμε να δούμε ότι ο πίνακας χωρίζεται διαδοχικά γύρω από το στοιχείο περιστροφής έως ότου έχουμε ένα μόνο στοιχείο στον πίνακα.
Τώρα παρουσιάζουμε μια απεικόνιση του Quicksort παρακάτω για να κατανοήσουμε καλύτερα την έννοια.
Απεικόνιση
Ας δούμε μια απεικόνιση του αλγορίθμου γρήγορης ταξινόμησης. Σκεφτείτε τον ακόλουθο πίνακα με το τελευταίο στοιχείο ως άξονα. Επίσης, το πρώτο στοιχείο είναι χαμηλό και το τελευταίο είναι υψηλό.
με τι ανοίγεις αρχεία βάζων
Από την εικόνα, μπορούμε να δούμε ότι, κινούμαστε τους δείκτες ψηλά και χαμηλά και στα δύο άκρα του πίνακα. Όποτε χαμηλά σημεία στο στοιχείο είναι μεγαλύτερο από το άξονα και υψηλά σημεία στο στοιχείο μικρότερο από το άξονα, τότε ανταλλάσσουμε τις θέσεις αυτών των στοιχείων και προωθούμε τους χαμηλούς και υψηλούς δείκτες στις αντίστοιχες κατευθύνσεις τους.
Αυτό γίνεται έως ότου οι χαμηλοί και οι υψηλοί δείκτες διασταυρώνονται μεταξύ τους. Μόλις διασταυρωθούν το στοιχείο περιστροφής τοποθετείται στη σωστή του θέση και ο πίνακας χωρίζεται σε δύο. Στη συνέχεια, και οι δύο αυτές υπο-σειρές ταξινομούνται ανεξάρτητα χρησιμοποιώντας τη γρήγορη ταξινόμηση αναδρομικά.
Παράδειγμα C ++
Δίνεται παρακάτω η εφαρμογή του αλγορίθμου Quicksort στο C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Παραγωγή:
Πίνακας εισόδου
διαφορά μεταξύ δοκιμών blackbox και whitebox
12 23 3 43 51 35 19 45
Η σειρά ταξινομήθηκε με γρήγορη ταξινόμηση
3 12 19 23 35 43 45 51
Εδώ έχουμε λίγες ρουτίνες που χρησιμοποιούνται για την κατάτμηση του πίνακα και την κλήση της γρήγορης ταξινόμησης αναδρομικά για να ταξινομήσετε το διαμέρισμα, τη βασική λειτουργία γρήγορης ταξινόμησης και τις λειτουργίες χρησιμότητας για να εμφανίσετε τα περιεχόμενα του πίνακα και να αλλάξετε τα δύο στοιχεία ανάλογα.
Πρώτον, καλούμε τη συνάρτηση γρήγορης ταξινόμησης με τον πίνακα εισαγωγής. Μέσα στη συνάρτηση γρήγορης ταξινόμησης, καλούμε τη συνάρτηση διαμέρισης. Στη συνάρτηση κατάτμησης, χρησιμοποιούμε το τελευταίο στοιχείο ως στοιχείο περιστροφής για τον πίνακα. Μόλις αποφασιστεί ο άξονας, ο πίνακας χωρίζεται σε δύο μέρη και στη συνέχεια καλείται η συνάρτηση γρήγορης ταξινόμησης για να ταξινομήσει ανεξάρτητα και τις δύο δευτερεύουσες συστοιχίες.
Όταν η συνάρτηση γρήγορης ταξινόμησης επιστρέφει, ο πίνακας ταξινομείται έτσι ώστε το στοιχείο περιστροφής να βρίσκεται στη σωστή θέση του και τα στοιχεία μικρότερα από τον άξονα να βρίσκονται στα αριστερά του άξονα και τα στοιχεία μεγαλύτερα από τον άξονα να βρίσκονται στα δεξιά του άξονα.
Στη συνέχεια, θα εφαρμόσουμε τον αλγόριθμο quicksort στην Java.
Παράδειγμα Java
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Παραγωγή:
Πίνακας εισόδου
12 23 3 43 51 35 19 45
Σειρά μετά την ταξινόμηση με γρήγορη ταξινόμηση
3 12 19 23 35 43 45 51
Στην εφαρμογή Java επίσης, χρησιμοποιήσαμε την ίδια λογική που χρησιμοποιήσαμε στην υλοποίηση C ++. Έχουμε χρησιμοποιήσει το τελευταίο στοιχείο στη συστοιχία καθώς ο άξονας και η γρήγορη ταξινόμηση εκτελείται στη συστοιχία προκειμένου να τοποθετηθεί το στοιχείο περιστροφής στη σωστή του θέση.
Ανάλυση πολυπλοκότητας του αλγόριθμου Quicksort
Ο χρόνος που απαιτείται από τη γρήγορη ταξινόμηση για ταξινόμηση ενός πίνακα εξαρτάται από τον πίνακα εισαγωγής και τη στρατηγική ή τη μέθοδο διαμέρισης.
Εάν το k είναι ο αριθμός των στοιχείων μικρότερος από τον άξονα και το n είναι ο συνολικός αριθμός των στοιχείων, τότε ο γενικός χρόνος που απαιτείται από το quicksort μπορεί να εκφραστεί ως εξής:
T (n) = T (k) + T (n-k-1) + O (n)
Εδώ, T (k) και T (n-k-1) είναι ο χρόνος που απαιτείται από αναδρομικές κλήσεις και το O (n) είναι ο χρόνος που απαιτείται από την κλήση διαμέρισης.
Ας αναλύσουμε αυτήν τη χρονική πολυπλοκότητα για γρήγορη ταξινόμηση λεπτομερώς.
# 1) Χειρότερη περίπτωση : Η χειρότερη περίπτωση στην τεχνική γρήγορης ταξινόμησης εμφανίζεται κυρίως όταν επιλέγουμε το χαμηλότερο ή υψηλότερο στοιχείο του πίνακα ως άξονα. (Στην παραπάνω εικόνα έχουμε επιλέξει το υψηλότερο στοιχείο ως τον άξονα). Σε μια τέτοια περίπτωση, η χειρότερη περίπτωση εμφανίζεται όταν ο πίνακας προς ταξινόμηση έχει ήδη ταξινομηθεί με αύξουσα ή φθίνουσα σειρά.
Εξ ου και η παραπάνω έκφραση για το συνολικό χρονικό διάστημα αλλάζει ως:
T (n) = T (0) + T (n-1) + O (n) που επιλύει Επίδύο)
# 2) Καλύτερη περίπτωση: Η καλύτερη περίπτωση για γρήγορη ταξινόμηση εμφανίζεται πάντα όταν το στοιχείο περιστροφής που επιλέγεται είναι το μέσο του πίνακα.
Έτσι, η επανάληψη για την καλύτερη περίπτωση είναι:
πώς να προσθέσετε έναν ακέραιο σε έναν πίνακα στο java
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Μέση περίπτωση: Για να αναλύσουμε τη μέση περίπτωση για γρήγορη ταξινόμηση, θα πρέπει να λάβουμε υπόψη όλες τις παραλλαγές πίνακα και στη συνέχεια να υπολογίσουμε τον χρόνο που απαιτείται για καθεμία από αυτές τις παραλλαγές. Με λίγα λόγια, ο μέσος χρόνος για γρήγορη ταξινόμηση γίνεται επίσης O (nlogn).
Παρακάτω δίνονται οι διάφορες πολυπλοκότητες για την τεχνική Quicksort:
Χειρότερη περίπτωση πολυπλοκότητας Ο (ν 2) σταθερότητα Δεν είναι σταθερά καθώς δύο στοιχεία με τις ίδιες τιμές δεν θα τοποθετηθούν στην ίδια σειρά. Σταθερό - δύο στοιχεία με τις ίδιες τιμές θα εμφανίζονται με την ίδια σειρά στην ταξινομημένη έξοδο. Καλύτερη πολυπλοκότητα χρόνου O (n * log n) Μέσος χρόνος πολυπλοκότητας O (n * log n) Διαστημικότητα O (n * log n)
Μπορούμε να εφαρμόσουμε τη γρήγορη ταξινόμηση με πολλούς διαφορετικούς τρόπους απλά αλλάζοντας την επιλογή του περιστρεφόμενου στοιχείου (μεσαίο, πρώτο ή τελευταίο), ωστόσο, η χειρότερη περίπτωση εμφανίζεται σπάνια για τη γρήγορη ταξινόμηση.
3-κατευθύνσεων Quicksort
Στην αρχική τεχνική γρήγορης ταξινόμησης, συνήθως επιλέγουμε ένα στοιχείο περιστροφής και στη συνέχεια διαιρούμε τον πίνακα σε δευτερεύουσες συστοιχίες γύρω από αυτόν τον άξονα, έτσι ώστε μια δευτερεύουσα σειρά να αποτελείται από στοιχεία μικρότερα από τον άξονα και μια άλλη να αποτελείται από στοιχεία μεγαλύτερα από τον άξονα.
Τι γίνεται όμως αν επιλέξουμε ένα στοιχείο περιστροφής και υπάρχουν περισσότερα από ένα στοιχεία στον πίνακα που είναι ίσο με το περιστρεφόμενο;
Για παράδειγμα, λάβετε υπόψη τον ακόλουθο πίνακα {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Εάν εκτελέσουμε μια απλή γρήγορη ταξινόμηση σε αυτόν τον πίνακα και επιλέξουμε το 4 ως στοιχείο περιστροφής, τότε θα διορθώσουμε μόνο μία εμφάνιση του στοιχείου 4 και τα υπόλοιπα θα διαχωριστούν μαζί με τα άλλα στοιχεία.
Αντ 'αυτού, εάν χρησιμοποιούμε γρήγορη ταξινόμηση 3 κατευθύνσεων, τότε θα διαιρέσουμε τον πίνακα (l… r) σε τρεις υπο-σειρές ως εξής:
- Array (l… i) - Εδώ, είμαι ο άξονας και αυτός ο πίνακας περιέχει στοιχεία λιγότερο από το άξονα.
- Array (i + 1… j-1) - Περιέχει τα στοιχεία που είναι ίδια με τον άξονα.
- Array (j… r) - Περιέχει στοιχεία μεγαλύτερα από τον άξονα.
Έτσι, η γρήγορη ταξινόμηση 3 κατευθύνσεων μπορεί να χρησιμοποιηθεί όταν έχουμε περισσότερα από ένα περιττά στοιχεία στη συστοιχία.
Τυχαιοποιημένο Quicksort
Η τεχνική γρήγορης ταξινόμησης ονομάζεται τεχνική τυχαιοποιημένης γρήγορης ταξινόμησης όταν χρησιμοποιούμε τυχαίους αριθμούς για να επιλέξουμε το στοιχείο περιστροφής. Στην τυχαιοποιημένη γρήγορη ταξινόμηση, ονομάζεται «κεντρικός άξονας» και διαιρεί τον πίνακα με τέτοιο τρόπο ώστε κάθε πλευρά να έχει τουλάχιστον ¼ στοιχεία.
Ο ψευδοκωδικός για τυχαιοποιημένη γρήγορη ταξινόμηση δίνεται παρακάτω:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureΣτον παραπάνω κώδικα στο 'randomQuickSort', στο βήμα # 2 επιλέγουμε τον κεντρικό άξονα. Στο βήμα 2, η πιθανότητα του επιλεγμένου στοιχείου να είναι ο κεντρικός άξονας είναι ½. Ως εκ τούτου, ο βρόχος στο βήμα 2 αναμένεται να τρέξει 2 φορές. Έτσι, η πολυπλοκότητα του χρόνου για το βήμα 2 στην τυχαιοποιημένη γρήγορη ταξινόμηση είναι O (n).
Η χρήση βρόχου για την επιλογή του κεντρικού άξονα δεν είναι ο ιδανικός τρόπος για την εφαρμογή τυχαιοποιημένης γρήγορης ταξινόμησης. Αντ 'αυτού, μπορούμε να επιλέξουμε τυχαία ένα στοιχείο και να το ονομάσουμε κεντρικό άξονα ή να ανακατέψουμε τα στοιχεία του πίνακα. Η αναμενόμενη πολυπλοκότητα χειρότερου χρόνου για τον τυχαιοποιημένο αλγόριθμο γρήγορης ταξινόμησης είναι O (nlogn).
Quicksort εναντίον Merge Sort
Σε αυτήν την ενότητα, θα συζητήσουμε τις κύριες διαφορές μεταξύ γρήγορης ταξινόμησης και συγχώνευσης.
Παράμετρος σύγκρισης Γρήγορη ταξινόμηση Συγχώνευση ταξινόμησης διαμέριση Ο πίνακας χωρίζεται γύρω από ένα περιστρεφόμενο στοιχείο και δεν είναι απαραίτητα πάντα σε δύο μισά. Μπορεί να χωριστεί σε οποιαδήποτε αναλογία. Ο πίνακας χωρίζεται σε δύο μισά (n / 2). Χειρότερη περίπλοκη περίπτωση O (n 2) - απαιτούνται πολλές συγκρίσεις στη χειρότερη περίπτωση. O (nlogn) - ίδιο με τη μέση περίπτωση Χρήση συνόλων δεδομένων Δεν μπορεί να λειτουργήσει καλά με μεγαλύτερα σύνολα δεδομένων. Λειτουργεί καλά με όλα τα σύνολα δεδομένων ανεξάρτητα από το μέγεθος. Πρόσθετος χώρος Επιτόπου - δεν χρειάζεται επιπλέον χώρο. Δεν υπάρχει - χρειάζεται επιπλέον χώρος για την αποθήκευση βοηθητικής συστοιχίας. Μέθοδος ταξινόμησης Εσωτερικά - τα δεδομένα ταξινομούνται στην κύρια μνήμη. External - χρησιμοποιεί εξωτερική μνήμη για την αποθήκευση συστοιχιών δεδομένων. Αποδοτικότητα Ταχύτερη και αποτελεσματική για λίστες μικρών μεγεθών. Γρήγορη και αποτελεσματική για μεγαλύτερες λίστες. Πίνακες / συνδεδεμένες λίστες Προτιμάται περισσότερο για συστοιχίες. Λειτουργεί καλά για συνδεδεμένες λίστες.
συμπέρασμα
Όπως υποδηλώνει το ίδιο το όνομα, το quicksort είναι ο αλγόριθμος που ταξινομεί τη λίστα γρήγορα από οποιονδήποτε άλλο αλγόριθμο ταξινόμησης. Ακριβώς όπως το είδος συγχώνευσης, το γρήγορο είδος υιοθετεί επίσης στρατηγική διαίρεσης και κατάκτησης.
Όπως έχουμε ήδη δει, χρησιμοποιώντας γρήγορη ταξινόμηση χωρίζουμε τη λίστα σε υπο-πίνακες χρησιμοποιώντας το στοιχείο περιστροφής. Στη συνέχεια, αυτές οι δευτερεύουσες συστοιχίες ταξινομούνται ανεξάρτητα. Στο τέλος του αλγορίθμου, ολόκληρος ο πίνακας έχει ταξινομηθεί πλήρως.
Το Quicksort είναι ταχύτερο και λειτουργεί αποτελεσματικά για την ταξινόμηση δομών δεδομένων. Το Quicksort είναι ένας δημοφιλής αλγόριθμος ταξινόμησης και μερικές φορές προτιμάται ακόμη και από τον αλγόριθμο συγχώνευσης ταξινόμησης.
Στο επόμενο σεμινάριό μας, θα συζητήσουμε λεπτομερέστερα για την ταξινόμηση Shell.
=> Παρακολουθήστε την απλή σειρά εκπαίδευσης C ++ εδώ.
Συνιστώμενη ανάγνωση
- MongoDB Sort () Μέθοδος με παραδείγματα
- Unix Sort Command με Σύνταξη, Επιλογές και Παραδείγματα
- Συγχώνευση ταξινόμησης σε C ++ με παραδείγματα
- Ταξινόμηση σωρού σε C ++ με παραδείγματα
- Ταξινόμηση κελύφους σε C ++ με παραδείγματα
- Επιλογή Ταξινόμηση σε C ++ με παραδείγματα
- Ταξινόμηση Bubble σε C ++ με παραδείγματα
- Εισαγωγή Ταξινόμηση σε C ++ με παραδείγματα
