Να δοθεί ο ορισμός της έννοιας της ταξινόμησης.
Σκέψη / Μεθοδολογία: Κλειστή ερώτηση ορισμού — δίνεται ρητά στο §3.7.
Λύση:
Ανατρέχουμε στον ορισμό του §3.7 και τον αποδίδουμε πλήρως.
Απάντηση: Ταξινόμηση (sorting) ή διάταξη (ordering) είναι η τακτοποίηση των στοιχείων μιας δομής με μια συγκεκριμένη σειρά — συνήθως αύξουσα. Πιο τυπικά, δοθέντων στοιχείων a1, a2, ..., an, η ταξινόμηση είναι μια αναδιάταξή τους έτσι ώστε, για μια συνάρτηση διάταξης f, να ισχύει f(a_k1) ≤ f(a_k2) ≤ ... ≤ f(a_kn).
Πρόσεξε:
Να περιγραφεί η ταξινόμηση ευθείας ανταλλαγής και να δοθεί ένα παράδειγμα.
Σκέψη / Μεθοδολογία: Ερώτηση περιγραφής + παράδειγμα — χρησιμοποιούμε τον ορισμό της bubblesort και το αριθμητικό παράδειγμα του §3.7.
Λύση:
Περιγράφουμε τη λογική της ταξινόμησης ευθείας ανταλλαγής (bubblesort), μετά εφαρμόζουμε τον αλγόριθμο στον πίνακα του παραδείγματος για να δείξουμε την εξέλιξή του.
Απάντηση: Η ταξινόμηση ευθείας ανταλλαγής (straight exchange sort), γνωστή και ως ταξινόμηση φυσαλίδας (bubblesort), βασίζεται σε διαδοχικές συγκρίσεις και ανταλλαγές γειτονικών στοιχείων· σε κάθε πέρασμα, το μικρότερο στοιχείο «ανεβαίνει» προς τη σωστή του θέση, σαν φυσαλίδα. Παράδειγμα: για τον πίνακα 52, 12, 71, 56, 5, 10, 19, 90, 45, μετά την 1η επανάληψη (i=2) το 5 ανεβαίνει στην αρχή: 5, 52, 12, 71, 56, 10, 19, 45, 90. Η διαδικασία συνεχίζεται μέχρι την 7η επανάληψη, όπου ο πίνακας γίνεται πλήρως ταξινομημένος: 5, 10, 12, 19, 45, 52, 56, 71, 90.
Πρόσεξε:
