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

Ο τρόπος με τον οποίο λειτουργεί είναι με την χρησιμοποίηση της επαναλαμβανόμενης σύγκρισης και στην περίπτωση που χρειάζεται στην αντιμετάθεση των γειτονικών στοιχείων μέσα στον πίνακα.

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

Έστω λοιπόν ότι έχουμε τον παρακάτω πίνακα :

[5,1,4,2,8]

Πρώτο πέρασμα :
[5,1,4,2,8] -> [1,5,4,2,8] : Γίνεται αντιμετάθεση του 1 με το 5 αφού 5 > 1
[1,5,4,2,8] -> [1,4,5,2,8] : Γίνεται αντιμετάθεση του 5 με το 4 αφού 5 > 4
[1,4,5,2,8] -> [1,4,2,5,8] : Γίνεται αντιμετάθεση του 5 με το 2 αφού 5 > 2
[1,4,2,5,8]  -> [1,4,2,5,8] : Καμία αντιμετάθεση αφού 5 < 8

Δεύτερο πέρασμα :

[1,4,2,5,8]  -> [1,2,4,5,8] : Γίνεται αντιμετάθεση του 4 με το 2 αφού 4 > 2
[1,2,4,5,8]  -> [1,2,4,5,8] : Καμία αντιμετάθεση αφού 4 < 5
[1,2,4,5,8] -> [1,2,4,5,8] : Καμία αντιμετάθεση αφού 4 < 8

Ο πίνακας μας είναι ήδη ταξινομημένος όμως ο αλγόριθμος δεν το ξέρει και πρέπει να τρέξει για μία τελευταία φορά :

Τρίτο πέρασμα :
[1,2,4,5,8] -> [1,2,4,5,8] : Καμία αντιμετάθεση αφού 1 < 2
[1,2,4,5,8] -> [1,2,4,5,8] : Καμία αντιμετάθεση αφού 2 < 4
[1,2,4,5,8] -> [1,2,4,5,8] : Καμία αντιμετάθεση αφού 4 < 5
[1,2,4,5,8] -> [1,2,4,5,8] : Καμία αντιμετάθεση αφού 5 < 8

Κώδικας σε Python :

Παρακάτω θα υλοποιήσουμε τον παραπάνω αλγόριθμο με Python. Παρόλο που μπορεί να γίνει με δύο for θα τον υλοποίησουμε λίγο διαφορετικά.

def sort(arr):
    while True:
        corrected = False
        for i in range(0,len(arr)-1):
            if arr[i] > arr[i+1]:
                arr[i],arr[i+1] = arr[i+1],arr[i]
                #Uncomment την παρακάτω γραμμή για να δείτε τα βήματα 
                #print(arr)
                corrected = True
        if not corrected:
            return arr

#Καλύτερο Σενάριο O(n)
print(sort([1,2,3,4,5,6,7,8,9]))

#Καλύτερο Σενάριο Average O(n^2)
print(sort([7,5,3,4,8,2,6,1,9]))

#Χειρότερο Σενάριο O(n^2)
print(sort([9,8,7,6,5,4,3,2,1]))

Η λογική με την οποία υλοποιούμε τον αλγόριθμο είναι πώς τρέχουμε την for μέχρι να ταξινομηθεί ο πίνακας. Δεν κάνουμε προσπέλαση όλο τον πίνακα αλλά όπως αναφέραμε και πιο πάνω πηγαίνουμε μέχρι το προτελευταίο στοιχείο.

Κάθε φορά που πετυχαίνουμε μία αντιμετάθεση η Corrected γίνεται true και έτσι ξανά τρέχει η While η οποία στην συνέχει κάνει την Corrected σε False .

Όταν ο πίνακας ταξινομηθεί τότε η corrected θα παραμείνει false και αυτό θα σημαίνει την ολοκλήρωση της ταξινόμησης καθώς δεν θα έχουμε πετύχει καμία αντιμετάθεση.

Στα σχόλια του κώδικα μπορείτε να δείτε και τρία παραδείγματα σχετικά με το καλύτερο , το μέσο και το χειρότερο σενάριο.

Τον παραπάνω κώδικα μπορείτε να τον βρείτε στο github εδώ

Στο επόμενο tutorial θα εξετάσουμε τον αλγόριθμο της γρήγορης ταξινόμησης (quick sort) ο οποίος είναι γρηγορότερος