Μετάβαση στο περιεχόμενο

Ταξινόμηση ευθείας ανταλλαγής

Οι διαδοχικές ανταλλαγές γειτονικών στοιχείων, βήμα βήμα, σε αύξουσα και φθίνουσα σειρά.

40 λεπτά

Θα μάθεις να

  1. Να περιγράφεις την ταξινόμηση ευθείας ανταλλαγής ως διαδοχικές συγκρίσεις και αντιμεταθέσεις γειτονικών στοιχείων, από το τέλος της λίστας προς την αρχή.
  2. Να γράφεις τον αλγόριθμο του βιβλίου σε Python, με τα όρια range(N - 1) και range(N - 1, i, -1).
  3. Να γράφεις το περιεχόμενο της λίστας μετά από κάθε πέρασμα και να μετράς συγκρίσεις και αντιμεταθέσεις.
  4. Να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά, σε παράλληλες λίστες και στη βελτιωμένη εκδοχή που σταματά μόλις η λίστα ταξινομηθεί.

Ο Αλέξανδρος βρίσκει τη θέση του

Τέσσερις μαθητές περιμένουν σε αλφαβητική σειρά την πρόβα της παρέλασης. Ο Αλέξανδρος φτάνει τελευταίος και μπαίνει στο τέλος της σειράς. Συγκρίνει το όνομά του με αυτό του συμμαθητή που είναι μπροστά του: αν προηγείται αλφαβητικά, αλλάζουν θέσεις. Μετά συγκρίνεται με τον επόμενο, ώσπου να φτάσει στη θέση του.

ΘέσηΑρχικάΤέλος
0ΔημήτρηςΔημήτρηςΔημήτρηςΔημήτρηςΑλέξανδρος
1ΕυγενίαΕυγενίαΕυγενίαΑλέξανδροςΔημήτρης
2ΝαταλίαΝαταλίαΑλέξανδροςΝαταλίαΕυγενία
3ΡένιαΑλέξανδροςΝαταλίαΕυγενίαΝαταλία
4ΑλέξανδροςΡένιαΡένιαΡένιαΡένια

Οι συμβολοσειρές συγκρίνονται με τη λεξικογραφική διάταξη, δηλαδή αλφαβητικά: "Αλέξανδρος" < "Ρένια" είναι True. Η αμοιβαία αλλαγή τιμών γίνεται με μία εντολή της Python, a, b = b, a, χωρίς βοηθητική μεταβλητή. Με βοηθητική θα έγραφες temp = a, a = b, b = temp.

Οι τέσσερις συγκρίσεις, από τη θέση 44 ως τη θέση 11, γράφονται με έναν βρόχο. Στους runners της ενότητας το print(...) έχει ένα όρισμα, και έτσι δουλεύει ίδια και στην Python 2.7 του βιβλίου και στην Python 3.

Ο Αλέξανδρος ανεβαίνει στη θέση 0

Σε κάθε επανάληψη συγκρίνεται το students[j] με αυτό που είναι μπροστά του, το students[j - 1]. Πριν από κάθε σύγκριση πες αν θα γίνει αντιμετάθεση.

  1. τρέχουσα γραμμή: students = ["Δημήτρης", "Ευγενία", "Ναταλία", "Ρένια", "Αλέξανδρος"]
  2. for j in range(4, 0, -1):
  3. if students[j] < students[j - 1]:
  4. students[j], students[j - 1] = students[j - 1], students[j]
  5. for name in students:
  6. print(name)

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.Γραμμή 1: τι τιμή θα πάρει το students;

Μεταβλητές

—

Έξοδος

Η 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]

Αυτό λέγεται πέρασμα. Το αποτέλεσμά του είναι ότι το μικρότερο στοιχείο ανεβαίνει στη θέση 00, όπως μια φυσαλίδα στην επιφάνεια του νερού.

Ένα πέρασμα στη λίστα [21, 13, 8, 5, 3, 2]

Σε κάθε γραμμή φαίνεται η σύγκριση. Πες αν θα γίνει αντιμετάθεση και πώς θα είναι η λίστα μετά, πριν πατήσεις.

ΒήμαjΣύγκρισηΑντιμετάθεση;Η λίστα μετά
Ζωντανή ενημέρωση

Όλα τα περάσματα

Αν εκτελέσεις το ίδιο πέρασμα ξανά, ανεβαίνει στη θέση 11 το αμέσως μικρότερο, το 33. Κάθε πέρασμα φέρνει ένα ακόμα στοιχείο στην τελική του θέση. Δύο παρατηρήσεις κάνουν τον αλγόριθμο οικονομικότερο:

  1. Αρκούν N - 1 περάσματα. Όταν τα N - 1 μικρότερα είναι στις θέσεις τους, το τελευταίο είναι αναγκαστικά στη θέση που περισσεύει. Γι' αυτό η εξωτερική επανάληψη είναι range(N - 1), με i από 0 ως και N - 2.
  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). Βασίζεται στη σύγκριση γειτονικών στοιχείων και στην αντιμετάθεση όσων δεν ακολουθούν τη σειρά της ταξινόμησης.

Επτά αριθμοί, πέρασμα πέρασμα

Η λίστα της εικόνας 5-4 του βιβλίου. Η print μέσα στον εξωτερικό βρόχο δείχνει τη λίστα στο τέλος κάθε περάσματος, για i = 0 ως 5. Μετά από ποιο πέρασμα είναι ήδη ταξινομημένη;

  1. A = [60, 38, 98, 54, 32, 90, 20]
  2. N = len(A)
  3. for i in range(N - 1):
  4. for j in range(N - 1, i, -1):
  5. if A[j] < A[j - 1]:
  6. A[j], A[j - 1] = A[j - 1], A[j]
  7. print(A)

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.

Μεταβλητές

—

Έξοδος

Μετά το πέρασμα i = 3 η λίστα είναι ήδη ταξινομημένη, αλλά ο αλγόριθμος κάνει και τα δύο τελευταία. Το πλήθος των συγκρίσεων δεν εξαρτάται από τα δεδομένα: το πέρασμα i κάνει N - 1 - i συγκρίσεις, άρα συνολικά

(N−1)+(N−2)+⋯+1=N(N−1)2.(N-1) + (N-2) + \dots + 1 = \frac{N(N-1)}{2}.

Για 77 στοιχεία, 2121 συγκρίσεις. Οι αντιμεταθέσεις εξαρτώνται από τα δεδομένα: εδώ ήταν 1414, σε ήδη ταξινομημένη λίστα 00.

Θα δεις και τη μορφή 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:

Σχεδόν ταξινομημένη λίστα

Η λίστα του βιβλίου 3, 5, 8, 13, 21, 34, 55, 2. Πόσα περάσματα θα εκτελεστούν; Μετά από κάθε πέρασμα τυπώνεται η λίστα και η isSorted.

  1. def optimizedBubbleSort(A):
  2. N = len(A)
  3. isSorted = False
  4. i = 1
  5. while i < N and not isSorted:
  6. isSorted = True
  7. for j in range(N - 1, i - 1, -1):
  8. if A[j] < A[j - 1]:
  9. A[j], A[j - 1] = A[j - 1], A[j]
  10. isSorted = False
  11. print(A)
  12. print(isSorted)
  13. i = i + 1
  14. L = [3, 5, 8, 13, 21, 34, 55, 2]
  15. optimizedBubbleSort(L)

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.

Μεταβλητές

—

Έξοδος

Το πρώτο πέρασμα φέρνει το 22 στην αρχή. Το δεύτερο δεν κάνει καμία αντιμετάθεση, η isSorted μένει True και ο βρόχος σταματά: δύο περάσματα αντί για επτά. Εδώ το i ξεκινά από 1, γι' αυτό η εσωτερική range σταματά στο i - 1.

Η ταξινόμηση με εισαγωγή (5.3) δεν εξετάζεται.

Παραδείγματα

Παράδειγμα 1

Δίνεται η λίστα A = [55, 34, 5, 3, 2, 1, 1]. Να γράψετε το περιεχόμενο της λίστας αμέσως μετά από κάθε πέρασμα του αλγορίθμου ταξινόμησης ευθείας ανταλλαγής σε αύξουσα σειρά.

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

Παράδειγμα 2

Τι θα εμφανίσει το παρακάτω τμήμα προγράμματος;

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

Παράδειγμα 3

Να γράψετε πρόγραμμα σε Python που διαβάζει το πλήθος N των μαθητών ενός τμήματος και για τον καθένα το όνομα και τον βαθμό του, και εμφανίζει τα ονόματα και τους βαθμούς σε φθίνουσα σειρά βαθμού.

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

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Σωστό ή Λάθος: «Στην ταξινόμηση ευθείας ανταλλαγής συγκρίνονται πάντα γειτονικά στοιχεία της λίστας.»

Ασκήσεις

ΒασικήΆσκηση 1 από 6

Η λίστα A = [7, 3, 9, 1] ταξινομείται σε αύξουσα σειρά με τον αλγόριθμο του βιβλίου. Πώς είναι η λίστα μετά το πρώτο πέρασμα;

Τα κατάφερες;

  • Να περιγράφεις την ταξινόμηση ευθείας ανταλλαγής ως διαδοχικές συγκρίσεις και αντιμεταθέσεις γειτονικών στοιχείων, από το τέλος της λίστας προς την αρχή.
  • Να γράφεις τον αλγόριθμο του βιβλίου σε Python, με τα όρια range(N - 1) και range(N - 1, i, -1).
  • Να γράφεις το περιεχόμενο της λίστας μετά από κάθε πέρασμα και να μετράς συγκρίσεις και αντιμεταθέσεις.
  • Να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά, σε παράλληλες λίστες και στη βελτιωμένη εκδοχή που σταματά μόλις η λίστα ταξινομηθεί.

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;