Υπάρχει μια πληθώρα αλγορίθμων ταξινόμησης. Η εύρεση της κατάλληλης εφαρμογής για την εφαρμογή σας είναι μια εργασία που απαιτεί μια σύντομη κατανόηση παραγόντων όπως η απόδοση, η πολυπλοκότητα του χρόνου, το μήκος του κώδικα κ.λπ. ενός συγκεκριμένου αλγορίθμου. Σε αυτήν την ανάρτηση, θα ρίξουμε μια ματιά σε όλες τις βασικές έννοιες που απαιτούνται για την εφαρμογή του Quicksort σε C ++ με την ακόλουθη σειρά:
- Κατανόηση του αλγόριθμου Quicksort
- Ψευδοκώδικας για το Quicksort
- Πρόγραμμα Quicksort σε C ++
- Χρόνος πολυπλοκότητας Quicksort
Κατανόηση του αλγόριθμου Quicksort
Οπως ακριβώς Συγχώνευση ταξινόμησης Ο Quicksort ακολουθεί τη στρατηγική διαίρεσης και κατάκτησης. Χρησιμοποιώντας τη στρατηγική διαίρεσης και κατάκτησης, διαιρούμε το πρόβλημα σε πολλά υποπροβλήματα και τα επιλύουμε αναδρομικά. Πρώτον, θα κατανοήσουμε όλη τη διαδικασία βήμα προς βήμα και μετά από αυτό, με τη βοήθεια ενός παραδείγματος, θα αναπτύξουμε μια βαθιά κατανόηση της όλης διαδικασίας.
Κατ 'αρχάς, θα ζητήσουμε τον μη ταξινομημένο πίνακα από τον χρήστη.
Μόλις έχουμε τον μη ταξινομημένο πίνακα μας, πρέπει να επιλέξουμε μια συγκεντρωτική τιμή από τον πίνακα. Μπορούμε να επιλέξουμε οποιαδήποτε τιμή.
stl ταξινόμηση c ++
Μόλις επιλέξουμε το σημείο περιστροφής μετά από αυτό, πρέπει να τακτοποιήσουμε τα άλλα στοιχεία της συστοιχίας με τέτοιο τρόπο ώστε, όλα τα στοιχεία μικρότερα από την τιμή περιστροφής να τοποθετηθούν στα δεξιά της τιμής περιστροφής και όλα τα στοιχεία μεγαλύτερα από τον άξονα Η τιμή πρέπει να τοποθετηθεί στα δεξιά της αξίας περιστροφής.
Εκτελούμε το βήμα 3 έως ότου λάβουμε την ταξινομημένη σειρά μας.
Τώρα, ας εξετάσουμε ένα παράδειγμα και να εφαρμόσουμε τον αλγόριθμο και να δούμε πώς λειτουργεί.
Γεια σας [5, 4, 1, 11, 9, 6, 2, 3] για αυτό το παράδειγμα θα θεωρούμε πάντα τον άξονα ως το πιο σωστό στοιχείο της λίστας.
Ας περάσουμε σε κάθε βήμα και να κατανοήσουμε τη λογική που χρησιμοποιήσαμε για την επίλυση του προβλήματος.
Αρχικά, επιλέξαμε το «3» ως τον άξονα μας και τακτοποιήσαμε όλα τα στοιχεία κάτω από το «3» στα δεξιά και όλα τα στοιχεία μεγαλύτερα από το «3» προς τα δεξιά.
Σε αυτό το σημείο, έχουμε 2 υποπροβλήματα. Ας λύσουμε πρώτα το υποπρόβλημα στα δεξιά. Επιλέξαμε έναν ως τον άξονα μας και τοποθετήσαμε το «2» στα δεξιά.
Για να λύσουμε το δεύτερο υποπρόβλημα επιλέγουμε το «6» ως τον άξονα μας και τοποθετούμε τα στοιχεία όπως συζητήσαμε νωρίτερα.
περάστε με αναφορά σε java
Έχουμε 2 ακόμη υποπροβλήματα. Το πρώτο επιλύεται επιλέγοντας 4 ως άξονα και το δεύτερο λύεται επιλέγοντας 9 ως άξονα. Τέλος, έχουμε την ταξινομημένη σειρά μας με τα στοιχεία τοποθετημένα στο ευρετήριο υπογράμμισης.
Σημείωση- Το σημαντικό σημείο που πρέπει να καταλάβετε εδώ είναι ότι όλες οι λειτουργίες πραγματοποιούνται στον ίδιο πίνακα. Δεν δημιουργούνται νέες συστοιχίες.
Ψευδοκώδικας για Quicksort σε C ++
QuickSort (πίνακας [], start_index, end_index) {if (start_index Πρόγραμμα Quicksort σε C ++
Κατανοήσαμε τον αλγόριθμο και αναπτύξαμε μια βαθιά κατανόηση της λειτουργίας του αλγορίθμου. Ας εφαρμόσουμε το Quicksort στο C ++ και γράψτε ένα πρόγραμμα για να ταξινομήσετε έναν πίνακα.
#include χρησιμοποιώντας namespace std void swap_elements (int * a, int * b) {int temp = * a * a = * b * b = temp} int partition (int array [], int start_index, int end_index) {int pivot = πίνακας [end_index] int i = (start_index - 1) για (int j = start_index j<= end_index- 1 j++) { if (array[j] <= pivot) { i++ swap_elements(&array[i], &array[j]) } } swap_elements(&array[i + 1], &array[end_index]) return (i + 1) } void quickSort(int array[], int start_index, int end_index) { if (start_index < end_index) { int partition_index = partition(array, start_index, end_index) quickSort(array, start_index, partition_index - 1) quickSort(array, partition_index + 1, end_index) } } void printArray(int array[], int number) { int i cout<<'Sorted Array: ' for (i = 0 i < number i++) cout << array[i] << ' ' cout << endl } int main() { int Hello[30] int i int NumberofElements cout<>Κόστος NumberofElements<<'Enter the elements one by one: ' for(i=0i>Γεια σας [i]} quickSort (Hello, 0, NumberofElements-1) printArray (Hello, NumberofElements) επιστροφή 0} Παραγωγή:
Χρόνος πολυπλοκότητας
Ας μιλήσουμε για την πιο σημαντική πτυχή οποιουδήποτε αλγορίθμου ταξινόμησης, δηλαδή την πολυπλοκότητα του χρόνου. Μας λέει για την απόδοση του αλγορίθμου σε διάφορα σενάρια. Αυτές οι τιμές μπορούν να μας βοηθήσουν να αποφασίσουμε εάν μπορούμε να χρησιμοποιήσουμε αυτόν τον αλγόριθμο για την εφαρμογή μας.
- Καλύτερη περίπτωση- Επί)
- Μέση περίπτωση- (nlogn)
- Χειρότερη περίπτωση- Επί2)
Με αυτό, καταλήγουμε στο τέλος αυτού του άρθρου Quicksort στο C ++. Εάν θέλετε να μάθετε περισσότερα, ρίξτε μια ματιά στο από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία μάθησης. Το μάθημα εκπαίδευσης και πιστοποίησης Java J2EE και SOA της Edureka έχει σχεδιαστεί για να σας εκπαιδεύσει τόσο για βασικές όσο και για προχωρημένες ιδέες Java μαζί με διάφορα πλαίσια Java όπως το Hibernate & Spring.
Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του ιστολογίου και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.