bubble sort c with examples
Τεχνική ταξινόμησης Bubble σε C ++.
Το Bubble Sort είναι η απλούστερη από τις τεχνικές ταξινόμησης.
Στην τεχνική ταξινόμησης φυσαλίδων, καθένα από τα στοιχεία της λίστας συγκρίνεται με το παρακείμενο στοιχείο. Έτσι, εάν υπάρχουν n στοιχεία στη λίστα A, τότε το A [0] συγκρίνεται με το A [1], το A [1] συγκρίνεται με το A [2] και ούτω καθεξής.
Μετά τη σύγκριση εάν το πρώτο στοιχείο είναι μεγαλύτερο από το δεύτερο, τότε τα δύο στοιχεία ανταλλάσσονται.
=> Επισκεφθείτε εδώ για το πλήρες μάθημα C ++ από ειδικούς.
Τι θα μάθετε:
πώς να χρησιμοποιήσετε αρχεία torrent μετά τη λήψη
- Τεχνική ταξινόμησης φυσαλίδων
- Απεικόνιση
- Παράδειγμα C ++
- Παράδειγμα Java
- Ανάλυση πολυπλοκότητας του αλγόριθμου Ταξινόμησης φυσαλίδων
- συμπέρασμα
- Συνιστώμενη ανάγνωση
Τεχνική ταξινόμησης φυσαλίδων
Χρησιμοποιώντας την τεχνική ταξινόμησης φυσαλίδων, η ταξινόμηση γίνεται σε περάσματα ή επαναλήψεις. Έτσι, στο τέλος κάθε επανάληψης, το βαρύτερο στοιχείο τοποθετείται στη σωστή θέση του στη λίστα. Με άλλα λόγια, το μεγαλύτερο στοιχείο της λίστας ανεβαίνει.
Παρακάτω έχουμε δώσει έναν γενικό αλγόριθμο τεχνικής ταξινόμησης φυσαλίδων.
Γενικός αλγόριθμος
Βήμα 1 : Για i = 0 έως N-1 επαναλάβετε το Βήμα 2
Βήμα 2 : Για J = i + 1 έως N - επαναλαμβάνω
Βήμα 3 : αν A [J]> A [i]
Ανταλλαγή A [J] και A [i]
[Τέλος εσωτερικού για βρόχο]
[Τερματισμός εάν Outer for loop]
Βήμα 4 : Έξοδος
Εδώ είναι ένας ψευδοκώδικας για αλγόριθμο ταξινόμησης φυσαλίδων, όπου διασχίζουμε τη λίστα χρησιμοποιώντας δύο επαναληπτικούς βρόχους.
Στον πρώτο βρόχο, ξεκινάμε από το 0ουστοιχείο και στον επόμενο βρόχο, ξεκινάμε από ένα παρακείμενο στοιχείο. Στο σώμα του εσωτερικού βρόχου, συγκρίνουμε κάθε ένα από τα παρακείμενα στοιχεία και τα ανταλλάσσουμε εάν δεν είναι σωστά. Στο τέλος κάθε επανάληψης του εξωτερικού βρόχου, το βαρύτερο στοιχείο φουσκώνει στο τέλος.
Ψευδοκώδικας
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array[i-1] > array[i] then swap array[i-1] and array[i] swapped = true end if end for until not swapped end procedure
Το παραπάνω που δίνεται είναι ο ψευδοκώδικας για την τεχνική ταξινόμησης φυσαλίδων. Ας απεικονίσουμε τώρα αυτήν την τεχνική χρησιμοποιώντας μια λεπτομερή απεικόνιση.
Απεικόνιση
Παίρνουμε μια σειρά μεγέθους 5 και επεξηγούμε τον αλγόριθμο ταξινόμησης φυσαλίδων.
Η σειρά είναι πλήρως ταξινομημένη.
Η παραπάνω εικόνα μπορεί να συνοψιστεί σε μορφή πίνακα όπως φαίνεται παρακάτω:
Πέρασμα | Μη ταξινομημένη λίστα | σύγκριση | Ταξινομημένη λίστα |
---|---|---|---|
{5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
1 | {10,5,15,0,12} | {10.5} | {5,10,15,0,12} |
{5,10,15,0,12} | {10.15} | {5,10,15,0,12} | |
{5,10,15,0,12} | {15.0} | {5,10,0,15,12} | |
{5,10,0,15,12} | {15.12} | {5,10,0,12,15} | |
δύο | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
{5,10,0,12,15} | {10.0} | {5,0,10,12,15} | |
3 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
{5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
{5,0,10,12,15} | ΚΑΤΑΧΩΡΙΣΜΕΝΟ |
Όπως φαίνεται στην εικόνα, με κάθε πάσο, το μεγαλύτερο στοιχείο φουσκώνει μέχρι το τελευταίο ταξινομώντας έτσι τη λίστα με κάθε πάσο. Όπως αναφέρθηκε στην εισαγωγή, κάθε στοιχείο συγκρίνεται με το γειτονικό του στοιχείο και ανταλλάσσεται το ένα με το άλλο εάν δεν είναι σωστά.
Έτσι, όπως φαίνεται στην παραπάνω εικόνα, στο τέλος του πρώτου περάσματος, εάν ο πίνακας πρόκειται να ταξινομηθεί σε αύξουσα σειρά, το μεγαλύτερο στοιχείο τοποθετείται στο τέλος της λίστας. Για το δεύτερο πέρασμα, το δεύτερο μεγαλύτερο στοιχείο τοποθετείται στη δεύτερη τελευταία θέση στη λίστα και ούτω καθεξής.
Όταν φτάσουμε στο N-1 (όπου το N είναι ένας συνολικός αριθμός στοιχείων στη λίστα) περνά, θα έχουμε ολόκληρη τη λίστα ταξινομημένη.
πώς μπορώ να ανοίξω ένα αρχείο bin
Η τεχνική ταξινόμησης φυσαλίδων μπορεί να εφαρμοστεί σε οποιαδήποτε γλώσσα προγραμματισμού. Έχουμε εφαρμόσει τον αλγόριθμο ταξινόμησης φυσαλίδων χρησιμοποιώντας τη γλώσσα C ++ και Java παρακάτω.
Παράδειγμα C ++
Ας δούμε ένα παράδειγμα προγραμματισμού για να δείξουμε το είδος των φυσαλίδων.
#include using namespace std; int main () { int i, j,temp,pass=0; int a[10] = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < Παραγωγή:
Λίστα εισαγωγής…
10 2 0 14 43 25 18 1 5 45
Ταξινομημένη λίστα στοιχείων…
0 1 2 5 10 14 18 25 43 45
Αριθμός πάσων που λήφθηκαν για ταξινόμηση της λίστας: 10
Παράδειγμα Java
class Main { public static void main(String[] args) { int pass = 0; int[] a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a[i] + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a[i] Παραγωγή:
Και στα δύο προγράμματα, χρησιμοποιήσαμε μια σειρά από 10 στοιχεία και τα ταξινομούμε χρησιμοποιώντας την τεχνική ταξινόμησης φυσαλίδων. Και στα δύο προγράμματα, χρησιμοποιήσαμε δύο για βρόχους για να επαναλάβουμε τα παρακείμενα στοιχεία του πίνακα.
Στο τέλος κάθε περάσματος (εξωτερικός βρόχος), το μεγαλύτερο στοιχείο της συστοιχίας διοχετεύεται μέχρι το τέλος της συστοιχίας. Μετράμε επίσης τον αριθμό των περάσεων που απαιτούνται για την ταξινόμηση ολόκληρου του πίνακα.
Ανάλυση πολυπλοκότητας του αλγόριθμου Ταξινόμησης φυσαλίδων
Από τον ψευδο κώδικα και την εικόνα που έχουμε δει παραπάνω, σε είδος φούσκας, κάνουμε συγκρίσεις Ν-1 στο πρώτο πέρασμα, συγκρίσεις Ν-2 στο δεύτερο πέρασμα και ούτω καθεξής.
Ως εκ τούτου, ο συνολικός αριθμός συγκρίσεων στο είδος φυσαλίδων είναι:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= Ν (Ν-1) / 2
= O (νδύο) => Χρονική πολυπλοκότητα της τεχνικής ταξινόμησης φυσαλίδων
Έτσι, οι διάφορες πολυπλοκότητες για την τεχνική ταξινόμησης φυσαλίδων δίνονται παρακάτω:
Χειρότερη περίπτωση πολυπλοκότητας Ο (ν 2) Βέλτιστη πολυπλοκότητα χρόνου Επί) Μέσος χρόνος πολυπλοκότητας Ο (ν 2) Διαστημική πολυπλοκότητα Ο (1)
Η τεχνική ταξινόμησης φυσαλίδων απαιτεί μόνο έναν επιπλέον χώρο μνήμης για τη μεταβλητή temp για τη διευκόλυνση της ανταλλαγής. Ως εκ τούτου, η πολυπλοκότητα του διαστήματος για τον αλγόριθμο ταξινόμησης φυσαλίδων είναι O (1).
Σημειώστε ότι η καλύτερη πολυπλοκότητα χρόνου για την τεχνική ταξινόμησης φυσαλίδων θα είναι όταν η λίστα έχει ήδη ταξινομηθεί και ότι θα είναι O (n).
συμπέρασμα
Το κύριο πλεονέκτημα του Bubble Sort είναι η απλότητα του αλγορίθμου. Στην ταξινόμηση φυσαλίδων, με κάθε πάσο, το μεγαλύτερο στοιχείο βράζει μέχρι το τέλος της λίστας εάν ο πίνακας ταξινομηθεί σε αύξουσα σειρά.
Ομοίως για τη λίστα που θα ταξινομηθεί σε φθίνουσα σειρά, το μικρότερο στοιχείο θα βρίσκεται στη σωστή θέση του στο τέλος κάθε πάσου.
Όντας η πιο απλή και εύκολη στην εφαρμογή τεχνική διαλογής, η ταξινόμηση φυσαλίδων συνήθως χρησιμοποιείται για την εισαγωγή της ταξινόμησης στο κοινό. Δεύτερον, η ταξινόμηση φυσαλίδων χρησιμοποιείται επίσης σε εφαρμογές όπως γραφικά υπολογιστών όπου η πλήρωση των άκρων πολυγώνου, κ.λπ. απαιτούν ταξινόμηση φυσαλίδων για ταξινόμηση των κορυφών που ευθυγραμμίζουν το πολύγωνο.
youtube σε mp3 περισσότερο από 90 λεπτά
Στο επερχόμενο σεμινάριό μας, θα μάθουμε λεπτομερώς για την επιλογή Ταξινόμηση.
=> Επισκεφθείτε εδώ για να μάθετε C ++ από το μηδέν.
Συνιστώμενη ανάγνωση
- Ταξινόμηση κελύφους σε C ++ με παραδείγματα
- Επιλογή Ταξινόμηση σε C ++ με παραδείγματα
- MongoDB Sort () Μέθοδος με παραδείγματα
- Unix Sort Command με Σύνταξη, Επιλογές και Παραδείγματα
- Εισαγωγή Ταξινόμηση σε C ++ με παραδείγματα
- Συγχώνευση ταξινόμησης σε C ++ με παραδείγματα
- Ταξινόμηση σωρού σε C ++ με παραδείγματα
- Γρήγορη ταξινόμηση σε C ++ με παραδείγματα