Καθηγητής: Στα προβλήματα ταξινόμησης γενικά θεωρούμε τα δεδομένα αποθηκευμένα σε ένα μονοδιάστατο πίνακα Τ, και θέλουμε να πάρουμε το αποτέλεσμα είτε στον Τ (επιθυμητό) είτε σε έναν άλλο πίνακα A. Γιατι προτιμούμε την πρώτη περίπτωση?
ΦΑ: Για να μην έχουμε δύο γράμματα.
Καθηγητής: Παιδάκι μου, πόσες φορές θα σου πω να μην πετάγεσαι? Οσο λιγότερο μιλάς τόσο καλύτερα είναι για σένα.
ΜετροΠοντικας: Γιατι χρειαζόμαστε λιγότερη memory, δηλαδή ο αλγόριθμός μας καταναλώνει λιγότερα resources.
Καθηγητής: Ευγε αγγλομαθή ποντικα. Και συνεχίζω:
Ενας απλός αλλά αργός τρόπος να ταξινομήσουμε δεδομένα είναι η InsertSort, η οποία εισάγει 1-1 τα στοιχεία του πίνακα Τ στον Α, τοποθετώντας πάντα στη (μέχρι εκείνη την ωρα) σωστή θέση.
Μοιαζει με τον τρόπο που ταξινομούμε τα χαρτιά της τράπουλας. Εστω οτι σηκώνουμε τα χαρτια: 6 8 4 5 9 3 2, με αυτή τη σειρά, ένα ένα. Και θέλουμε στο τέλος να τα κρατάμε σε αύξουσα σειρά, αριστερά το μικρότερο και δεξιά το μεγαλύτερο. Τι κάνουμε?
Kakaskimos: Σηκώνουμε το 6 και το κρατάμε,
| Χαρτωσια | 6 |
σηκώνουμε το 8 και το τοποθετούμε δεξιά απο το 6
| Χαρτωσια | 6 | 8 |
σηκώνουμε το 4 και το τοποθετούμε πρώτο
| Χαρτωσια | 4 | 6 | 8 |
σηκωνουμε το 5 και το τοποθετούμε ανάμεσα στο 4 και το 6
| Χαρτωσια | 4 | 5 | 6 | 8 |
σηκωνουμε το 9 και το τοποθετούμε μετά το 8
| Χαρτωσια | 4 | 5 | 6 | 8 | 9 |
σηκωνουμε το 3 και το τοποθετούμε πριν απο το 4
| Χαρτωσια | 3 | 4 | 5 | 6 | 8 | 9 |
και στο τέλος σηκωνουμε το 2 και το τοποθετούμε πριν απο το 3
| Χαρτωσια | 2 | 3 | 4 | 5 | 6 | 8 | 9 |
Καθηγητής: Μπράβο παιδί μου. Την επόμενη φορά θα μας εξηγήσεις πως παίζεται η πρέφα.
Τι κάναμε λοιπόν? Ταξινομήσαμε τον πίνακα Τ,
| Τ | 6 | 8 | 4 | 5 | 9 | 3 | 2 |
φτιάχνοντας τον πίνακα Α:
| A | 2 | 3 | 4 | 5 | 6 | 8 | 9 |
Συνοπτικά: παίρνουμε ένα - ένα τα στοιχεία απο τον πίνακα εισόδου, και το τοποθετούμε στη σωστή θεση στον πίνακα εξόδου. Αν τύχει και η θέση είναι πιασμένη τι κάνουμε παιδί μου Τεμπέλη?
Τεμπέλης: Της κάνουμε μασάζ?
Καθηγητής: Καλά, συνέχισε τον ύπνο σου. Παιδι μου πόντικα?
ΜετροΠόντικας: We move τα στοιχεία που πρέπει.
Καθηγητής: Και ποια ειναι τα στοιχεία που πρέπει?
ΜετροΠόντικας: Αυτά που είναι μεγαλύτερα απο αυτό που προσπαθούμε να εισάγουμε.
Καθηγητής: Και πως ξέρουμε ποια είναι αυτά?
ΜετροΠόντικας: Αν θ η θέση του στοιχείου που θέλουμε να εισάγουμε, αυτά που βρίσκονται σε θέση μεγαλύτερη ή ίση της κ.
Καθηγητής: Για να δούμε λοιπον:
InsertSort(Τ : Πίνακας; ν : Ακέραιος) --> αποτέλεσμα Α Πίνακας
| Για I απο 1 έως ν | ||
| θ = θέση του Τ[Ι] στον Α | ||
| Αντιγράφουμε τα Α[θ]..Α[κ] μια θέση δεξιά | ||
| Α[θ] = Τ[Ι] | ||
Καθηγητής: Πως βρίσκουμε ποια είναι η θέση στην οποία πρέπει να μπει το εκάστοτε τρέχων στοιχείο?
ΜετροΠόντικας: Ψάχνουμε απο το Α[1] έως το Α[κ] μέχρι να βρούμε μεγαλύτερο στοιχείο απο το Τ[Ι]
Καθηγητής: Αρα για καθε στοιχείο που εισάγω παιδί μου πόσο χρόνο χρειάζομαι?
ΜετροΠόντικας: Ολο τα εύκολα με ρωτάτε: πρέπει να κανουμε θ συγκρίσεις και κ-θ μετακινήσεις. Οπότε συνολικά κ steps.
Καθηγητής: Κι αυτό πρέπει να το κάνουμε για καθε στοιχείο. Δηλαδή συνολικά θα πρέπει να κάνουμε 1 + 2 + 3 + ... + ν ΒΗΜΑΤΑ μετροΠόντικα (τον κοιτάζει με βλέμμα που εννοεί ότι αν ξαναπετάξει αγγλική κουβέντα, το μάθημα θα το περάσει αφού παρει σύνταξη). Αρα συνολικά θα χρειαστούμε χρόνο ν(ν+1)/2, όπου ν τα στοιχεία εισόδου. Αρα ο αλγόριθμός μας είναι το πολύ ευθέως ανάλογη της Ν2, δηλαδή Τ(Ν)=O(N2)
ΦΑ:Οπου Τ ο πίνακας εισόδου?
Καθηγητής: Δεν το γλυτώνω το εγκεφαλικό. Πως μπορείς παιδί μου να είσαι ΤΟΣΟ άσχετος? Λοιπον, αν δεν ξαναμιλήσεις σε όλο το εξάμηνο, θα σου προσθέσω σε ότι γράψεις στο τελικό μια μονάδα. (ούτως ή άλλως με 0+1 δεν περνάει το ζώον).
Διάλλειμα να συνέλθω απο το τούβλο που περασε ξυστά κι επανερχόμαστε με βελτιωμενο αλγόριθμο ταξινόμησης, την mergesort (γαμώτο, με κόλλησε ο πόντικας)
Συνεχίζεται (?)
