Το QuickSort είναι ένας αλγόριθμος διαίρεσης & κατάκτησης. Στο παράδειγμα σχεδίασης αλγορίθμου Divide & Conquer, διαιρούμε τα προβλήματα σε υπο-προβλήματα αναδρομικά και στη συνέχεια επιλύουμε τα υπο-προβλήματα & επιτέλους συνδυάζουμε τις λύσεις για να βρούμε το τελικό αποτέλεσμα. Σε αυτό το άρθρο θα επικεντρωθούμε στο QuickSort In
Οι ακόλουθοι δείκτες θα καλυφθούν σε αυτό το άρθρο,
Ας ξεκινήσουμε!
Ένα πράγμα που πρέπει να θυμάστε κατά τη διαίρεση των προβλημάτων σε υπο-προβλήματα είναι ότι η δομή των υπο-προβλημάτων δεν αλλάζει από το αρχικό πρόβλημα.
Ο αλγόριθμος Divide & Conquer έχει 3 βήματα:
- Διαίρεση: Σπάσιμο του προβλήματος σε υποπροβλήματα
- Conquer: Επίλυση των υποπροβλημάτων αναδρομικά
- Combine: Συνδυάζοντας τις λύσεις για να λάβετε το τελικό αποτέλεσμα
Υπάρχουν διάφοροι αλγόριθμοι που βασίζονται στο παράδειγμα διαίρεσης & κατάκτησης. Η γρήγορη ταξινόμηση και η συγχώνευση είναι μεταξύ αυτών.
Αν και η χειρότερη περίπτωση πολυπλοκότητας του QuickSort είναι O (n2) που είναι κάτι περισσότερο από πολλούς άλλους αλγόριθμους ταξινόμησης όπως Merge Sort και Heap Sort, το QuickSort είναι ταχύτερο στην πράξη, επειδή ο εσωτερικός βρόχος του μπορεί να εφαρμοστεί αποτελεσματικά στις περισσότερες αρχιτεκτονικές και στις περισσότερες δεδομένα πραγματικού κόσμου.
Ας μιλήσουμε για την εφαρμογή του αλγορίθμου γρήγορης ταξινόμησης. Οι αλγόριθμοι Quicksort λαμβάνουν ένα στοιχείο περιστροφής και χωρίζουν τον πίνακα γύρω από το περιστρεφόμενο στοιχείο. Υπάρχουν πολλές παραλλαγές του Quicksot που εξαρτάται από τον τρόπο επιλογής του στοιχείου περιστροφής. Υπάρχουν πολλοί τρόποι για να επιλέξετε το στοιχείο περιστροφής:
- Επιλέγοντας το πρώτο στοιχείο
- Επιλέξτε το τελευταίο στοιχείο
- Επιλογή τυχαίου στοιχείου
- Επιλογή μέσου στοιχείου
Το επόμενο σημαντικό πράγμα που πρέπει να καταλάβετε είναι, η συνάρτηση partition () στον αλγόριθμο γρήγορης ταξινόμησης. Λειτουργία διαμέρισης για λήψη στοιχείου περιστροφής, τοποθέτηση στη σωστή θέση, μετακίνηση όλων των στοιχείων μικρότερων από το στοιχείο περιστροφής προς τα αριστερά & όλων των στοιχείων μεγαλύτερων προς τα δεξιά. Το Quicksort απαιτεί γραμμικό χρόνο για να το κάνει.
Στη συνέχεια, ο πίνακας χωρίζεται σε δύο μέρη από το στοιχείο περιστροφής (δηλαδή στοιχεία μικρότερα από το περιστρεφόμενο και στοιχεία μεγαλύτερα από το περιστρεφόμενο) και οι δύο πίνακες ταξινομούνται αναδρομικά χρησιμοποιώντας αλγόριθμο Quicksort.
Τώρα που κατανοούμε τη λειτουργία του αλγορίθμου QuickSort. Ας καταλάβουμε πώς να εφαρμόσουμε τον αλγόριθμο Quicksort στην Java.
Γρήγορη ταξινόμηση Λειτουργία:
/ * Η λειτουργία Quicksort χρειάζεται τον πίνακα να ταξινομηθεί με τον χαμηλότερο & υψηλότερο δείκτη * /
κενή ταξινόμηση (int arr [], int lowIndex, int highIndex) {// Μέχρι lowIndex = highIndex if (lowIndexΤώρα ας δούμε τον κώδικα διαμέρισης για να καταλάβουμε πώς λειτουργεί.
Χώρισμα Κώδικας
Στον κώδικα διαμέρισης, θα επιλέξουμε το τελευταίο στοιχείο ως στοιχείο περιστροφής. Διασχίζουμε τον πλήρη πίνακα (δηλαδή χρησιμοποιώντας τη μεταβλητή j στην περίπτωσή μας). Παρακολουθούμε το τελευταίο μικρότερο στοιχείο του πίνακα (δηλαδή χρησιμοποιώντας τη μεταβλητή i στην περίπτωσή μας). Εάν εντοπίσουμε οποιοδήποτε στοιχείο μικρότερο από το άξονα, μετακινούμε το στοιχείο εναλλαγής ρεύματος a [j] με arr [i], αλλιώς συνεχίζουμε να διασχίζουμε.
int partition (int arr [], int lowIndex, int highIndex) {// Κάνοντας το τελευταίο στοιχείο ως pivot int pivot = arr [highIndex] // Χρησιμοποιώντας το i για να παρακολουθώ μικρότερα στοιχεία από το pivot int i = (lowIndex-1) για (int j = lowIndex jΤώρα που έχετε κατανοήσει τη λειτουργία Quicksort & partition, ας ρίξουμε μια γρήγορη ματιά στον πλήρη κώδικα
Γρήγορη ταξινόμηση Κωδικός Java
κλάση QuickSort {// Μέθοδος κατάτμησης int διαμέρισμα (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) για (int j = lowIndex j// Μέθοδος ταξινόμησης
κενή ταξινόμηση (int arr [], int lowIndex, int highIndex) {if (lowIndex// Μέθοδος εκτύπωσης πίνακα
static void printArray (int arr []) {int n = arr.length για (int i = 0 i// Κύρια μέθοδος
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = νέο QuickSort () ob.sort (arr, 0, n-1) System.out.println ('sorted array') printArray (arr)}} Παραγωγή:
java ξεφύγει από μια μέθοδο
Τώρα μετά την εκτέλεση του παραπάνω προγράμματος Java θα καταλάβατε πώς λειτουργεί το QuickSort και πώς να το εφαρμόσετε στην Java.Έτσι, έχουμε φτάσει στο τέλος αυτού του άρθρου σχετικά με το «Quicksort in Java». Αν θέλετε να μάθετε περισσότερα,δείτε το από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία μάθησης. Το μάθημα εκπαίδευσης και πιστοποίησης Java J2EE και SOA της Edureka έχει σχεδιαστεί για να σας εκπαιδεύσει τόσο για βασικές όσο και για προχωρημένες ιδέες Java μαζί με διάφορα πλαίσια Java όπως το Hibernate & Spring.
Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του ιστολογίου και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.