quicksort java algorithm
Αυτό το σεμινάριο εξηγεί τον αλγόριθμο Quicksort στην Java, τις απεικονίσεις του, την εφαρμογή QuickSort σε Java με τη βοήθεια παραδειγμάτων κώδικα:
Η τεχνική διαλογής Quicksort χρησιμοποιείται ευρέως σε εφαρμογές λογισμικού. Το Quicksort χρησιμοποιεί μια στρατηγική διαίρεσης και κατάκτησης όπως το είδος συγχώνευσης.
Στον αλγόριθμο quicksort, επιλέγεται πρώτα ένα ειδικό στοιχείο που ονομάζεται «pivot» και ο εν λόγω πίνακας ή λίστα χωρίζεται σε δύο υποσύνολα. Τα διαμερισμένα υποσύνολα ενδέχεται να έχουν ή όχι ίσο μέγεθος.
=> Διαβάστε ολόκληρη τη σειρά Easy Java Training.
Οι κατατμήσεις είναι τέτοιες που όλα τα στοιχεία λιγότερο από το στοιχείο περιστροφής είναι προς τα αριστερά του περιστρεφόμενου και τα στοιχεία μεγαλύτερα από τον άξονα βρίσκονται στα δεξιά του περιστροφικού άξονα. Η ρουτίνα Quicksort ταξινομεί αναδρομικά τις δύο δευτερεύουσες λίστες. Το Quicksort λειτουργεί αποτελεσματικά και ταχύτερα ακόμη και για μεγαλύτερες συστοιχίες ή λίστες.
η προεπιλεγμένη πύλη δεν είναι διαθέσιμη τα Windows 10 συνεχίζουν να συμβαίνουν
Τι θα μάθετε:
- Quicksort Partition Java
- Quicksort Αλγόριθμος Java
- Ψευδοκώδικας για γρήγορη ταξινόμηση
- Απεικόνιση
- Εφαρμογή Quicksort στην Java
- Συχνές Ερωτήσεις
- συμπέρασμα
- Συνιστώμενη ανάγνωση
Quicksort Partition Java
Η κατάτμηση είναι η βασική διαδικασία της τεχνικής Quicksort. Τι είναι λοιπόν το διαμέρισμα;
Δεδομένου ενός πίνακα A, επιλέγουμε μια τιμή x που ονομάζεται pivot έτσι ώστε όλα τα στοιχεία μικρότερα από το x να είναι πριν από το x και όλα τα στοιχεία μεγαλύτερα από το x είναι μετά το x.
Μια τιμή περιστροφής μπορεί να είναι οποιοδήποτε από τα ακόλουθα:
- Το πρώτο στοιχείο στον πίνακα
- Το τελευταίο στοιχείο στον πίνακα
- Το μεσαίο στοιχείο του πίνακα
- Οποιοδήποτε τυχαίο στοιχείο στον πίνακα
Αυτή η περιστρεφόμενη τιμή τοποθετείται στη συνέχεια στη σωστή θέση της στον πίνακα χωρίζοντας τον πίνακα. Έτσι, η έξοδος της διαδικασίας «διαμέρισης» είναι η τιμή περιστροφής στη σωστή θέση και τα στοιχεία λιγότερο από το περιστρεφόμενο στα αριστερά και τα στοιχεία μεγαλύτερα από έναν περιστρεφόμενο στα δεξιά.
Εξετάστε το παρακάτω διάγραμμα που εξηγεί τη διαδικασία διαμέρισης.
Το παραπάνω διάγραμμα δείχνει τη διαδικασία της κατάτμησης του πίνακα επιλέγοντας επανειλημμένα το τελευταίο στοιχείο του πίνακα ως άξονα. Σε κάθε επίπεδο, σημειώστε ότι χωρίζουμε τον πίνακα σε δύο δευτερεύουσες συστοιχίες τοποθετώντας τον άξονα στη σωστή του θέση.
Στη συνέχεια, παραθέτουμε τον αλγόριθμο και τον ψευδοκώδικα για τεχνική γρήγορης ταξινόμησης που περιλαμβάνει επίσης ρουτίνα διαμερισμάτων.
Quicksort Αλγόριθμος Java
Ο γενικός αλγόριθμος για γρήγορη ταξινόμηση δίνεται παρακάτω.
quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low Δίνεται παρακάτω ο ψευδοκώδικας για την τεχνική γρήγορης ταξινόμησης.
Ψευδοκώδικας για γρήγορη ταξινόμηση
Ακολουθεί ο ψευδοκώδικας για μια τεχνική γρήγορης ταξινόμησης. Λάβετε υπόψη ότι παρέχουμε τον ψευδοκώδικα για ρουτίνα γρήγορης ταξινόμησης και διαμέρισης.
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low Απεικόνιση
Ας δούμε την απεικόνιση του αλγορίθμου γρήγορης ταξινόμησης. Πάρτε ως παράδειγμα τον ακόλουθο πίνακα. Εδώ έχουμε επιλέξει το τελευταίο στοιχείο ως άξονα.
Όπως φαίνεται, το πρώτο στοιχείο είναι χαμηλό και το τελευταίο είναι υψηλό.
Όπως φαίνεται στην παραπάνω εικόνα, υπάρχουν δύο δείκτες, υψηλοί και χαμηλοί που δείχνουν αντίστοιχα το τελευταίο και το πρώτο στοιχείο του πίνακα. Και οι δύο αυτοί δείκτες μετακινούνται καθώς προχωρά η γρήγορη ταξινόμηση.
Όταν το στοιχείο που δείχνει ο χαμηλός δείκτης γίνεται μεγαλύτερο από το στοιχείο περιστροφής και το στοιχείο που δείχνει ο υψηλός δείκτης είναι μικρότερο από το στοιχείο περιστροφής, ανταλλάσσουμε τα στοιχεία που υποδεικνύονται από το χαμηλό και υψηλό δείκτη και κάθε δείκτης προχωρά κατά 1 θέση.
Τα παραπάνω βήματα εκτελούνται έως ότου και οι δύο δείκτες διασταυρώσουν ο ένας τον άλλο στη διάταξη. Μόλις διασχίσουν, το στοιχείο περιστροφής παίρνει την κατάλληλη θέση του στον πίνακα. Σε αυτό το σημείο, ο πίνακας χωρίζεται και τώρα μπορούμε να ταξινομήσουμε κάθε δευτερεύοντα πίνακα ανεξάρτητα εφαρμόζοντας αναδρομικά έναν αλγόριθμο γρήγορης ταξινόμησης σε κάθε υπο-πίνακα.
Εφαρμογή Quicksort στην Java
Η τεχνική QuickSort μπορεί να εφαρμοστεί σε Java χρησιμοποιώντας είτε επανάληψη είτε επανάληψη. Σε αυτήν την ενότητα, θα δούμε και τις δύο αυτές τεχνικές.
Αναδρομικό Quicksort
Γνωρίζουμε ότι η βασική τεχνική της γρήγορης ταξινόμησης που απεικονίζεται παραπάνω χρησιμοποιεί αναδρομή για την ταξινόμηση του πίνακα. Στην αναδρομική γρήγορη ταξινόμηση μετά την κατάτμηση του πίνακα, η ρουτίνα γρήγορης ταξινόμησης καλείται αναδρομικά για να ταξινομήσετε τις υπο-σειρές.
Η παρακάτω Εφαρμογή δείχνει την τεχνική γρήγορης ταξινόμησης χρησιμοποιώντας αναδρομή.
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j Παραγωγή:
Πρωτότυπη σειρά: (4, -1, 6, 8, 0, 5, -3)
Ταξινομημένη σειρά: (-3, -1, 0, 4, 5, 6, 8)
Επαναληπτικό Quicksort
Στην επαναληπτική γρήγορη ταξινόμηση, χρησιμοποιούμε τη βοηθητική στοίβα για να τοποθετήσουμε ενδιάμεσες παραμέτρους αντί να χρησιμοποιήσουμε επαναλαμβανόμενες και ταξινομημένες κατατμήσεις.
Το ακόλουθο πρόγραμμα Java εφαρμόζει επαναληπτική γρήγορη ταξινόμηση.
import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1 Παραγωγή:
Πρωτότυπη σειρά: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Ταξινομημένη σειρά: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)
Συχνές Ερωτήσεις
Ε # 1) Πώς λειτουργεί ένα Quicksort;
Απάντηση: Το Quicksort χρησιμοποιεί μια στρατηγική διαίρεσης και κατάκτησης. Το Quicksort χωρίζει πρώτα έναν πίνακα γύρω από ένα στοιχείο περιστροφής που έχει επιλεγεί και δημιουργεί υπο-πίνακες που ταξινομούνται αναδρομικά.
Q # 2) Ποια είναι η χρονική πολυπλοκότητα του Quicksort;
Απάντηση: Η χρονική πολυπλοκότητα της γρήγορης ταξινόμησης κατά μέσο όρο είναι O (nlogn). Στη χειρότερη περίπτωση, είναι O (n ^ 2) το ίδιο με το είδος επιλογής.
Q # 3) Πού χρησιμοποιείται το Quicksort;
Απάντηση: Το Quicksort χρησιμοποιείται κυρίως σε αναδρομικές εφαρμογές. Το Quicksort είναι μέρος της βιβλιοθήκης C. Επίσης, σχεδόν οι γλώσσες προγραμματισμού που χρησιμοποιούν ενσωματωμένη ταξινόμηση εφαρμόζουν γρήγορη ταξινόμηση.
Q # 4) Ποιο είναι το πλεονέκτημα του Quicksort;
Απάντηση:
- Το Quicksort είναι ένας αποτελεσματικός αλγόριθμος και μπορεί εύκολα να ταξινομήσει ακόμη και μια τεράστια λίστα στοιχείων.
- Είναι επιτόπιο είδος και ως εκ τούτου δεν χρειάζεται επιπλέον χώρο ή μνήμη.
- Χρησιμοποιείται ευρέως και παρέχει έναν αποτελεσματικό τρόπο ταξινόμησης συνόλων δεδομένων οποιουδήποτε μήκους.
Q # 5) Γιατί το Quicksort είναι καλύτερο από το είδος συγχώνευσης;
Απάντηση: Ο κύριος λόγος για τον οποίο η γρήγορη ταξινόμηση είναι καλύτερη από την ταξινόμηση συγχώνευσης είναι ότι η γρήγορη ταξινόμηση είναι η επιτόπια μέθοδο ταξινόμησης και δεν απαιτεί επιπλέον χώρο μνήμης. Η ταξινόμηση συγχώνευσης απαιτεί επιπλέον μνήμη για ενδιάμεση ταξινόμηση.
συμπέρασμα
Το Quicksort θεωρείται ως ο καλύτερος αλγόριθμος ταξινόμησης κυρίως λόγω της αποτελεσματικότητάς του να ταξινομήσει ακόμη και ένα τεράστιο σύνολο δεδομένων σε χρόνο O (nlogn).
δωρεάν εφαρμογή μετατροπέα youtube σε mp3
Το Quicksort είναι επίσης επιτόπιο είδος και δεν απαιτεί επιπλέον χώρο μνήμης. Σε αυτό το σεμινάριο, έχουμε δει την αναδρομική και επαναληπτική εφαρμογή του quicksort.
Στο επερχόμενο σεμινάριό μας, θα συνεχίσουμε με μεθόδους ταξινόμησης στην Java.
=> Ρίξτε μια ματιά στον οδηγό για αρχάριους Java εδώ.
Συνιστώμενη ανάγνωση
- Binary Search Algorithm In Java - Εφαρμογή & παραδείγματα
- Java Array - Πώς να εκτυπώσετε στοιχεία ενός πίνακα στην Java;
- Επιλογή ταξινόμησης σε Java - Αλγόριθμος επιλογής ταξινόμησης & παραδείγματα
- Τύποι δεδομένων Array - int Array, Double array, Array of Strings κ.λπ.
- Java Array - Δήλωση, δημιουργία και αρχικοποίηση μιας σειράς στην Java
- Εκπαιδευτικό πρόγραμμα JAVA για αρχάριους: 100+ πρακτικά εκπαιδευτικά βίντεο Java
- Java Copy Array: Πώς να αντιγράψετε / κλωνοποιήσετε μια σειρά στην Java
- Εκμάθηση μήκους σειράς Java με παραδείγματα κώδικα
