Πώς να εφαρμόσετε το QuickSort στην Java;

Αυτό το άρθρο θα σας παρουσιάσει έναν άλλο Αλγόριθμο Διαίρεσης και Κατάκτησης Ταξινόμησης που είναι το QuickSort In Java και θα το παρακολουθήσετε με μια επίδειξη.

Το QuickSort είναι ένας αλγόριθμος διαίρεσης & κατάκτησης. Στο παράδειγμα σχεδίασης αλγορίθμου Divide & Conquer, διαιρούμε τα προβλήματα σε υπο-προβλήματα αναδρομικά και στη συνέχεια επιλύουμε τα υπο-προβλήματα & επιτέλους συνδυάζουμε τις λύσεις για να βρούμε το τελικό αποτέλεσμα. Σε αυτό το άρθρο θα επικεντρωθούμε στο QuickSort In

Οι ακόλουθοι δείκτες θα καλυφθούν σε αυτό το άρθρο,





Ας ξεκινήσουμε!

Ένα πράγμα που πρέπει να θυμάστε κατά τη διαίρεση των προβλημάτων σε υπο-προβλήματα είναι ότι η δομή των υπο-προβλημάτων δεν αλλάζει από το αρχικό πρόβλημα.
Ο αλγόριθμος Divide & Conquer έχει 3 βήματα:



  • Διαίρεση: Σπάσιμο του προβλήματος σε υποπροβλήματα
  • Conquer: Επίλυση των υποπροβλημάτων αναδρομικά
  • Combine: Συνδυάζοντας τις λύσεις για να λάβετε το τελικό αποτέλεσμα

Εικόνα- Γρήγορη ταξινόμηση σε Java- Edureka

Υπάρχουν διάφοροι αλγόριθμοι που βασίζονται στο παράδειγμα διαίρεσης & κατάκτησης. Η γρήγορη ταξινόμηση και η συγχώνευση είναι μεταξύ αυτών.

Αν και η χειρότερη περίπτωση πολυπλοκότητας του 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- Edureka

Τώρα μετά την εκτέλεση του παραπάνω προγράμματος Java θα καταλάβατε πώς λειτουργεί το QuickSort και πώς να το εφαρμόσετε στην Java.Έτσι, έχουμε φτάσει στο τέλος αυτού του άρθρου σχετικά με το «Quicksort in Java». Αν θέλετε να μάθετε περισσότερα,δείτε το από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία μάθησης. Το μάθημα εκπαίδευσης και πιστοποίησης Java J2EE και SOA της Edureka έχει σχεδιαστεί για να σας εκπαιδεύσει τόσο για βασικές όσο και για προχωρημένες ιδέες Java μαζί με διάφορα πλαίσια Java όπως το Hibernate & Spring.

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