[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:10.50,0:00:13.49,Default,,0000,0000,0000,,Μάθημα 1ο: Αλγόριθμος Φυσαλίδας\N
Dialogue: 0,0:00:13.49,0:00:16.92,Default,,0000,0000,0000,,Για την κατανόηση του παρόντος video απαιτείται βασική γνώση άλγεβρας\N
Dialogue: 0,0:00:18.50,0:00:21.68,Default,,0000,0000,0000,,O Αλγόριθμος Φυσαλίδας είναι η απλούστερη διαδικασία ταξινόμησης\N
Dialogue: 0,0:00:22.29,0:00:24.56,Default,,0000,0000,0000,,Σε αυτό το πλαίσιο η ταξινόμηση σημαίνει να βάζουμε σε σειρά
Dialogue: 0,0:00:24.56,0:00:26.55,Default,,0000,0000,0000,,ένα πίνακα από δεδομένα όπως ακέραιοι\N
Dialogue: 0,0:00:27.78,0:00:31.66,Default,,0000,0000,0000,,Αρχικά φανταστείτε ένα πίνακα με στοιχεία που θέλουμε να ταξινομίσουμε
Dialogue: 0,0:00:32.31,0:00:35.15,Default,,0000,0000,0000,,Χρησιμοποιύμε έναν άδειο πίνακα για επίδειξη\N
Dialogue: 0,0:00:35.15,0:00:38.08,Default,,0000,0000,0000,,Ο Αλγόριθμος Φυσαλίδας περιγράφεται ως εξής
Dialogue: 0,0:00:39.17,0:00:43.67,Default,,0000,0000,0000,,Συγκρίνουμε τα δύο πρώτα στοιχεία του πίνακα και αν δεν είναι σε σειρά ανταλάζουμε τις θέσεις τους\N
Dialogue: 0,0:00:43.67,0:00:48.100,Default,,0000,0000,0000,,Κάνουμε το ίδιο για τα ζεύγη γειτονικών στοιχείων του πίνακα μέχρι και το τελευταίο στοιχείο\N
Dialogue: 0,0:00:48.100,0:00:53.03,Default,,0000,0000,0000,,Σε αυτό το σημείο το τελευταίο στοιχείο είναι το μεγαλύτερο του πίνακα\N
Dialogue: 0,0:00:53.25,0:00:57.47,Default,,0000,0000,0000,,Στην συνέχεια επαναλαμβάνουμε την διαδικασία για όλα τα ζευγάρια πλην του τελευταίου στοιχείου\N
Dialogue: 0,0:00:57.47,0:01:00.91,Default,,0000,0000,0000,,μέχρι ο πίνακας να είναι πλήρως ταξινομημένος\N
Dialogue: 0,0:01:07.08,0:01:11.73,Default,,0000,0000,0000,,Τώρα γεμίζουμε τον πίνακα με στοιχεία για να δείξουμε την λειτουργία του αλγορίθμου\N
Dialogue: 0,0:01:11.73,0:01:13.80,Default,,0000,0000,0000,,Ξεκινάμε συγκρίνοντας το 5 με το 9 \N
Dialogue: 0,0:01:13.80,0:01:17.36,Default,,0000,0000,0000,,Από την στιγμή που το 5 είναι μικρότερο του 9 δεν κάνουμε τίποτα\N
Dialogue: 0,0:01:17.36,0:01:20.03,Default,,0000,0000,0000,,Στην συνέχεια συγκρίνουμε το 9 με το 2\N
Dialogue: 0,0:01:20.03,0:01:23.58,Default,,0000,0000,0000,,Επειδή το 9 είναι μεγαλύτερο του 2 ανταλλάσουμε τα στοιχεία\N
Dialogue: 0,0:01:23.58,0:01:30.18,Default,,0000,0000,0000,,Κάνουμε το ίδιο ώσπου το 9 που είναι το μεγαλύτερο στοιχείο να φτάσει στη τελευταία θέση\N
Dialogue: 0,0:01:30.18,0:01:32.70,Default,,0000,0000,0000,,Αυτός είναι και ο λόγος που ο αλγόριθμος πήρε το όνομα φυσαλίδα
Dialogue: 0,0:01:32.70,0:01:34.85,Default,,0000,0000,0000,,Όταν το 9 φτάσει στην τελευταία θέση
Dialogue: 0,0:01:34.87,0:01:40.63,Default,,0000,0000,0000,,συνεχίζουμε με τα επόμενα περάσματα του αλγορίθμου και ταξινομούμαι τον πίνακα\N
Dialogue: 0,0:01:50.61,0:01:53.83,Default,,0000,0000,0000,,Ο ψευδοκώδικας για τον αλγόριθμο Φυσαλίδας είναι αρκετά απλός\N
Dialogue: 0,0:01:53.83,0:01:57.49,Default,,0000,0000,0000,,Μόνο αυτές οι 4 γραμμές που βλέπετε\N
Dialogue: 0,0:01:59.20,0:02:02.19,Default,,0000,0000,0000,,Ο Αλγόριθμος Φυσαλίδας είναι αργός\N
Dialogue: 0,0:02:02.19,0:02:06.18,Default,,0000,0000,0000,,Για να σας δείξουμε τι εννοούμε υπολογίζουμε την πολυπλοκότητά του\N
Dialogue: 0,0:02:06.18,0:02:09.15,Default,,0000,0000,0000,,Υποθέστε ότι έχουμε έναν πίνακα ν στοιχείων\N
Dialogue: 0,0:02:09.16,0:02:13.06,Default,,0000,0000,0000,,Στο πρώτο πέρασμα εκτελούμε ν-1 συγκρίσεις
Dialogue: 0,0:02:13.10,0:02:16.08,Default,,0000,0000,0000,,για να πάμε το μεγαλύτερο στοιχείο στο τέλος του πίνακα\N
Dialogue: 0,0:02:16.08,0:02:19.30,Default,,0000,0000,0000,,Στο επόμενο εκτελούμε ν-2 συκρίσεις
Dialogue: 0,0:02:19.30,0:02:21.71,Default,,0000,0000,0000,,και συνεχίζοντας με τον ίδιο τρόπο παίρνουμε το ακόλουθο άθροισμα:\N
Dialogue: 0,0:02:21.71,0:02:23.62,Default,,0000,0000,0000,,Συκρίσεις = (ν-1) + (ν-2) + ... + 1\N
Dialogue: 0,0:02:23.62,0:02:36.82,Default,,0000,0000,0000,,Με μαθηματικές πράξεις το παραπάνω άθροισμα ισούται με ν(ν-1)/2 το οποίο είναι ίσο με ν^2/2 - ν/2\N
Dialogue: 0,0:02:36.82,0:02:42.08,Default,,0000,0000,0000,,Για μεγάλες τιμές του ν, το ν^2 υπερισχύει από τους υπόλοιπους όρους\N
Dialogue: 0,0:02:42.08,0:02:47.94,Default,,0000,0000,0000,,και λέμε ότι ο αλγόριθμος φυσαλίδας έχει πολυπλοκότητα της τάξης του ν^2\N