Algorithms Lesson 1: Bubblesort

Μάθημα 1ο: Αλγόριθμος Φυσαλίδας

Για την κατανόηση του παρόντος video απαιτείται βασική γνώση άλγεβρας

O Αλγόριθμος Φυσαλίδας είναι η απλούστερη διαδικασία ταξινόμησης

Σε αυτό το πλαίσιο η ταξινόμηση σημαίνει να βάζουμε σε σειρά

ένα πίνακα από δεδομένα όπως ακέραιοι

Αρχικά φανταστείτε ένα πίνακα με στοιχεία που θέλουμε να ταξινομίσουμε

Χρησιμοποιύμε έναν άδειο πίνακα για επίδειξη

Ο Αλγόριθμος Φυσαλίδας περιγράφεται ως εξής

Συγκρίνουμε τα δύο πρώτα στοιχεία του πίνακα και αν δεν είναι σε σειρά ανταλάζουμε τις θέσεις τους

Κάνουμε το ίδιο για τα ζεύγη γειτονικών στοιχείων του πίνακα μέχρι και το τελευταίο στοιχείο

Σε αυτό το σημείο το τελευταίο στοιχείο είναι το μεγαλύτερο του πίνακα

Στην συνέχεια επαναλαμβάνουμε την διαδικασία για όλα τα ζευγάρια πλην του τελευταίου στοιχείου

μέχρι ο πίνακας να είναι πλήρως ταξινομημένος

Τώρα γεμίζουμε τον πίνακα με στοιχεία για να δείξουμε την λειτουργία του αλγορίθμου

Ξεκινάμε συγκρίνοντας το 5 με το 9

Από την στιγμή που το 5 είναι μικρότερο του 9 δεν κάνουμε τίποτα

Στην συνέχεια συγκρίνουμε το 9 με το 2

Επειδή το 9 είναι μεγαλύτερο του 2 ανταλλάσουμε τα στοιχεία

Κάνουμε το ίδιο ώσπου το 9 που είναι το μεγαλύτερο στοιχείο να φτάσει στη τελευταία θέση

Αυτός είναι και ο λόγος που ο αλγόριθμος πήρε το όνομα φυσαλίδα

Όταν το 9 φτάσει στην τελευταία θέση

συνεχίζουμε με τα επόμενα περάσματα του αλγορίθμου και ταξινομούμαι τον πίνακα

Ο ψευδοκώδικας για τον αλγόριθμο Φυσαλίδας είναι αρκετά απλός

Μόνο αυτές οι 4 γραμμές που βλέπετε

Ο Αλγόριθμος Φυσαλίδας είναι αργός

Για να σας δείξουμε τι εννοούμε υπολογίζουμε την πολυπλοκότητά του

Υποθέστε ότι έχουμε έναν πίνακα ν στοιχείων

Στο πρώτο πέρασμα εκτελούμε ν-1 συγκρίσεις

για να πάμε το μεγαλύτερο στοιχείο στο τέλος του πίνακα

Στο επόμενο εκτελούμε ν-2 συκρίσεις

και συνεχίζοντας με τον ίδιο τρόπο παίρνουμε το ακόλουθο άθροισμα:

Συκρίσεις = (ν-1) + (ν-2) + ... + 1

Με μαθηματικές πράξεις το παραπάνω άθροισμα ισούται με ν(ν-1)/2 το οποίο είναι ίσο με ν^2/2 - ν/2

Για μεγάλες τιμές του ν, το ν^2 υπερισχύει από τους υπόλοιπους όρους

και λέμε ότι ο αλγόριθμος φυσαλίδας έχει πολυπλοκότητα της τάξης του ν^2