Δευτέρα 26 Νοεμβρίου 2007

Ενα τυχαίο γεγονός. Μέρος 1ο

Ενα συνηθισμένο φθινοπωρινό πρωϊνό, σε κάποια αίθουσα ελληνικού πανεπιστημίου, ο (συνήθως όχι και τόσο σχετικός με το θέμα) καθηγητής, εξηγεί στους τυχερούς φυτητές την τεχνική διαίρει και βασίλευε:

Καθηγητής: Στα προβλήματα ταξινόμησης γενικά θεωρούμε τα δεδομένα αποθηκευμένα σε ένα μονοδιάστατο πίνακα Τ, και θέλουμε να πάρουμε το αποτέλεσμα είτε στον Τ (επιθυμητό) είτε σε έναν άλλο πίνακα A. Γιατι προτιμούμε την πρώτη περίπτωση?

ΦΑ: Για να μην έχουμε δύο γράμματα.

Καθηγητής: Παιδάκι μου, πόσες φορές θα σου πω να μην πετάγεσαι? Οσο λιγότερο μιλάς τόσο καλύτερα είναι για σένα.

ΜετροΠοντικας: Γιατι χρειαζόμαστε λιγότερη memory, δηλαδή ο αλγόριθμός μας καταναλώνει λιγότερα resources.

Καθηγητής: Ευγε αγγλομαθή ποντικα. Και συνεχίζω:

Ενας απλός αλλά αργός τρόπος να ταξινομήσουμε δεδομένα είναι η InsertSort, η οποία εισάγει 1-1 τα στοιχεία του πίνακα Τ στον Α, τοποθετώντας πάντα στη (μέχρι εκείνη την ωρα) σωστή θέση.

Μοιαζει με τον τρόπο που ταξινομούμε τα χαρτιά της τράπουλας. Εστω οτι σηκώνουμε τα χαρτια: 6 8 4 5 9 3 2, με αυτή τη σειρά, ένα ένα. Και θέλουμε στο τέλος να τα κρατάμε σε αύξουσα σειρά, αριστερά το μικρότερο και δεξιά το μεγαλύτερο. Τι κάνουμε?

Kakaskimos: Σηκώνουμε το 6 και το κρατάμε,

Χαρτωσια6

σηκώνουμε το 8 και το τοποθετούμε δεξιά απο το 6

Χαρτωσια 68

σηκώνουμε το 4 και το τοποθετούμε πρώτο

Χαρτωσια 468

σηκωνουμε το 5 και το τοποθετούμε ανάμεσα στο 4 και το 6

Χαρτωσια 456 8

σηκωνουμε το 9 και το τοποθετούμε μετά το 8

Χαρτωσια 456 89

σηκωνουμε το 3 και το τοποθετούμε πριν απο το 4

Χαρτωσια 34 56 89

και στο τέλος σηκωνουμε το 2 και το τοποθετούμε πριν απο το 3

Χαρτωσια 2 34 56 89

Καθηγητής: Μπράβο παιδί μου. Την επόμενη φορά θα μας εξηγήσεις πως παίζεται η πρέφα.

Τι κάναμε λοιπόν? Ταξινομήσαμε τον πίνακα Τ,

Τ 684 593 2

φτιάχνοντας τον πίνακα Α:

A 234 568 9

Συνοπτικά: παίρνουμε ένα - ένα τα στοιχεία απο τον πίνακα εισόδου, και το τοποθετούμε στη σωστή θεση στον πίνακα εξόδου. Αν τύχει και η θέση είναι πιασμένη τι κάνουμε παιδί μου Τεμπέλη?

Τεμπέλης: Της κάνουμε μασάζ?

Καθηγητής: Καλά, συνέχισε τον ύπνο σου. Παιδι μου πόντικα?

ΜετροΠόντικας: We move τα στοιχεία που πρέπει.

Καθηγητής: Και ποια ειναι τα στοιχεία που πρέπει?

ΜετροΠόντικας: Αυτά που είναι μεγαλύτερα απο αυτό που προσπαθούμε να εισάγουμε.

Καθηγητής: Και πως ξέρουμε ποια είναι αυτά?

ΜετροΠόντικας: Αν θ η θέση του στοιχείου που θέλουμε να εισάγουμε, αυτά που βρίσκονται σε θέση μεγαλύτερη ή ίση της κ.

Καθηγητής: Για να δούμε λοιπον:

InsertSort(Τ : Πίνακας; ν : Ακέραιος) --> αποτέλεσμα Α Πίνακας
Για I απο 1 έως ν

θ = θέση του Τ[Ι] στον Α

Αντιγράφουμε τα Α[θ]..Α[κ] μια θέση δεξιά

Α[θ] = Τ[Ι]

Καθηγητής: Πως βρίσκουμε ποια είναι η θέση στην οποία πρέπει να μπει το εκάστοτε τρέχων στοιχείο?

ΜετροΠόντικας: Ψάχνουμε απο το Α[1] έως το Α[κ] μέχρι να βρούμε μεγαλύτερο στοιχείο απο το Τ[Ι]

Καθηγητής: Αρα για καθε στοιχείο που εισάγω παιδί μου πόσο χρόνο χρειάζομαι?

ΜετροΠόντικας: Ολο τα εύκολα με ρωτάτε: πρέπει να κανουμε θ συγκρίσεις και κ-θ μετακινήσεις. Οπότε συνολικά κ steps.

Καθηγητής: Κι αυτό πρέπει να το κάνουμε για καθε στοιχείο. Δηλαδή συνολικά θα πρέπει να κάνουμε 1 + 2 + 3 + ... + ν ΒΗΜΑΤΑ μετροΠόντικα (τον κοιτάζει με βλέμμα που εννοεί ότι αν ξαναπετάξει αγγλική κουβέντα, το μάθημα θα το περάσει αφού παρει σύνταξη). Αρα συνολικά θα χρειαστούμε χρόνο ν(ν+1)/2, όπου ν τα στοιχεία εισόδου. Αρα ο αλγόριθμός μας είναι το πολύ ευθέως ανάλογη της Ν2, δηλαδή Τ(Ν)=O(N2)

ΦΑ:Οπου Τ ο πίνακας εισόδου?

Καθηγητής: Δεν το γλυτώνω το εγκεφαλικό. Πως μπορείς παιδί μου να είσαι ΤΟΣΟ άσχετος? Λοιπον, αν δεν ξαναμιλήσεις σε όλο το εξάμηνο, θα σου προσθέσω σε ότι γράψεις στο τελικό μια μονάδα. (ούτως ή άλλως με 0+1 δεν περνάει το ζώον).

Διάλλειμα να συνέλθω απο το τούβλο που περασε ξυστά κι επανερχόμαστε με βελτιωμενο αλγόριθμο ταξινόμησης, την mergesort (γαμώτο, με κόλλησε ο πόντικας)

Συνεχίζεται (?)

6 σχόλια:

σορολόπ είπε...

Τα Depon που τα μοιράζετε?! :P

(δεν σχολιάζω τίποτα άλλο μια και θα είμαι εκτός θέματος και θα θυμώσει ο θεματοθέτης :)))

kakaskimos είπε...

Δεν θυμώνω με τα εκτός θέματος σχόλια.
Θες να γίνεις πιο συγκεκριμένη? Τι σε δυσκόλεψε? Η ταξινόμηση των χαρτιών της τράπουλας?
Γιατί εκτός αυτού και της insertSort (που είναι ΙΔΙΕΣ) υπάρχουν διάλογοι μεταξύ καθηγητή και φυ/οιτητών.

σορολόπ είπε...

Για να είμαι απόλυτα ειλικρινής δεν άντεξα μέχρι τέλους... αφού τα βρήκε ο κ. καθηγητής με τον μετροπόντικα.. έκανα κοπάνα και πήγα στην καντίνα για καφέ με έναν κούκλο συμφοιτητή μου :PP χαχαχα

diva είπε...

απαπα ζημιά..
:-)

kakaskimos είπε...

Ελπίζω να μην είναι μεγάλη η ζημιά. Είπαμε. Ο καθηγητής είναι άσχετος με το θέμα ...

diva είπε...

Ζημιά ταξινομημένη, ουκ έστι ζημιά
:-ρ