Bubble Αλγόριθμος ταξινόμησης σε Java: Πρόγραμμα ταξινόμησης πινάκων & Παράδειγμα
Τζέιμς Χάρτμαν
⚡ Έξυπνη Σύνοψη
Bubble Αλγόριθμος ταξινόμησης σε Java συγκρίνει επανειλημμένα γειτονικά στοιχεία πίνακα και τα ανταλλάσσει μέχρι να ταξινομηθεί η ακολουθία. Αυτό το άρθρο εξηγεί τον μηχανισμό λειτουργίας, τον ψευδοκώδικα, την πλήρη Java υλοποίηση, βελτιστοποιημένη παραλλαγή, ανάλυση πολυπλοκότητας και πρακτικές συγκρίσεις με άλλες τεχνικές ταξινόμησης.
Τι είναι Bubble Ταξινόμηση;
BubblΗ ηλεκτρονική ταξινόμηση είναι ένας απλός αλγόριθμος ταξινόμησης που βασίζεται σε συγκρίσεις και συγκρίνει το πρώτο στοιχείο του πίνακα με το επόμενο. Εάν το τρέχον στοιχείο του πίνακα είναι αριθμητικά μεγαλύτερο από το επόμενο, τα στοιχεία αντικαθίστανται. Ομοίως, ο αλγόριθμος θα διασχίσει ολόκληρο το στοιχείο του πίνακα.
Ο αλγόριθμος παίρνει το όνομά του από τον τρόπο με τον οποίο η μεγαλύτερη τιμή στην μη ταξινομημένη περιοχή ανεβαίνει σταθερά στην τελική της θέση, όπως μια φυσαλίδα που ανεβαίνει στην επιφάνεια του νερού. Μετά το πρώτο πλήρες πέρασμα, το μεγαλύτερο στοιχείο καταλαμβάνει τον τελευταίο δείκτη. Μετά το δεύτερο πέρασμα, το δεύτερο μεγαλύτερο στοιχείο κλειδώνει στη θέση του και η διαδικασία επαναλαμβάνεται μέχρι να ταξινομηθεί πλήρως ο πίνακας.
Σε αυτό το άρθρο, θα δημιουργήσουμε ένα Java πρόγραμμα προς εφαρμογή BubblΤαξινόμηση. Ελέγξτε την έξοδο του κώδικα που θα σας βοηθήσει να κατανοήσετε τη λογική του προγράμματος και, στη συνέχεια, εξετάστε τη βελτιστοποιημένη έκδοση και την ανάλυση πολυπλοκότητας που ακολουθεί.
Πώς λειτουργεί το BubblΛειτουργεί ο αλγόριθμος ηλεκτρονικής ταξινόμησης;
BubblΗ ηλεκτρονική ταξινόμηση λειτουργεί μέσω επαναλαμβανόμενων περασμάτων στον πίνακα. Κάθε πέρασμα περπατά από τον πρώτο δείκτη στο τέλος της περιοχής που δεν είναι ταξινομημένη τη δεδομένη στιγμή, συγκρίνοντας γειτονικές τιμές και ανταλλάσσονταςping τα όποτε εμφανίζονται με λάθος σειρά. Επειδή η μεγαλύτερη εναπομένουσα τιμή ταξιδεύει πάντα στην άκρη δεξιά της μη ταξινομημένης περιοχής, η περιοχή συρρικνώνεται κατά ακριβώς μία θέση μετά από κάθε πέρασμα.
Η πλήρης διαδικασία μπορεί να χωριστεί σε τέσσερα επαναλαμβανόμενα βήματα:
- Συγκρίνω: Εξετάστε το στοιχείο στον δείκτη j-1 σε σχέση με το στοιχείο στον δείκτη j.
- Ανταλαγή: Εάν το αριστερό στοιχείο είναι μεγαλύτερο από το δεξί στοιχείο, ανταλλάξτε τις δύο τιμές χρησιμοποιώντας μια προσωρινή μεταβλητή.
- Προκαταβολή: Μετακινήστε μία θέση προς τα δεξιά και επαναλάβετε μέχρι να φτάσετε στο τέλος της μη ταξινομημένης περιοχής.
- Επαναλαμβάνω: Ξεκινήστε ένα νέο πέρασμα πάνω από μια περιοχή που είναι κατά ένα στοιχείο μικρότερη και σταματήστε μετά από n-1 περάσματα ή όταν ένα πέρασμα δεν εκτελεί ανταλλαγές.
Ο παρακάτω πίνακας tracείναι ο πίνακας δειγμάτων {860, 8, 200, 9} που χρησιμοποιείται στο πρόγραμμα αργότερα σε αυτήν τη σελίδα. Δείχνει ακριβώς ποια τιμή καταλήγει στην τελική της θέση στο τέλος κάθε περάσματος.
| Πέρασμα | Πίνακας στην αρχή του περάσματος | Συγκρίσεις που πραγματοποιήθηκαν | Πίνακας στο τέλος του περάσματος | Στοιχείο κλειδωμένο |
|---|---|---|---|---|
| 1 | 860, 8, 200, 9 | 3 | 8, 200, 9, 860 | 860 |
| 2 | 8, 200, 9, 860 | 2 | 8, 9, 200, 860 | 200 |
| 3 | 8, 9, 200, 860 | 1 | 8, 9, 200, 860 | 9 |
| 4 | 8, 9, 200, 860 | 0 | 8, 9, 200, 860 | 8 |
Παρατηρήστε ότι το τρίτο πέρασμα εκτελεί μια σύγκριση αλλά όχι ανταλλαγή. Μια βελτιστοποιημένη υλοποίηση ανιχνεύει αυτήν την συνθήκη και σταματά αμέσως, η οποία είναι η πιο πολύτιμη βελτίωση που μπορείτε να εφαρμόσετε σε αυτόν τον αλγόριθμο.
BubblΨευδοκώδικας Αλγορίθμου Ταξινόμησης e
Πριν γράψετε Java σύνταξη, βοηθά στην έκφραση της λογικής σε ψευδοκώδικα ουδέτερης ως προς τη γλώσσα. Η παρακάτω έκδοση περιλαμβάνει τη σημαία πρόωρης εξόδου, επομένως καλύπτει τόσο την κλασική όσο και τη βελτιστοποιημένη συμπεριφορά.
procedure bubbleSort(array A, integer n) for i from 0 to n - 2 do swapped := false for j from 1 to n - i - 1 do // compare the adjacent pair if A[j - 1] > A[j] then swap A[j - 1] and A[j] swapped := true end if end for // no swap in a full pass means the array is sorted if swapped = false then break end if end for end procedure
Ο εξωτερικός βρόχος ελέγχει τον αριθμό των περασμάτων και ο εσωτερικός βρόχος ελέγχει τις συγκρίσεις μέσα σε ένα μόνο πέρασμα. Το άνω όριο του εσωτερικού βρόχου είναι n – i – 1 επειδή οι τελευταίες θέσεις i διατηρούν ήδη τις τελικές τους τιμές.
Java Πρόγραμμα προς εφαρμογή Bubble Ταξινόμηση
Το ακόλουθο πρόγραμμα ταξινομεί έναν ακέραιο πίνακα σε αύξουσα σειρά. Επιπλέον εντολές εκτύπωσης έχουν διατηρηθεί μέσα στους βρόχους σκόπιμα, επειδή η ανάγνωση του pass-by-pass tracΤο e είναι ο πιο γρήγορος τρόπος για έναν αρχάριο να καταλάβει πώς συσσωρεύονται οι ανταλλαγές.
package com.guru99; public class BubbleSort { public static void main(String[] args) { int arr[] = {860, 8, 200, 9}; System.out.println("---Array BEFORE Bubble Sort---"); printArray(arr); bubbleSort(arr); //sorting array elements using bubble sort System.out.println("---Array AFTER Bubble Sort---"); printArray(arr); } static void bubbleSort(int[] array) { int n = array.length; int temp = 0; for(int i = 0; i < n; i++) // Looping through the array length { System.out.println("Sort Pass Number " + (i + 1)); for(int j = 1; j < (n - i); j++) { System.out.println("Comparing " + array[j - 1] + " and " + array[j]); if(array[j - 1] > array[j]) { //swap elements temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; System.out.println(array[j] + " is greater than " + array[j - 1]); System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } } } static void printArray(int[] array){ for(int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Παραγωγή:
---Array BEFORE Bubble Sort--- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Swapping Elements: New Array After Swap 8 860 200 9 Comparing 860 and 200 860 is greater than 200 Swapping Elements: New Array After Swap 8 200 860 9 Comparing 860 and 9 860 is greater than 9 Swapping Elements: New Array After Swap 8 200 9 860 Sort Pass Number 2 Comparing 8 and 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 8 and 9 Sort Pass Number 4 ---Array AFTER Bubble Sort--- 8 9 200 860
Code εξήγηση: The Ταξινόμηση με φυσαλίδες Η μέθοδος λαμβάνει τον πίνακα μέσω αναφοράς, επομένως ο καλών βλέπει το ταξινομημένο αποτέλεσμα χωρίς καμία τιμή επιστροφής. Η μεταβλητή temp διατηρεί μία τιμή κατά την εναλλαγή τριών γραμμών, γι' αυτό και ο αλγόριθμος χρειάζεται μόνο O(1) επιπλέον μνήμη. Η έκφραση n – i Στη συνθήκη εσωτερικού βρόχου εγγυάται ότι οι ήδη ταξινομημένες θέσεις στην ουρά δεν θα επανεξεταστούν ποτέ.
βελτιστοποιημένη Bubble Ταξινόμηση προγράμματος σε Java
Το παραπάνω πρόγραμμα εκτελεί πάντα n-1 περάσματα, ακόμα και όταν ο πίνακας ταξινομείται νωρίς. Η προσθήκη μιας μόνο boolean σημαίας διορθώνει αυτήν την αναποτελεσματικότητα. Εάν ένα πλήρες πέρασμα ολοκληρωθεί χωρίς μία μόνο εναλλαγή, ο πίνακας είναι εγγυημένο ότι θα ταξινομηθεί και ο εξωτερικός βρόχος μπορεί να σταματήσει αμέσως.
package com.guru99; public class OptimizedBubbleSort { public static void main(String[] args) { int arr[] = {5, 12, 33, 47, 58}; bubbleSort(arr); System.out.println(java.util.Arrays.toString(arr)); } static void bubbleSort(int[] array) { int n = array.length; int passes = 0; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 1; j < n - i; j++) { if (array[j - 1] > array[j]) { int temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; swapped = true; } } passes++; // Early exit: the array is already sorted if (!swapped) { break; } } System.out.println("Passes executed: " + passes); } }
Παραγωγή:
Passes executed: 1 [5, 12, 33, 47, 58]
Ο πίνακας εισόδου ήταν ήδη ταξινομημένος, επομένως η βελτιστοποιημένη έκδοση ολοκληρώθηκε μετά από ένα μόνο πέρασμα αντί για τέσσερα. Σε σχεδόν ταξινομημένα δεδομένα, αυτή η αλλαγή μετατρέπει ένα τετραγωνικό φόρτο εργασίας σε σχεδόν γραμμικό, που είναι ο κύριος λόγος BubblΗ ταξινόμηση e εμφανίζεται ακόμα σε πραγματικό κώδικα κατά καιρούς.
Χρονική Πολυπλοκότητα και Χωρική Πολυπλοκότητα Bubble Ταξινόμηση
Η πολυπλοκότητα περιγράφει πώς ο χρόνος εκτέλεσης αυξάνεται καθώς αυξάνεται το μέγεθος της εισόδου. BubblΗ ταξινόμηση του αριθμού των συγκρίσεων στην μη βελτιστοποιημένη έκδοση είναι σταθερή στο n(n-1)/2, γεγονός που την τοποθετεί σταθερά στην τετραγωνική κλάση.
| σενάριο | Συνθήκη εισόδου | Χρόνος πολυπλοκότητας | Διαστημική πολυπλοκότητα |
|---|---|---|---|
| καλυτερα case | Ο πίνακας είναι ήδη ταξινομημένος, βελτιστοποιημένη έκδοση | O (n) | Ο (1) |
| Μέση περίπτωση | Στοιχεία σε τυχαία σειρά | O(n²) | Ο (1) |
| Χειρότερη περίπτωση | Ο πίνακας ταξινομήθηκε με αντίστροφη σειρά | O(n²) | Ο (1) |
Επειδή κάθε ανταλλαγή συμβαίνει μέσα στον αρχικό πίνακα και χρησιμοποιείται μόνο μία προσωρινή μεταβλητή, BubblΗ ταξινόμηση μέσω ηλεκτρονικού ταχυδρομείου (e Sort) είναι ένας αλγόριθμος in place με βοηθητικό χώρο O(1). Είναι επίσης μια σταθερή ταξινόμηση, που σημαίνει ότι δύο εγγραφές που κατέχουν το ίδιο κλειδί διατηρούν την αρχική τους σχετική σειρά μετά την ταξινόμηση.
Πλεονεκτήματα και μειονεκτήματα του Bubble Ταξινόμηση
Η κατανόηση και των δύο πλευρών σάς βοηθά να αποφασίσετε πότε ο αλγόριθμος είναι μια αποδεκτή επιλογή και πότε πρέπει να αντικατασταθεί.
Πλεονεκτήματα
- Απλότητα: Η λογική χωράει σε περίπου δέκα γραμμές, γεγονός που διευκολύνει τη σωστή γραφή υπό συνθήκες συνέντευξης.
- Λειτουργία επί τόπου: Δεν εκχωρείται βοηθητικός πίνακας, επομένως η χρήση μνήμης δεν αυξάνεται με το μέγεθος εισόδου.
- Σταθερότητα: Τα ίσα κλειδιά διατηρούν την αρχική τους σειρά, κάτι που έχει σημασία κατά την ταξινόμηση εγγραφών κατά δευτερεύον πεδίο.
- Πρώιμη ανίχνευση εξόδου: Η σημαία swapped αναγνωρίζει έναν ήδη ταξινομημένο πίνακα με ένα μόνο πέρασμα.
Μειονεκτήματα
- Τετραγωνική ανάπτυξη: Η ταξινόμηση 10,000 στοιχείων απαιτεί σχεδόν 50 εκατομμύρια συγκρίσεις στη χειρότερη περίπτωση.
- Ο/Η Excessive γράφει: Ο αλγόριθμος εκτελεί πολύ περισσότερες εναλλαγές από την Ταξινόμηση με Επιλογή, η οποία είναι δαπανηρή στη μνήμη με αργές λειτουργίες εγγραφής.
- Κακή επεκτασιμότητα: Τα φόρτα εργασίας παραγωγής σχεδόν πάντα ευνοούν τη μέθοδο Quicksort, Merge Sort ή την ενσωματωμένη μέθοδο Arrays.sort.
💡 Συμβουλές: Σε παραγωγή Java κωδικός, προτιμώ Arrays.sort () για πρωτόγονα και Συλλογές.sort() για λίστες. Και οι δύο χρησιμοποιούν εξαιρετικά συντονισμένους αλγόριθμους, Dual-Pivot Quicksort και TimSort αντίστοιχα, που ξεπερνούν σε απόδοση ένα χειρόγραφο Bubblε Ταξινόμηση κατά τάξεις μεγέθους.
BubblΗλεκτρονική Ταξινόμηση έναντι Άλλης Ταξινόμησης Algorithms
Ο παρακάτω πίνακας συγκρίνει BubblΤαξινομήστε με τις τεχνικές ταξινόμησης που συναντούν στη συνέχεια οι αρχάριοι, ώστε να μπορείτε να δείτε ακριβώς πού κερδίζει η καθεμία.
| Αλγόριθμος | καλυτερα Case | Μέση περίπτωση | Χειρότερη περίπτωση | Χώρος | Σταθερός |
|---|---|---|---|---|---|
| Bubble Ταξινόμηση | O (n) | O(n²) | O(n²) | Ο (1) | Ναι |
| Ταξινόμηση επιλογής | O(n²) | O(n²) | O(n²) | Ο (1) | Οχι |
| Ταξινόμηση εισαγωγής | O (n) | O(n²) | O(n²) | Ο (1) | Ναι |
| Γρήγορη ταξινόμηση | O (n log n) | O (n log n) | O(n²) | O (ημερολόγιο n) | Οχι |
| Ταξινόμηση σωρού | O (n log n) | O (n log n) | O (n log n) | Ο (1) | Οχι |
BubblΗ ταξινόμηση με εισαγωγή και η ταξινόμηση με εισαγωγή μοιράζονται την ίδια γραμμική βέλτιστη περίπτωση, αλλά η ταξινόμηση με εισαγωγή εκτελεί λιγότερες ανταλλαγές σε μερικώς ταξινομημένα δεδομένα. Η ταξινόμηση επιλογής εκτελεί πάντα ακριβώς n-1 ανταλλαγές, γεγονός που την καθιστά σεtractive όταν οι εγγραφές είναι ακριβές, αν και θυσιάζει τη σταθερότητα. Για οποιονδήποτε πίνακα μεγαλύτερο από μερικές εκατοντάδες στοιχεία, η Quicksort ή η Heap Sort είναι η σωστή επιλογή.
Μόλις εξοικειωθείτε με τα μοτίβα διέλευσης πινάκων που χρησιμοποιούνται εδώ, η ίδια δομή βρόχου εμφανίζεται σε πολλές κλασικές ασκήσεις όπως η Η σειρά Φιμπονάτσι στο Java και την Java πρόγραμμα παλίνδρομου. Reviewing Java συστοιχίες και το ευρύτερο Java φροντιστήριο θα ενισχύσει τα θεμελιώδη στοιχεία στα οποία βασίζεται αυτός ο αλγόριθμος.
