Αναζήτηση και ταξινόμηση

Σειριακή αναζήτηση

Η πιο απλή: ελέγχουμε τα στοιχεία ένα προς ένα από την αρχή, μέχρι να βρεθεί το ζητούμενο ή να τελειώσει ο πίνακας.

1. 1ΑΛΓΟΡΙΘΜΟΣ Σειριακή
2. 2ΔΕΔΟΜΕΝΑ // A, n, key //
3. 3done ← ΨΕΥΔΗΣ
4. 4position ← -1
5. 5i ← 1
6. 6ΟΣΟ i <= n ΚΑΙ done = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
7. 7 ΑΝ A[i] = key ΤΟΤΕ
8. 8 done ← ΑΛΗΘΗΣ
9. 9 position ← i
10. 10 ΑΛΛΙΩΣ
11. 11 i ← i + 1
12. 12 ΤΕΛΟΣ_ΑΝ
13. 13ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
14. 14ΑΠΟΤΕΛΕΣΜΑΤΑ // done, position //
15. 15ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥ

Η σημαία done υπάρχει για να σταματά ο βρόχος μόλις βρεθεί το στοιχείο. Χωρίς αυτήν, ο αλγόριθμος θα σάρωνε ολόκληρο τον πίνακα ακόμη κι όταν το βρήκε στην πρώτη θέση.

Δυαδική αναζήτηση

Απαιτεί ταξινομημένο πίνακα. Σε κάθε βήμα κοιτάζει το μεσαίο στοιχείο και πετάει το μισό που δεν μπορεί να περιέχει το ζητούμενο.

1. Βρες το μεσαίο στοιχείο του διαστήματος αναζήτησης.
2. Αν είναι το ζητούμενο, τελείωσε.
3. Αν είναι μικρότερο, συνέχισε στο δεξί μισό· αν μεγαλύτερο, στο αριστερό.
4. Επανάλαβε ώσπου το διάστημα αδειάσει.

Σειριακή εναντίον δυαδικής

Ανέβασε το μέγεθος στα 1000. Η σειριακή χρειάζεται στη χειρότερη περίπτωση 1000 συγκρίσεις· η δυαδική 10. Κάθε διπλασιασμός του πίνακα κοστίζει στη δυαδική μία μόνο σύγκριση παραπάνω.

Μέγεθος πίνακα100

Θέση του ζητούμενου73

Η δυαδική προϋποθέτει ταξινομημένο πίνακα. Η σειριακή όχι — γι' αυτό δεν είναι πάντα η κακή επιλογή.

Συγκρίσεις για αυτή τη θέση

Σειριακή73

χειρότερη περίπτωση: 100

Δυαδική6

χειρότερη περίπτωση: 7

Ταξινόμηση φυσαλίδας

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

1. 1ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ n
2. 2ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
3. 3 ΑΝ A[j-1] > A[j] ΤΟΤΕ
4. 4 temp ← A[j-1]
5. 5 A[j-1] ← A[j]
6. 6 A[j] ← temp
7. 7 ΤΕΛΟΣ_ΑΝ
8. 8ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
9. 9ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ο εσωτερικός βρόχος πηγαίνει ανάποδα, από το τέλος προς το i. Έτσι το μικρότερο στοιχείο ανεβαίνει προς την αρχή, και μετά το πέρασμα i οι πρώτες i-1 θέσεις είναι οριστικές.

Φυσαλίδα στον πίνακα 5, 2, 9, 1

Έξι συγκρίσεις συνολικά, όσες και το n(n−1)/2 για n = 4. Πρόσεξε ότι το πλήθος τους δεν εξαρτάται από τα δεδομένα — μόνο το πλήθος των αντιμεταθέσεων.

Βήμα	i	j	Σύγκριση	Πίνακας
Ζωντανή ενημέρωση

Επόμενο βήμαΌλαΕπαναφορά

Οι συγκρίσεις είναι πάντα

$$\frac{n(n-1)}{2}$$

ανεξάρτητα από τα δεδομένα. Οι αντιμεταθέσεις εξαρτώνται: καμία σε ήδη ταξινομημένο πίνακα, το μέγιστο σε αντιστρόφως ταξινομημένο.

Διαίρει και βασίλευε

Η στρατηγική πίσω από τη δυαδική αναζήτηση, σε τρία βήματα:

1. Διαίρεση του προβλήματος σε μικρότερα του ίδιου τύπου.
2. Κυριαρχία — λύση των μικρότερων, συνήθως αναδρομικά.
3. Σύνθεση των επιμέρους λύσεων.

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

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση