Τι είναι ο αλγόριθμος ταξινόμησης με φυσαλίδες [Επεξήγηση με παραδείγματα]

Η ταξινόμηση με φυσαλίδες είναι ένας από τους απλούστερους αλγόριθμους ταξινόμησης που επαναλαμβάνεται μέσω του δεδομένου πίνακα και συγκρίνει γειτονικά στοιχεία. Εάν τα στοιχεία είναι σε λάθος σειρά, ανταλλάσσονται για να φέρουν τη σωστή σειρά. Αυτή η διαδικασία συνεχίζεται μέχρι να ταξινομηθεί ολόκληρος ο πίνακας.

Αλγόριθμος:

Βήμα 1:Επαναλάβετε τον πίνακα πολλές φορές

Σε κάθε επανάληψη, συγκρίνετε γειτονικά στοιχεία (i και i + 1)

Βήμα 2:Εάν το τρέχον στοιχείο (i) είναι μεγαλύτερο από το επόμενο στοιχείο (i + 1), αλλάξτε το

Επαναλάβετε αυτή τη διαδικασία μέχρι να ταξινομηθεί ολόκληρος ο πίνακας

Χρονική πολυπλοκότητα:

O(n^2), αφού επαναλαμβάνει μέσα από τον πίνακα πολλές φορές και εκτελεί συγκρίσεις και εναλλαγές σε κάθε επανάληψη.

Παράδειγμα κώδικα στην Python:

def bubble_sort(arr):

για i στο εύρος (len(arr) - 1):

# Επαναλάβετε μέσα από τον πίνακα για να συγκρίνετε γειτονικά στοιχεία

για j στην περιοχή (len(arr) - 1 - i):

# Συγκρίνετε το τρέχον στοιχείο με το επόμενο στοιχείο

αν arr[j]> arr[j + 1]:

# Αλλάξτε τα στοιχεία εάν είναι σε λάθος σειρά

arr[j], arr[j + 1] =arr[j + 1], arr[j]

# Επιστρέψτε τον ταξινομημένο πίνακα

επιστροφή αρ

Παράδειγμα:

Εισαγωγή:

[5, 3, 1, 2, 4]

Παραγωγή:

[1, 2, 3, 4, 5]

Ο αλγόριθμος ταξινόμησης με φυσαλίδες επαναλαμβάνεται μέσω του πίνακα και συγκρίνει γειτονικά στοιχεία. Αν είναι σε λάθος σειρά, ανταλλάσσονται. Αυτή η διαδικασία επαναλαμβάνεται μέχρι να ταξινομηθεί ολόκληρος ο πίνακας.

Δείτε πώς λειτουργεί ο αλγόριθμος σε αυτό το παράδειγμα:

Επανάληψη 1:

- Συγκρίνετε 5 και 3:Ανταλλάξτε τα αφού το 5 είναι μεγαλύτερο από το 3.

- Συγκρίνετε 3 και 1:Ανταλλάξτε τα αφού το 3 είναι μεγαλύτερο από το 1.

- Συγκρίνετε 2 και 4:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Ο πίνακας γίνεται:[3, 1, 2, 4, 5].

Επανάληψη 2:

- Συγκρίνετε 3 και 1:Ανταλλάξτε τα αφού το 3 είναι μεγαλύτερο από το 1.

- Συγκρίνετε 1 και 2:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Συγκρίνετε 2 και 4:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Ο πίνακας γίνεται:[1, 2, 3, 4, 5].

Επανάληψη 3:

- Συγκρίνετε 1 και 2:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Συγκρίνετε 2 και 3:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Συγκρίνετε 3 και 4:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Ο πίνακας γίνεται:[1, 2, 3, 4, 5].

Επανάληψη 4:

- Συγκρίνετε 1 και 2:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Συγκρίνετε 2 και 3:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Συγκρίνετε 3 και 4:Δεν χρειάζεται ανταλλαγή αφού είναι στη σωστή σειρά.

- Ο πίνακας παραμένει αμετάβλητος.

Μετά την τέταρτη επανάληψη, ο πίνακας ταξινομείται με αύξουσα σειρά:[1, 2, 3, 4, 5].