Αναζήτηση και ταξινόμηση
Κεφ. 3 §3.6–3.7 · Σειριακή αναζήτηση, ταξινόμηση ευθείας ανταλλαγής
Ψάχνεις ένα όνομα σε μια ανακατεμένη λίστα 500 ονομάτων: δεν έχεις άλλη επιλογή από το να τα κοιτάξεις ένα ένα. Αν όμως τα ονόματα είναι σε αλφαβητική σειρά, το βρίσκεις σε λίγα δευτερόλεπτα.
Αναζήτηση και ταξινόμηση είναι οι δύο πιο συχνές λειτουργίες σε δομές δεδομένων — και οι δύο αλγόριθμοι που γράφεις σχεδόν σε κάθε Θέμα Δ.
Σειριακή αναζήτηση
Στη σειριακή (γραμμική) αναζήτηση εξετάζουμε τα στοιχεία του πίνακα ένα προς ένα, από το πρώτο, μέχρι να βρεθεί το ζητούμενο στοιχείο (κλειδί) ή να τελειώσει ο πίνακας.
Είναι η πιο απλή αλλά και η λιγότερο αποδοτική μέθοδος. Η χρήση της δικαιολογείται όταν:
- ο πίνακας είναι μη ταξινομημένος,
- ο πίνακας είναι μικρού μεγέθους,
- η αναζήτηση γίνεται σπάνια.
Για πίνακα Ν στοιχείων, στη χειρότερη περίπτωση (το κλειδί είναι τελευταίο ή δεν υπάρχει) χρειάζονται Ν συγκρίσεις.
Αλγόριθμος σειριακής αναζήτησης (πίνακας Α[Ν], κλειδί κλ)
βρεθηκε ← ΨΕΥΔΗΣ θεση ← 0 i ← 1 ΟΣΟ i <= Ν ΚΑΙ βρεθηκε = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ ΑΝ Α[i] = κλ ΤΟΤΕ βρεθηκε ← ΑΛΗΘΗΣ θεση ← i ΑΛΛΙΩΣ i ← i + 1 ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ βρεθηκε = ΑΛΗΘΗΣ ΤΟΤΕ ΓΡΑΨΕ 'Βρέθηκε στη θέση ', θεση ΑΛΛΙΩΣ ΓΡΑΨΕ 'Δεν βρέθηκε' ΤΕΛΟΣ_ΑΝ
Η λογική μεταβλητή βρεθηκε σταματά την αναζήτηση μόλις βρεθεί το κλειδί. Χρησιμοποιούμε ΟΣΟ και όχι ΓΙΑ, γιατί δεν ξέρουμε από πριν πόσες συγκρίσεις θα γίνουν.
Σε ποια περίπτωση δεν δικαιολογείται η σειριακή αναζήτηση;
Ταξινόμηση ευθείας ανταλλαγής (φυσαλίδα)
Ταξινόμηση είναι η διάταξη των στοιχείων σε αύξουσα ή φθίνουσα σειρά. Η απλούστερη μέθοδος είναι η ταξινόμηση ευθείας ανταλλαγής (bubble sort): συγκρίνουμε διαδοχικά ζεύγη γειτονικών στοιχείων και, αν δεν είναι στη σωστή σειρά, τα αντιμεταθέτουμε.
Στην εκδοχή του βιβλίου η σάρωση γίνεται από το τέλος προς την αρχή: σε κάθε πέρασμα το μικρότερο από τα αταξινόμητα στοιχεία «ανεβαίνει» σαν φυσαλίδα στη θέση του, στην αρχή του πίνακα.
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν ΓΙΑ j ΑΠΟ Ν ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1 ΑΝ Α[j - 1] > Α[j] ΤΟΤΕ temp ← Α[j - 1] Α[j - 1] ← Α[j] Α[j] ← temp ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Για φθίνουσα σειρά αλλάζει μόνο η σύγκριση: Α[j - 1] < Α[j].
Παράδειγμα 1: Ίχνος της φυσαλίδας για Α = [5, 3, 8, 1] (Ν = 4).
- i = 2, j = 4: 8 > 1 → αντιμετάθεση → [5, 3, 1, 8]
- i = 2, j = 3: 3 > 1 → αντιμετάθεση → [5, 1, 3, 8]
- i = 2, j = 2: 5 > 1 → αντιμετάθεση → [1, 5, 3, 8]
- i = 3, j = 4: 3 > 8 ψευδές → [1, 5, 3, 8]
- i = 3, j = 3: 5 > 3 → αντιμετάθεση → [1, 3, 5, 8]
- i = 4, j = 4: 5 > 8 ψευδές → [1, 3, 5, 8]
Έγιναν συγκρίσεις και 4 αντιμεταθέσεις. Μετά το πρώτο πέρασμα το 1 (το μικρότερο) ήταν ήδη στη θέση του.
Πόσες συγκρίσεις κάνει η ταξινόμηση ευθείας ανταλλαγής του βιβλίου σε πίνακα 10 στοιχείων;
Μέθοδος: ίχνος αναζήτησης ή ταξινόμησης
- Γράψε τον πίνακα με τους δείκτες 1…Ν από πάνω.
- Για κάθε τιμή του εξωτερικού μετρητή (i), γράψε όλες τις τιμές του εσωτερικού (j) — στη φυσαλίδα το j μειώνεται από Ν μέχρι i.
- Σε κάθε βήμα σημείωσε ποια δύο στοιχεία συγκρίνονται (Α[j - 1] και Α[j]) και αν έγινε αντιμετάθεση.
- Μέτρα συγκρίσεις και αντιμεταθέσεις χωριστά — οι εξετάσεις ζητούν συχνά και τα δύο.
- Στην αναζήτηση, σταμάτα αμέσως μόλις βρεθεί το κλειδί.
Θέμα τύπου Πανελλαδικών: Δίνεται πίνακας ΟΝ[100] με ονόματα και πίνακας ΒΑΘ[100] με τους αντίστοιχους βαθμούς. Να γραφεί τμήμα που ταξινομεί τους μαθητές κατά φθίνουσα σειρά βαθμού, ώστε κάθε όνομα να μένει δίπλα στον βαθμό του, και εμφανίζει τους τρεις πρώτους.
Λύση: Όταν αντιμεταθέτουμε δύο βαθμούς, αντιμεταθέτουμε και τα αντίστοιχα ονόματα (παράλληλοι πίνακες).
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 100 ΓΙΑ j ΑΠΟ 100 ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1 ΑΝ ΒΑΘ[j - 1] < ΒΑΘ[j] ΤΟΤΕ tb ← ΒΑΘ[j - 1] ΒΑΘ[j - 1] ← ΒΑΘ[j] ΒΑΘ[j] ← tb tn ← ΟΝ[j - 1] ΟΝ[j - 1] ← ΟΝ[j] ΟΝ[j] ← tn ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 3 ΓΡΑΨΕ ΟΝ[i], ΒΑΘ[i] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Η tb είναι πραγματική (όπως οι βαθμοί) και η tn χαρακτήρας (όπως τα ονόματα) — κάθε βοηθητική μεταβλητή έχει τον τύπο των στοιχείων που ανταλλάσσει.
Στη σειριακή αναζήτηση σε πίνακα 50 στοιχείων, πόσες συγκρίσεις με το κλειδί γίνονται αν αυτό δεν υπάρχει στον πίνακα;
Το 2007, σε εκδήλωση της Google, ο τότε υποψήφιος πρόεδρος των ΗΠΑ Barack Obama ρωτήθηκε ποιος είναι ο καλύτερος τρόπος να ταξινομηθούν ένα εκατομμύριο ακέραιοι 32 bit. Απάντησε: «Νομίζω ότι η ταξινόμηση φυσαλίδας θα ήταν ο λάθος τρόπος» — και είχε δίκιο: για θα χρειαζόταν περίπου συγκρίσεις.
Στη φυσαλίδα του βιβλίου θυμήσου «2 μέχρι Ν έξω, Ν μέχρι i μέσα, με βήμα -1, σύγκρινε τον προηγούμενο με τον τρέχοντα (j - 1 με j)». Οι ελαφριές φυσαλίδες (μικρά στοιχεία) ανεβαίνουν προς την αρχή.
Αν ο πίνακας είναι ήδη ταξινομημένος, η φυσαλίδα του βιβλίου κάνει όλες τις συγκρίσεις χωρίς καμία αντιμετάθεση. Τροποποίησέ την ώστε να σταματά μόλις ένα πέρασμα ολοκληρωθεί χωρίς αντιμετάθεση.
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Χρησιμοποιούμε μια λογική μεταβλητή που γίνεται ΑΛΗΘΗΣ όταν γίνει αντιμετάθεση, και ΟΣΟ στη θέση του εξωτερικού ΓΙΑ.
i ← 2 αλλαγη ← ΑΛΗΘΗΣ ΟΣΟ i <= Ν ΚΑΙ αλλαγη = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ αλλαγη ← ΨΕΥΔΗΣ ΓΙΑ j ΑΠΟ Ν ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1 ΑΝ Α[j - 1] > Α[j] ΤΟΤΕ temp ← Α[j - 1] Α[j - 1] ← Α[j] Α[j] ← temp αλλαγη ← ΑΛΗΘΗΣ ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ i ← i + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Σε ήδη ταξινομημένο πίνακα γίνεται μόνο ένα πέρασμα με συγκρίσεις. Αν σε ένα πέρασμα δεν έγινε καμία αντιμετάθεση, όλα τα γειτονικά ζεύγη είναι στη σωστή σειρά — άρα ο πίνακας είναι ταξινομημένος.
- Αναζήτηση με ΓΙΑ χωρίς διακοπή: βρίσκει την τελευταία εμφάνιση του κλειδιού, όχι την πρώτη, και κάνει άσκοπες συγκρίσεις.
- Αντιμετάθεση χωρίς βοηθητική μεταβλητή (Α[j - 1] ← Α[j] και Α[j] ← Α[j - 1]): χάνεται μία τιμή.
- Σε παράλληλους πίνακες αντιμεταθέτεις μόνο τον πίνακα-κλειδί: τα ονόματα «ξεκολλάνε» από τους βαθμούς.
- Εσωτερικό ΓΙΑ από Ν μέχρι i χωρίς ΜΕ_ΒΗΜΑ -1: αφού Ν > i, δεν εκτελείται ποτέ.
- Σειριακή αναζήτηση: ένα ένα τα στοιχεία, με ΟΣΟ και λογική μεταβλητή· έως Ν συγκρίσεις.
- Δικαιολογείται σε μη ταξινομημένο ή μικρό πίνακα ή σε σπάνιες αναζητήσεις.
- Φυσαλίδα: σύγκριση γειτονικών Α[j - 1], Α[j] και αντιμετάθεση· i από 2 μέχρι Ν, j από Ν μέχρι i με βήμα -1.
- Συγκρίσεις φυσαλίδας: , πάντα.
- Σε παράλληλους πίνακες αντιμεταθέτεις όλους τους πίνακες μαζί.