Ταξινόμηση ευθείας ανταλλαγής
Οι διαδοχικές ανταλλαγές γειτονικών στοιχείων, βήμα βήμα, σε αύξουσα και φθίνουσα σειρά.
40 λεπτά
Θα μάθεις να
- Να περιγράφεις την ταξινόμηση ευθείας ανταλλαγής ως διαδοχικές συγκρίσεις και αντιμεταθέσεις γειτονικών στοιχείων, από το τέλος της λίστας προς την αρχή.
- Να γράφεις τον αλγόριθμο του βιβλίου σε Python, με τα όρια range(N - 1) και range(N - 1, i, -1).
- Να γράφεις το περιεχόμενο της λίστας μετά από κάθε πέρασμα και να μετράς συγκρίσεις και αντιμεταθέσεις.
- Να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά, σε παράλληλες λίστες και στη βελτιωμένη εκδοχή που σταματά μόλις η λίστα ταξινομηθεί.
Ο Αλέξανδρος βρίσκει τη θέση του
Τέσσερις μαθητές περιμένουν σε αλφαβητική σειρά την πρόβα της παρέλασης. Ο Αλέξανδρος φτάνει τελευταίος και μπαίνει στο τέλος της σειράς. Συγκρίνει το όνομά του με αυτό του συμμαθητή που είναι μπροστά του: αν προηγείται αλφαβητικά, αλλάζουν θέσεις. Μετά συγκρίνεται με τον επόμενο, ώσπου να φτάσει στη θέση του.
| Θέση | Αρχικά | Τέλος | |||
|---|---|---|---|---|---|
| 0 | Δημήτρης | Δημήτρης | Δημήτρης | Δημήτρης | Αλέξανδρος |
| 1 | Ευγενία | Ευγενία | Ευγενία | Αλέξανδρος | Δημήτρης |
| 2 | Ναταλία | Ναταλία | Αλέξανδρος | Ναταλία | Ευγενία |
| 3 | Ρένια | Αλέξανδρος | Ναταλία | Ευγενία | Ναταλία |
| 4 | Αλέξανδρος | Ρένια | Ρένια | Ρένια | Ρένια |
Οι συμβολοσειρές συγκρίνονται με τη λεξικογραφική διάταξη, δηλαδή αλφαβητικά: "Αλέξανδρος" < "Ρένια" είναι True. Η αμοιβαία αλλαγή τιμών γίνεται με μία εντολή της Python, a, b = b, a, χωρίς βοηθητική μεταβλητή. Με βοηθητική θα έγραφες temp = a, a = b, b = temp.
Οι τέσσερις συγκρίσεις, από τη θέση ως τη θέση , γράφονται με έναν βρόχο. Στους runners της ενότητας το print(...) έχει ένα όρισμα, και έτσι δουλεύει ίδια και στην Python 2.7 του βιβλίου και στην Python 3.
Η range(4, 0, -1) δίνει 4, 3, 2, 1. Στην τελευταία επανάληψη j = 1 και j - 1 = 0: το τελευταίο στοιχείο που συγκρίνεται είναι το students[0].
Ένα πέρασμα
Σε μια λίστα A με N στοιχεία, ο ίδιος βρόχος γράφεται:
N = len(A)
for j in range(N - 1, 0, -1):
if A[j] < A[j - 1]:
A[j], A[j - 1] = A[j - 1], A[j]
Αυτό λέγεται πέρασμα. Το αποτέλεσμά του είναι ότι το μικρότερο στοιχείο ανεβαίνει στη θέση , όπως μια φυσαλίδα στην επιφάνεια του νερού.
Όλα τα περάσματα
Αν εκτελέσεις το ίδιο πέρασμα ξανά, ανεβαίνει στη θέση το αμέσως μικρότερο, το . Κάθε πέρασμα φέρνει ένα ακόμα στοιχείο στην τελική του θέση. Δύο παρατηρήσεις κάνουν τον αλγόριθμο οικονομικότερο:
- Αρκούν
N - 1περάσματα. Όταν ταN - 1μικρότερα είναι στις θέσεις τους, το τελευταίο είναι αναγκαστικά στη θέση που περισσεύει. Γι' αυτό η εξωτερική επανάληψη είναιrange(N - 1), μεiαπό0ως καιN - 2. - Κάθε πέρασμα σταματά νωρίτερα. Μετά το πέρασμα
i, οι θέσεις0ωςiείναι ήδη τελικές. Στο επόμενο πέρασμα η φυσαλίδα δεν χρειάζεται να ανέβει πάνω από αυτές.
Η τελευταία σύγκριση του περάσματος i είναι η A[i + 1] < A[i], δηλαδή με j = i + 1. Γι' αυτό η εσωτερική range γίνεται range(N - 1, i, -1), που σταματά στο i + 1. Ο αλγόριθμος παίρνει την τελική του μορφή:
N = len(A)
for i in range(N - 1):
for j in range(N - 1, i, -1):
if A[j] < A[j - 1]:
A[j], A[j - 1] = A[j - 1], A[j]
Λέγεται ταξινόμηση ευθείας ανταλλαγής (straight exchange sort) και είναι πιο γνωστή ως ταξινόμηση φυσαλίδας (bubble sort). Βασίζεται στη σύγκριση γειτονικών στοιχείων και στην αντιμετάθεση όσων δεν ακολουθούν τη σειρά της ταξινόμησης.
Μετά το πέρασμα i = 3 η λίστα είναι ήδη ταξινομημένη, αλλά ο αλγόριθμος κάνει και τα δύο τελευταία. Το πλήθος των συγκρίσεων δεν εξαρτάται από τα δεδομένα: το πέρασμα i κάνει N - 1 - i συγκρίσεις, άρα συνολικά
Για στοιχεία, συγκρίσεις. Οι αντιμεταθέσεις εξαρτώνται από τα δεδομένα: εδώ ήταν , σε ήδη ταξινομημένη λίστα .
Θα δεις και τη μορφή for i in range(N). Ταξινομεί σωστά: στο τελευταίο πέρασμα η range(N - 1, N - 1, -1) είναι κενή, άρα δεν γίνεται καμία σύγκριση.
Φθίνουσα σειρά
Για ταξινόμηση από το μεγαλύτερο στο μικρότερο αλλάζει μόνο ο τελεστής της σύγκρισης:
if A[j] > A[j - 1]:
A[j], A[j - 1] = A[j - 1], A[j]
Τώρα σε κάθε πέρασμα ανεβαίνει στην κορυφή το μεγαλύτερο από όσα απομένουν. Ο αλγόριθμος δουλεύει με αριθμούς και με συμβολοσειρές, γιατί και οι δύο συγκρίνονται με < και >.
Η βελτιωμένη φυσαλίδα
Το πλεονέκτημα της ευθείας ανταλλαγής, αν και είναι από τους πιο αργούς αλγορίθμους ταξινόμησης, είναι ότι μπορεί να σταματήσει μόλις διαπιστώσει ότι η λίστα ταξινομήθηκε. Αν σε ένα πέρασμα δεν γίνει καμία αντιμετάθεση, όλα τα γειτονικά ζεύγη είναι στη σωστή σειρά. Αυτό το κρατά μια λογική μεταβλητή, η isSorted:
Το πρώτο πέρασμα φέρνει το στην αρχή. Το δεύτερο δεν κάνει καμία αντιμετάθεση, η isSorted μένει True και ο βρόχος σταματά: δύο περάσματα αντί για επτά. Εδώ το i ξεκινά από 1, γι' αυτό η εσωτερική range σταματά στο i - 1.
Η ταξινόμηση με εισαγωγή (5.3) δεν εξετάζεται.
Παραδείγματα
Παράδειγμα 1
Δίνεται η λίστα A = [55, 34, 5, 3, 2, 1, 1]. Να γράψετε το περιεχόμενο της λίστας αμέσως μετά από κάθε πέρασμα του αλγορίθμου ταξινόμησης ευθείας ανταλλαγής σε αύξουσα σειρά.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Πρώτο πέρασμα (
i = 0): ένα ανεβαίνει ως τη θέση . Στη σύγκρισηA[6] < A[5]είναι , ψευδές, οπότε ανεβαίνει το της θέσης , και το άλλο μένει στο τέλος:[1, 55, 34, 5, 3, 2, 1].Δεύτερο (
i = 1):[1, 1, 55, 34, 5, 3, 2]. Τρίτο:[1, 1, 2, 55, 34, 5, 3]. Τέταρτο:[1, 1, 2, 3, 55, 34, 5].Πέμπτο:
[1, 1, 2, 3, 5, 55, 34]. Έκτο (i = 5):[1, 1, 2, 3, 5, 34, 55]. Για στοιχεία, περάσματα.
Παράδειγμα 2
Τι θα εμφανίσει το παρακάτω τμήμα προγράμματος;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
A = [4, 1, 3, 2] N = len(A) s = 0 for i in range(N - 1): for j in range(N - 1, i, -1): if A[j] < A[j - 1]: A[j], A[j - 1] = A[j - 1], A[j] s = s + 1 print A, sΠέρασμα
i = 0:j = 3, , αντιμετάθεση:[4, 1, 2, 3].j = 2, ψευδές.j = 1, , αντιμετάθεση:[1, 4, 2, 3].Πέρασμα
i = 1:j = 3, ψευδές.j = 2, , αντιμετάθεση:[1, 2, 4, 3]. Πέρασμαi = 2:j = 3, , αντιμετάθεση:[1, 2, 3, 4].Εμφανίζει
[1, 2, 3, 4] 4. Έγιναν συγκρίσεις, όσο το , και από αυτές έδωσαν αντιμετάθεση.
Παράδειγμα 3
Να γράψετε πρόγραμμα σε Python που διαβάζει το πλήθος N των μαθητών ενός τμήματος και για τον καθένα το όνομα και τον βαθμό του, και εμφανίζει τα ονόματα και τους βαθμούς σε φθίνουσα σειρά βαθμού.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Δύο παράλληλες λίστες,
nameListκαιgradeList: ο μαθητής της θέσηςiέχει τον βαθμό της ίδιας θέσης. Η ταξινόμηση γίνεται με βάση τηgradeList, με>για φθίνουσα σειρά.Κάθε αντιμετάθεση γίνεται και στις δύο λίστες. Αν άλλαζαν θέσεις μόνο οι βαθμοί, κάθε όνομα θα έμενε με λάθος βαθμό.
N = input("Πόσοι μαθητές έχει η τάξη; N = ") gradeList = [] nameList = [] for i in range(N): name = raw_input("όνομα = ") grade = input("βαθμός = ") nameList.append(name) gradeList.append(grade) for i in range(N - 1): for j in range(N - 1, i, -1): if gradeList[j] > gradeList[j - 1]: gradeList[j], gradeList[j - 1] = gradeList[j - 1], gradeList[j] nameList[j], nameList[j - 1] = nameList[j - 1], nameList[j] for i in range(N): print nameList[i], gradeList[i]Για 4 μαθητές, Ελένη 15, Νίκος 18, Μαρία 12, Γιάννης 19, εμφανίζει
Γιάννης 19,Νίκος 18,Ελένη 15,Μαρία 12. Το όνομα διαβάζεται μεraw_input, γιατί είναι κείμενο, και ο βαθμός μεinput, που δίνει αριθμό.
Πολλαπλή επιλογή
Ασκήσεις
Η λίστα A = [7, 3, 9, 1] ταξινομείται σε αύξουσα σειρά με τον αλγόριθμο του βιβλίου. Πώς είναι η λίστα μετά το πρώτο πέρασμα;
Τα κατάφερες;
- Να περιγράφεις την ταξινόμηση ευθείας ανταλλαγής ως διαδοχικές συγκρίσεις και αντιμεταθέσεις γειτονικών στοιχείων, από το τέλος της λίστας προς την αρχή.
- Να γράφεις τον αλγόριθμο του βιβλίου σε Python, με τα όρια range(N - 1) και range(N - 1, i, -1).
- Να γράφεις το περιεχόμενο της λίστας μετά από κάθε πέρασμα και να μετράς συγκρίσεις και αντιμεταθέσεις.
- Να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά, σε παράλληλες λίστες και στη βελτιωμένη εκδοχή που σταματά μόλις η λίστα ταξινομηθεί.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.