Έστω ότι θέλουμε να διατάξουμε τους μαθητές μίας τάξης κατά φθίνουσα σειρά ύψους. Η τεχνική που θα ακολουθήσουμε είναι η εξής: Αρχικά, τοποθετούμε τους μαθητές σε μία τυχαία σειρά. Κατόπιν συγκρίνουμε το δεύτερο με τον πρώτο και αν χρειασθεί τους αντιμεταθέτουμε ώστε πρώτος να είναι ο ψηλότερος. Στη συνέχεια θεωρούμε τον τρίτο και τον τοποθετούμε στη σωστή σειρά σε σχέση με τον πρώτο και το δεύτερο. Κατ’ αυτόν τον τρόπο συνεχίζουμε μέχρι να τοποθετήσουμε στη σωστή σειρά όλους τους μαθητές. Να σχεδιασθεί ένας αλγόριθμος που να υλοποιεί αυτή τη μέθοδο ταξινόμησης.
ΛΥΣΗ:
Ουσιαστικά πρόκειται για τον αλγόριθμο ταξινόμησης ευθείας εισαγωγής straight insertion sort). Ο αλγόριθμος αυτός είναι ιδανικός για περιπτώσεις δεδομένων που είναι «περίπου» ταξινομημένα και χρησιμοποιείται σε πολλά υβριδικά σχήματα. Σύμφωνα µε τον αλγόριθμο αυτό τα στοιχεία διακρίνονται σχηματικά σε µία ακολουθία προορισμού (destination sequence) table[1], table[2], …, table[i-1] και σε µία ακολουθία πηγής (source sequence) table[i], …, table[n]. Αρχικά η ακολουθία προορισμού αποτελείται από ένα στοιχείο, το πρώτο, και σταδιακά μεγαλώνει κατά ένα. Αυτό επιτυγχάνεται θεωρώντας το πρώτο στοιχείο της ακολουθίας πηγής και παρεμβάλοντάς το στην κατάλληλη θέση μεταξύ των στοιχείων της ακολουθίας προορισμού εκτελώντας διαδοχικές συγκρίσεις από τα δεξιά προς τα αριστερά των µε τα στοιχεία της ακολουθίας προορισμού. Ο σχετικός αλγόριθμος δίνεται στη συνέχεια.
! Η πρώτη θέση του πίνακα παραμένει κενή (πίνακας με 1 παραπάνω στοιχείο) ! για να μείνει απλούστερη η ΟΣΟ, χωρίς έλεγχο για το τέλος του πίνακα. Αλγόριθμος Ευθεία_Εισαγωγή Δεδομένα // table // Για i από 2 μέχρι n temp ← table[i] j ← i-1 Όσο temp<table[j] και j>0 επανάλαβε table[j+1] ← table[j] j ← j-1 Τέλος_επανάληψης table[j+1] ← temp Τέλος_επανάληψης Αποτελέσματα // table // Τέλος Ευθεία_Εισαγωγή
Παράδειγμα. ‘Έστω ότι ο αρχικός πίνακας αποτελείται από τα εννέα (9) κλειδιά 52, 12, 71, 56, 5, 10, 19, 90 και 45. Στο προηγούμενο σχήμα παρουσιάζεται η διαδικασία ταξινόμησης θεωρώντας τον πίνακα αυτό. Κάθε φορά η ακολουθία προορισμού εμφανίζεται µε σκίαση, ενώ το πρώτο στοιχείο της ακολουθίας πηγής αναδεικνύεται από το αντίστοιχο βέλος. Το στοιχείο αυτό λαµβάνει την κατάλληλη θέση μέσα στην ακολουθία προορισμού “σπρώχνοντας” μερικά στοιχεία προς τα δεξιά. Η εύρεση της κατάλληλης θέσης γίνεται εύκολα µε διαδοχικές συγκρίσεις και μετακινήσεις. Λόγου χάριν, στην πέμπτη σειρά το στοιχείο 10 συγκρίνεται διαδοχικά µε τα στοιχεία 71, 56, 52, 12 και 5, οπότε γίνεται αντιληπτό ότι το 10 πρέπει να παρεμβληθεί μεταξύ των 5 και 12. Για να γίνει αυτό τα στοιχεία 12 ως και 71 μετακινούνται µία θέση προς τα δεξιά για να δημιουργηθεί µία κενή θέση για το 10.
Πρόγραμμα Ευθεία_Εισαγωγή Μεταβλητές Ακέραιες: table[10], i, j, temp ! Πίνακας κατά μία θέση μεγαλύτερος Αρχή table[1]<--0 ! η πρώτη θέση του πίνακα παραμένει κενή Για i από 2 μέχρι 10 Διάβασε table[i] Τέλος_Επανάληψης Για i από 2 μέχρι 10 temp <-- table[i] j <-- i-1 Όσο temp<table[j] και j>0 επανάλαβε ! Αύξουσα ταξινόμηση table[j+1] <-- table[j] j <-- j-1 Τέλος_επανάληψης table[j+1] <-- temp Τέλος_επανάληψης Για i από 2 μέχρι 10 Γράψε table[i], ' ' Τέλος_Επανάληψης Τέλος_Προγράμματος
! Προτεινόμενη, με flag για τερματισμό της σύγκρισης
Πρόγραμμα Ευθεία_Εισαγωγή Μεταβλητές Ακέραιες: table[9], i, j, temp Λογικές: done Αρχή ! εισαγωγή δεδομένων Για i από 1 μέχρι 9 διάβασε table[i] Τέλος_επανάληψης ! straight insertion sort Για i από 2 μέχρι 9 temp <-- table[i] j <-- i - 1 done <-- ψευδής Όσο done = ψευδής επανάλαβε Αν j = 0 τότε ! φτάσαμε στην αρχή του πίνακα, άρα πρέπει να σταματήσουμε done <-- αληθής Αλλιώς_Αν temp < table[j] τότε ! συναντήσαμε μεγαλύτερο στοιχείο, δημιουργούμε οπή table[j+1] <-- table[j] j <-- j - 1 Αλλιώς ! πρέπει να σταματήσουμε την επανάληψη γιατί το στοιχείο θα μείνει σε αυτήν τη θέση done <-- αληθής Τέλος_Αν Τέλος_επανάληψης table[j+1] <-- temp ! τοποθετούμε το στοιχείο στην οπή Τέλος_επανάληψης ! εμφάνιση ταξινομημένων στοιχείων Γράψε Γράψε 'Αύξουσα Ταξινόμηση:' Για i από 1 μέχρι 9 Γράψε table[i], ' ' Τέλος_Επανάληψης Τέλος_Προγράμματος
Πρόσφατα σχόλια