Ο ΝΤΑΒΙΝΤ ΤΡΕΖΕΓΚΕ ΠΛΗΣΙΑΣΕ ΤΟ ΤΑΧΥΤΕΡΟ ΧΑΤ ΤΡΙΚ Τα μοναστήρια έχουν ψυχή

Ταξινόμηση ευθείας ανταλλαγής

Παραλίγο να κάνει ρεκόρ!

ΠΑΡΑΣΚΕΥΗ ΚΑΤΗΜΕΡΤΖΗ

H μέθοδος της ταξινόμησης ευθείας ανταλλαγής (straight exchange sort) βασίζεται στην αρχή της σύγκρισης και ανταλλαγής ζευγών γειτονικών στοιχείων, μέχρις ότου διαταχθούν όλα τα στοιχεία.

Ένα από τα γρηγορότερα χατ τρικ στην ιστορία του καμπιονάτο πέτυχε ο Νταβίντ Τρεζεγκέ στο 1-3 της Γιουβέντους επί της Άσκολι. Η Κρήτη έχει τουλάχιστον 364 μοναστήρια, μεγάλα και μικρά, με τα μετόχια και την πολυτάραχη ιστορία τους.

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

Ο Γάλλος βρήκε δίχτυα τρεις φορές σε διάστημα 11 αγωνιστικών λεπτών, από το 7' ως το 18', αλλά παραδόξως αυτή δεν ήταν η ταχύτερη επίδοση, αφού δύο ποδοσφαιριστές στο παρελθόν τα έχουν καταφέρει καλύτερα… Συνδυάζοντας την αμεσότητα και την τεκμηρίωση, "Τα Μοναστήρια και Ερημητήρια της Κρήτης" αναπτύσσονται σ' ένα πλούσιο εικονογραφημένο δίτομο έργο 1.200 σελίδων, που βασίζεται σε πρωτογενή έρευνα: την περιήγηση και αυτοψία για τον εντοπισμό και των άγνωστων απόμακρων μνημείων, τη βουτιά σε χιλιάδες κιτρινισμένες σελίδες δυσεύρετων αρχείων και βιβλίων, την αποδελτίωση.

Αν ο πίνακας θεωρηθεί σε κατακόρυφη θέση αντί σε οριζόντια και οι ακέραιοι θεωρηθούν -επιστρατεύοντας αρκετή φαντασία -ως φυσαλίδες (bubbles) σε μία δεξαμενή νερού με βάρη σύμφωνα με την τιμή τους, τότε κάθε προσπέλαση στον πίνακα έχει ως αποτέλεσμα την άνοδο της φυσαλίδας στο κατάλληλο επίπεδο βάρους.

Το σχετικό ρεκόρ, άλλωστε, μοιάζει εξωπραγματικό κι αντέχει από το 1947.

Ο βραβευμένος από την Ακαδημία Αθηνών "Οδηγός του Ψιλάκη" μπαίνει τώρα στην τρίτη - μέσα σε δέκα χρόνια - έκδοσή του και ολοκληρώνεται με κάτι που έλειπε: το "ευρετήριο" των χιλιάδων αναφορών σε πρόσωπα, τοπωνύμια, κ.ά., που ήταν απαραίτητο για τους μελετητές της κρητολογίας.

Η μέθοδος είναι γνωστή ως ταξινόμηση φυσαλίδας (bubblesort).

Τότε, ο Βαλεντίνο Ματσόλα είχε σκοράρει τρεις φορές σε ισάριθμα λεπτά(!), από το 29' ως το 31' με την Τορίνο εναντίον της Βιτσέντζα.

Το συνέταξε η ιστορικός Τέχνης, Μίρκα Παλιούρα.

Δομές Δεδομένων δευτερεύουσας μνήμης Σε μεγάλες πρακτικές εμπορικές/ επιστημονικές εφαρμογές, το μέγεθος της κύριας μνήμης δεν επαρκεί για την αποθήκευση των δεδομένων. Στην περίπτωση αυτή χρησιμοποιούνται ειδικές δομές για την αποθήκευση των δεδομένων στη δευτερεύουσα μνήμη, δηλαδή κυρίως στο μαγνητικό δίσκο. Οι ειδικές αυτές δομές ονομάζονται αρχεία (files). Είναι γνωστό ότι μία σημαντική διαφορά μεταξύ κύριας μνήμης και μαγνητικού δίσκου είναι ότι στην περίπτωση του δίσκου, τα δεδομένα δεν χάνονται, αν διακοπεί η ηλεκτρική παροχή. Έτσι, τα δεδομένα των αρχείων διατηρούνται ακόμη και μετά τον τερματισμό ενός προγράμματος, κάτι που δεν συμβαίνει στην περίπτωση των δομών της κύριας μνήμης, όπως είναι οι πίνακες, όπου τα δεδομένα χάνονται όταν τελειώσει το πρόγραμμα. Τα στοιχεία ενός αρχείου ονομάζονται εγγραφές (records), όπου κάθε εγγραφή αποτελείται από ένα ή περισσότερα πεδία (fields), που ταυτοποιούν την εγγραφή, και από άλλα πεδία που περιγράφουν διάφορα χαρακτηριστικά της εγγραφής. Για παράδειγμα, έστω η εγγραφή ενός μαθητή με πεδία: Αριθμός Μητρώου, Ονοματεπώνυμο, Έτος Γέννησης, Τάξη, Τμήμα. Το πεδίο Αριθμός Μητρώου ταυτοποιεί την εγγραφή και ονομάζεται πρωτεύον κλειδί (primary key) ή απλά κλειδί. Το πεδίο Ονοματεπώνυμο επίσης ταυτοποιεί την εγγραφή και γι' αυτό αποκαλείται δευτερεύον κλειδί (secondary keys), αν υπάρχει πρωτεύον κλειδί. Το πρόβλημα της αναζήτησης (searching) μίας εγγραφής με βάση την τιμή του πρωτεύοντος ή ενός δευτερεύοντος κλειδιού σε αρχεία είναι ιδιαίτερα ενδιαφέρον, αν ληφθεί υπ' όψη η μεγάλη ποικιλία των χαρακτηριστικών τόσο της δομής (για παράδειγμα, στατική ή δυναμική, τρόπος οργάνωσης, μέσο αποθήκευσης κ.λπ.), του τύπου των δεδομένων (για παράδειγμα, ακέραιοι, κείμενο, χαρτογραφικά δεδομένα, χρονοσειρές κ.λπ.), όσο και της αναζήτησης (δηλαδή, με βάση το πρωτεύον ή το δευτερεύον κλειδί κλπ.).

Καλύτερη επίδοση από τον Τρεζεγκέ έχει επίσης ο θρυλικός Τζιουζέπε Μεάτσα, που χρειάστηκε 4' για να πετύχει χατ - τρικ για την Ίντερ επί της Ρόμα το 1930.

Είκοσι ολόκληρα χρόνια κράτησε η έρευνα.

Παράδειγμα.

Πάντως με τα τρία του γκολ επί της Άσκολι, ο "Τρεζεγκόλ" έφτασε τα 18 φέτος, απειλεί πλέον τον Λούκα Τόνι (21 γκολ) και διεκδικεί με αξιώσεις το "Χρυσό Παπούτσι".

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

Έστω ότι ο αρχικός πίνακας αποτελείται από εννέα κλειδιά τα εξής: 52, 12, 71, 56, 5, 10, 19, 90 και 45.

Ο Γάλλος, που είχε αναδειχθεί 1ος σκόρερ του καμπιονάτο και τη σεζόν 2001-02 (24 γκολ), μετρά πλέον 118 γκολ καριέρας με τη Γιούβε, της οποίας είναι 9ος σκόρερ διαχρονικά (1ος είναι ο Αλεσάντρο Ντελ Πιέρο με 188).

Αν σήμερα λειτουργούν στην Κρήτη 36 ακμαία μοναστήρια, υπήρξαν εποχές - κατά την Ενετοκρατία - που ζούσαν 8.000 καλόγηροι.

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

"Καλά είναι τα ρεκόρ, αλλά οι τίτλοι αξίζουν περισσότερο.

Οι σελίδες του βιβλίου δίνουν τον λόγο σ' αυτό τον άγνωστο πλούτο των προσωπικοτήτων, με δείγμα της γραφής, της σκέψης, της δράσης τους.

Κάθε φορά το ταξινομημένο τμήμα του πίνακα εμφανίζεται με χρώμα, ενώ τα στοιχεία που σαν φυσσαλίδες ανέρχονται μέσα στον πίνακα εντοπίζονται με το αντίστοιχο βέλος στα δεξιά τους.

Κι η Γιουβέντους διεκδικεί όλα τα τρόπαια", αρκέστηκε να πει ο 28χρονος Γάλλος διεθνής (60 συμμετοχές, 31 γκολ στους "τρικολόρ"), από τον οποίο λείπει μόνο ένα Τσάμπιονς λιγκ.

Και αυτό το τελευταίο στοιχείο δίνει στο έργο έναν αέρα ντοκουμέντου.

Κάθε φορά εμφανίζεται η τάξη της επανάληψης (i).

Σχ. 3.7. Ταξινόμηση φυσσαλίδας.

Η ταξινόμηση φυσσαλίδας υλοποιείται με τον επόμενο αλγόριθμο. Αλγόριθμος Φυσσαλίδα Δεδομένα // table, n // Για i από 2 μέχρι n Για j από n μέχρι i με_βήμα ­1 Αν table[j-1] > table[j] τότε αντιμετάθεσε table[j-1], table[j] Τέλος_αν Τέλος_επανάληψης Τέλος_επανάληψης Αποτελέσματα // table // Τέλος Φυσσαλίδα

Για την ταξινόμηση δεδομένων έχουν εκπονηθεί πάρα πολλοί αλγόριθμοι. Άλλοι σχετικά απλοί αλγόριθμοι είναι η ταξινόμηση με επιλογή και η ταξινόμηση με παρεμβολή. Ο πιο γρήγορος αλγόριθμος ταξινόμησης είναι η "γρήγορη ταξινόμηση" (quicksort). Η ταξινόμηση φυσαλίδας είναι ο πιο απλός και ταυτόχρονα ο πιο αργός αλγόριθμος ταξινόμησης.

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

Σημειώνεται ότι η εντολή "αντιμετάθεσε table[j-1], table[j]" ανταλλάσσει -το περιεχόμενο δύο θέσεων με τη βοήθεια μίας βοηθητικής θέσης. Εναλλακτικά αυτό μπορεί να αυτό μπορεί να γίνει με εξής τρεις εντολές. temptable[j-1] table[j-1]table[j] table[j]temp