Λύσεις — Κεφάλαιο 5: Κλασικοί Αλγόριθμοι ΙΙ (σελ. 85-88) – ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ

ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ – ΛΥΣΕΙΣ – ΑΠΑΝΤΗΣΕΙΣ Ασκήσεων Σχολικού Βιβλίου Λύσεις — Κεφάλαιο 5: Κλασικοί Αλγόριθμοι ΙΙ (σελ. 85-88) – ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ

Λύσεις — Κεφάλαιο 5: Κλασικοί Αλγόριθμοι ΙΙ (σελ. 85-88)

Λύσεις των 10 Δραστηριοτήτων (κώδικας Python) και των 5 Ερωτήσεων του κεφαλαίου 5, ελεγμένες με το επίσημο βιβλίο λύσεων.

Δραστηριότητα 1 — Αντιστοίχιση αλγορίθμων με στοιχειώδη λειτουργία

Ερώτηση: Να αντιστοιχήσετε τους παρακάτω αλγόριθμους με τις κατάλληλες λειτουργίες: Αλγόριθμος: Ταξινόμηση με επιλογή · Ταξινόμηση ευθείας ανταλλαγής · Ταξινόμηση με εισαγωγή. Στοιχειώδης Λειτουργία: Α. Αντιμετάθεση ζευγών · Β. Εισαγωγή στοιχείου σε ταξινομημένη λίστα · Γ. Εύρεση ελαχίστου.

Απάντηση:

Ταξινόμηση με επιλογή → Γ. Εύρεση ελαχίστου. Σε κάθε βήμα βρίσκει το ελάχιστο του αταξινόμητου τμήματος (findMinPosition) και το αντιμεταθέτει με το πρώτο στοιχείο του τμήματος (Β΄ τάξη, ενότητα 6.3).
Ταξινόμηση ευθείας ανταλλαγής → Α. Αντιμετάθεση ζευγών. Βασίζεται στη «σύγκριση και αντιμετάθεση γειτονικών ζευγών που δεν ακολουθούν τη διάταξη» (σελ. 78) — η φυσαλίδα ανεβαίνει με διαδοχικές αντιμεταθέσεις.
Ταξινόμηση με εισαγωγή → Β. Εισαγωγή στοιχείου σε ταξινομημένη λίστα. Κάθε νέο στοιχείο «παρεμβάλλεται στο ταξινομημένο τμήμα της λίστας» στη σωστή θέση, μετά από αναζήτηση και μετακίνηση (shift) των μεγαλύτερων (σελ. 81).
Σημείωση: το επίσημο βιβλίο λύσεων γράφει εκ παραδρομής «1Α» για την τρίτη αντιστοίχιση — η σωστή είναι 3Β.

Σύνοψη: Επιλογή → Γ (εύρεση ελαχίστου), ευθείας ανταλλαγής → Α (αντιμετάθεση ζευγών), εισαγωγή → Β (εισαγωγή σε ταξινομημένη λίστα).

Κριτήρια αξιολόγησης:

Τρεις σωστές αντιστοιχίσεις με μια φράση αιτιολόγησης.

Δραστηριότητα 2 — Ταξινόμηση με επιλογή σε φθίνουσα σειρά

Ερώτηση: Να τροποποιήσετε τον αλγόριθμο της ταξινόμησης με επιλογή, ώστε να ταξινομεί μια λίστα ακεραίων σε φθίνουσα σειρά. Υπάρχει τρόπος να το πετύχετε, χωρίς να κάνετε καμία απολύτως αλλαγή στον κύριο αλγόριθμο που δίνεται στην ενότητα 6.3 του βιβλίου της Β’ τάξης; Σε τι οφείλεται αυτό;

Απάντηση:

Ο αλγόριθμος της Β΄ τάξης είναι χωρισμένος σε δύο συναρτήσεις: η findMinPosition(start, end, List) βρίσκει τη θέση του ελαχίστου στο τμήμα [start, end) και η selectionSortAscending(List) σε κάθε βήμα i την καλεί και αντιμεταθέτει το στοιχείο της θέσης i με το ελάχιστο.
Λύση χωρίς καμία αλλαγή στον κύριο αλγόριθμο: αρκεί να αλλάξουμε μόνο τον τελεστή σύγκρισης μέσα στη findMinPosition από < σε >, ώστε να επιστρέφει τη θέση του μεγίστου. Τότε η selectionSortAscending — χωρίς να πειραχτεί ούτε μία γραμμή της — φέρνει σε κάθε βήμα το μεγαλύτερο στοιχείο μπροστά, δηλαδή ταξινομεί σε φθίνουσα σειρά:

def findMinPosition(start, end, List):     # τώρα βρίσκει τη θέση του ΜΕΓΙΣΤΟΥ
    position = start
    for i in range(start, end):
        if List[ i ] > List[ position ] :   # μόνο αυτό άλλαξε: < έγινε >
            position = i
    return position

def selectionSortAscending(List):          # ΑΜΕΤΑΒΛΗΤΗ
    position = None
    n = len(List)
    for i in range(0, n):
        position = findMinPosition(i, n, List)
        List[ i ], List[ position ] = List[ position ], List[ i ]
    return List

print selectionSortAscending([21, 13, 8, 5, 3, 2, 34])   # [34, 21, 13, 8, 5, 3, 2]

Σε τι οφείλεται: στην ανεξαρτησία και ευελιξία του τμηματικού (αρθρωτού) προγραμματισμού — ο κύριος αλγόριθμος δεν γνωρίζει πώς επιλέγεται το στοιχείο, μόνο ότι η βοηθητική συνάρτηση του επιστρέφει μια θέση. Αλλάζοντας τη «στοιχειώδη λειτουργία» (εύρεση ελαχίστου → μεγίστου) αλλάζει η συμπεριφορά όλου του αλγορίθμου χωρίς να θιγεί ο κώδικάς του.
Εναλλακτικά (με μία αλλαγή στον κύριο αλγόριθμο) θα μπορούσαμε να καλούμε την αρχική findMinPosition και να τοποθετούμε το ελάχιστο στο τέλος του αταξινόμητου τμήματος, ή απλώς να αντιστρέψουμε τη λίστα στο τέλος (List.reverse()).

Σύνοψη: Αλλάζουμε μόνο τον τελεστή < σε > στη findMinPosition (βρίσκει το μέγιστο)· η selectionSortAscending ταξινομεί φθίνουσα χωρίς καμία αλλαγή — χάρη στην ανεξαρτησία του τμηματικού προγραμματισμού.

Κριτήρια αξιολόγησης:

Η ελάχιστη αλλαγή (ένας τελεστής) + η εξήγηση «τμηματικός προγραμματισμός».

Δραστηριότητα 3 — Συνάρτηση ελέγχου αύξουσας σειράς

Ερώτηση: Να γράψετε μια συνάρτηση σε Python, η οποία θα δέχεται μια λίστα, θα ελέγχει αν τα στοιχεία της είναι σε αύξουσα σειρά και θα επιστρέφει αντίστοιχα True ή False. Υπόδειξη: Χρησιμοποιήστε μια λογική μεταβλητή.

Απάντηση:

Ιδέα: η λογική μεταβλητή ascending ξεκινά True και γίνεται False μόλις βρεθεί ένα ζευγάρι γειτονικών στοιχείων σε φθίνουσα σειρά (myList[i] > myList[i+1]). Μόλις βρεθεί τέτοιο ζευγάρι δεν έχει νόημα να συνεχίσουμε — η συνθήκη του while το εξασφαλίζει:

def isAscending(myList):
    ascending = True
    i = 0
    N = len(myList)
    while ascending and i < N-1 :
        if myList[ i ] > myList[ i+1 ] :
            ascending = False
        i = i + 1
    return ascending

print isAscending([2, 3, 5, 8, 13])     # True
print isAscending([2, 3, 9, 8, 13])     # False
print isAscending([7])                  # True (κανένα ζευγάρι)

Εναλλακτικά χωρίς λογική μεταβλητή — με άμεση επιστροφή μόλις βρεθεί «παραφωνία»: def isAscending2(myList): for i in range(len(myList)-1): if myList[i] > myList[i+1]: return False και στο τέλος return True.
Παρατήρηση: ελέγχουμε i < N−1 ώστε το myList[i+1] να υπάρχει· η κενή λίστα και η λίστα ενός στοιχείου θεωρούνται ταξινομημένες. Η συνάρτηση δουλεύει και για αλφαριθμητικά (λεξικογραφική σύγκριση).

Σύνοψη: ascending = True· while ascending and i < N−1: αν myList[i] > myList[i+1] τότε ascending = False· return ascending.

Κριτήρια αξιολόγησης:

Λογική μεταβλητή + σωστά όρια (i < N−1) + τερματισμός με το πρώτο λάθος ζευγάρι.

Δραστηριότητα 4 — Βελτιωμένη φυσαλίδα

Ερώτηση: Να αναπτύξετε τη βελτιωμένη έκδοση του αλγορίθμου ταξινόμησης ευθείας ανταλλαγής η οποία τερματίζει, όταν διαπιστώσει ότι η λίστα είναι ταξινομημένη, ώστε να αποφεύγονται περιττές συγκρίσεις. Υπόδειξη: Χρησιμοποιήστε μια λογική μεταβλητή η οποία θα αλλάζει τιμή, αν υπάρχουν τουλάχιστον δύο στοιχεία τα οποία δε βρίσκονται στην επιθυμητή σειρά, καθώς η “φυσαλίδα ανεβαίνει στην επιφάνεια”.

Απάντηση:

Ιδέα: στην αρχή κάθε περάσματος θέτουμε isSorted = True. Αν στο πέρασμα γίνει έστω μία αντιμετάθεση, isSorted = False. Αν ολοκληρωθεί πέρασμα χωρίς αντιμετάθεση, όλα τα γειτονικά ζευγάρια είναι στη σωστή σειρά → η λίστα είναι ταξινομημένη και ο αλγόριθμος τερματίζει αντί να κάνει τα υπόλοιπα (περιττά) περάσματα.

# Βελτιωμένη ταξινόμηση ευθείας ανταλλαγής (με λογική μεταβλητή)
def optimizedBubbleSort( A ):
    N = len( A )
    isSorted = False
    i = 0
    while i < N-1 and not isSorted :
        isSorted = True                        # υπόθεση: είναι ταξινομημένη
        for j in range(N-1, i, -1):
            if A[ j ] < A[ j-1 ]:
                A[ j ], A[ j-1 ] = A[ j-1 ], A[ j ]
                isSorted = False               # έγινε αντιμετάθεση -> όχι ακόμα
        i = i + 1
    return A

print optimizedBubbleSort([3, 5, 8, 13, 21, 34, 55, 2])   # [2, 3, 5, 8, 13, 21, 34, 55]

Για τη λίστα 3, 5, 8, 13, 21, 34, 55, 2 (σελ. 78): στο 1ο πέρασμα το 2 ανεβαίνει στη θέση 0 (7 αντιμεταθέσεις, isSorted = False)· στο 2ο πέρασμα δεν γίνεται καμία αντιμετάθεση → isSorted μένει True → τερματισμός μετά από 2 περάσματα αντί για 7. Στην Εικόνα 5-4 (60,38,98,54,32,90,20) θα σταματούσε μετά το 5ο πέρασμα (το 4ο ταξινομεί, το 5ο το διαπιστώνει), γλιτώνοντας το 6ο.
Δεύτερος τρόπος (επίσημες λύσεις): κρατάμε το for i in range(N) και μετά την εσωτερική επανάληψη if isSorted: return — βίαιη διακοπή της εξωτερικής επανάληψης.
Το πλεονέκτημα αυτό είναι που ξεχωρίζει τη φυσαλίδα από την ταξινόμηση με επιλογή (πάντα ίδιος αριθμός συγκρίσεων) — σελ. 72, 78.

Σύνοψη: Λογική μεταβλητή isSorted: True στην αρχή κάθε περάσματος, False σε κάθε αντιμετάθεση· ο εξωτερικός βρόχος (while i < N−1 and not isSorted) σταματά μόλις ένα πέρασμα ολοκληρωθεί χωρίς αντιμετάθεση.

Κριτήρια αξιολόγησης:

Σωστή θέση αρχικοποίησης (μέσα στο πέρασμα) + συνθήκη τερματισμού + παράδειγμα με το 2 στο τέλος.

Δραστηριότητα 5 — Διαχωρισμός True/False (True πριν από False)

Ερώτηση: Να γράψετε μια συνάρτηση σε Python η οποία θα δέχεται μια λίστα με λογικές τιμές True/False και θα διαχωρίζει τις τιμές αυτές, τοποθετώντας τα True πριν από τα False.

Απάντηση:

1ος τρόπος — με μέτρηση (ο απλούστερος και γρηγορότερος): μετράμε πόσα True υπάρχουν (k)· τα υπόλοιπα N−k είναι False. Στη συνέχεια γράφουμε True στις πρώτες k θέσεις και False στις υπόλοιπες:

def count_true_values( booleanList ) :
    true_values = 0
    for item in booleanList :
        if item :                       # ή: if item == True
            true_values = true_values + 1
    return true_values

def swapBooleanbyCounting( List ):
    N = len( List )
    true_values = count_true_values( List )
    for i in range(true_values):
        List[ i ] = True
    for i in range(true_values, N):
        List[ i ] = False
    return List

print swapBooleanbyCounting([False, True, False, False, True, True])
# [True, True, True, False, False, False]

(Παραλλαγή μέτρησης: επειδή True = 1 και False = 0, true_values = true_values + item.)
2ος τρόπος — με δύο δείκτες και αντιμεταθέσεις: left στην αρχή, right στο τέλος· όσο left < right: αν αριστερά υπάρχει False και δεξιά True τα αντιμεταθέτουμε και κινούμε και τους δύο δείκτες· αν δεξιά είναι False κατεβάζουμε το right· αλλιώς (αριστερά True) ανεβάζουμε το left:

def swapBooleanbyComparison( List ):
    N = len( List )
    left = 0
    right = N-1
    while left < right:
        if List[ right ] == True and List[ left ] == False :
            List[ left ], List[ right ] = List[ right ], List[ left ]
            left = left + 1
            right = right - 1
        elif List[ right ] == False :
            right = right - 1
        else :
            left = left + 1
    return List

Και οι δύο τρόποι διατρέχουν τη λίστα μία φορά· ο δεύτερος διατηρεί τα ίδια αντικείμενα (χρήσιμο αν αντί για True/False είχαμε εγγραφές με λογικό πεδίο).

Σύνοψη: Μέτρηση των True (k) και επανεγγραφή: True στις πρώτες k θέσεις, False στις υπόλοιπες· ή δύο δείκτες left/right με αντιμετάθεση των (False αριστερά, True δεξιά).

Κριτήρια αξιολόγησης:

Λειτουργικός κώδικας με ένα πέρασμα· η μέτρηση αρκεί.

Δραστηριότητα 6 — Διαχωρισμός και μετά εναλλάξ True, False, True, False…

Ερώτηση: Να γράψετε ένα πρόγραμμα σε Python το οποίο θα δέχεται μια λίστα με λογικές τιμές True/False και στη συνέχεια θα καλεί την συνάρτηση του προηγούμενου ερωτήματος, ώστε να τοποθετηθούν τα True πριν από τα False. Στη συνέχεια θα τοποθετεί τις τιμές αυτές εναλλάξ, δηλαδή True, False, True, False, κ.λπ.

Απάντηση:

Ανάγνωση της λίστας: συνάρτηση readList() που διαβάζει τιμές μέχρι να δοθεί None (η input() της Python 2 αποτιμά την είσοδο, άρα ο χρήστης πληκτρολογεί True / False / None). Θα χρησιμοποιηθεί και στις δραστηριότητες 9-10.

def readList( ) :
    print "* Για το τέλος δώσε την τιμή None *"
    index = 0
    L = []
    value = input("L[" + str(index) + "] = ")
    while value != None :
        L.append(value)
        index += 1
        value = input("L[" + str(index) + "] = ")
    return L

Πρόγραμμα: ① καλούμε τη swapBooleanbyCounting (δραστηριότητα 5) — True μπροστά, False πίσω· ② για την εναλλάξ τοποθέτηση, το πλήθος των ζευγών (True, False) είναι όσο η λιγότερο συχνή τιμή: αν τα True είναι λιγότερα από τα μισά (2·k < N) τα ζεύγη είναι k, αλλιώς N−k· γράφουμε True, False εναλλάξ στις πρώτες 2·ζεύγη θέσεις και στις υπόλοιπες την τιμή που περισσεύει:

def program6( ):
    List = readList( )
    N = len( List )
    List = swapBooleanbyCounting( List )        # βήμα 1: True πριν από False
    print "Μετά τον διαχωρισμό:", List
    true_values = count_true_values( List )
    if 2*true_values < N :                       # τα True είναι τα λιγότερα
        couples = true_values
        rest = False                             # περισσεύουν False
    else :
        couples = N - true_values                # τα False είναι τα λιγότερα (ή ίσα)
        rest = True                              # περισσεύουν True
    for i in range(0, 2*couples, 2):             # βήμα 2: εναλλάξ
        List[ i ] = True
        List[ i+1 ] = False
    for i in range(2*couples, N):                # ό,τι περισσεύει
        List[ i ] = rest
    print "Εναλλάξ:", List
    return List

program6()

Παράδειγμα: [F, T, F, F, T, T] → διαχωρισμός [T, T, T, F, F, F] → 3 ζεύγη → [T, F, T, F, T, F]. Για [T, F, F, F, F]: 1 ζεύγος → [T, F, F, F, F] (τα 3 F που περισσεύουν στο τέλος).
Η λύση δεν κάνει συγκρίσεις στοιχείων για την εναλλάξ τοποθέτηση — μόνο μετρά, όπως προτείνουν οι επίσημες λύσεις («με τις λιγότερες δυνατές συγκρίσεις»).

Σύνοψη: Διάβασμα λίστας ως None· κλήση της swapBooleanbyCounting· πλήθος ζευγών = min(True, False)· επανεγγραφή True, False εναλλάξ στις 2·ζεύγη πρώτες θέσεις και η περισσευούμενη τιμή στις υπόλοιπες.

Κριτήρια αξιολόγησης:

Σωστή χρήση της συνάρτησης της Δρ. 5 + σωστή διαχείριση της περίσσειας τιμών.

Δραστηριότητα 7 — Εναλλάξ True/False → True πριν από False, χωρίς σύγκριση και if

Ερώτηση: Ας υποθέσουμε ότι σας δίνεται μια λίστα στην Python η οποία περιέχει λογικές τιμές True/False εναλλάξ. Επίσης, το πλήθος των True είναι ίσο με το πλήθος των False. Να γράψετε αλγόριθμο, σε Python, ο οποίος δεδομένης της παραπάνω δομής της λίστας, θα τοποθετεί τα True πριν από τα False. Δεν επιτρέπεται να κάνετε καμία σύγκριση ούτε να χρησιμοποιήσετε τη δομή if.

Απάντηση:

Εκμετάλλευση της δομής: αφού οι τιμές είναι μισές True – μισές False, το τελικό αποτέλεσμα είναι γνωστό εκ των προτέρων: οι πρώτες N/2 θέσεις True, οι υπόλοιπες False. Δεν χρειάζεται να «δούμε» καν τα στοιχεία — άρα ούτε σύγκριση ούτε if:

def splitBoolean_byCounting( List ):
    mid = len(List) / 2            # ακέραια διαίρεση (Python 2)· Python 3: //
    for index in range(mid):
        List[ index ] = True
        List[ index + mid ] = False
    return List

print splitBoolean_byCounting([True, False, True, False, True, False])
# [True, True, True, False, False, False]

Εναλλακτικά, με μετακινήσεις της εναλλάξ δομής: τα True βρίσκονται στις άρτιες θέσεις 0, 2, 4, … και τα False στις περιττές. Το True της θέσης 2k πρέπει να πάει στη θέση k και το False της θέσης 2k+1 στη θέση mid+k — πάλι χωρίς if: for k in range(mid): List[k], List[mid+k] = List[2*k], List[2*k+1] (με προσοχή στη σειρά ανάθεσης: αντιγράφουμε πρώτα σε νέα λίστα για να μην «πατήσουμε» τιμές που δεν έχουμε διαβάσει ακόμη — π.χ. new = [True]*mid + [False]*mid).
Με τον αλγόριθμο ταξινόμησης (επίσημες λύσεις, 2ος τρόπος): αρκούν N/2 περάσματα της ευθείας ανταλλαγής με συνθήκη List[j] > List[j-1] (True > False) — αλλά αυτό χρησιμοποιεί σύγκριση και if, οπότε δεν ικανοποιεί τον περιορισμό της εκφώνησης· αναφέρεται μόνο για την «ελάχιστες μετακινήσεις» παραλλαγή.

Σύνοψη: Οι πρώτες N/2 θέσεις γίνονται True και οι υπόλοιπες False με έναν βρόχο for (mid = N/2), χωρίς καμία σύγκριση ή if — η δομή της λίστας κάνει το αποτέλεσμα γνωστό εκ των προτέρων.

Κριτήρια αξιολόγησης:

Κώδικας χωρίς if/συγκρίσεις· αιτιολόγηση από την υπόθεση «ίσο πλήθος».

Δραστηριότητα 8 — Το πρόβλημα της ολλανδικής σημαίας (R, W, B)

Ερώτηση: Το πρόβλημα της ολλανδικής σημαίας αναφέρεται στην αναδιάταξη μιας λίστας γραμμάτων, η οποία περιέχει μόνο τους χαρακτήρες R, W, B. (Red, White, Blue), έτσι ώστε όλα τα R να βρίσκονται πριν από τα W και όλα τα W να βρίσκονται πριν από B. Να τροποποιήσετε έναν από τους αλγορίθμους ταξινόμησης που παρουσιάστηκαν σε αυτήν την ενότητα, ώστε να επιλύει αυτό το πρόβλημα.

Απάντηση:

Είναι μια ταξινόμηση με ειδική διάταξη R < W < B (όχι η αλφαβητική, όπου B < R < W). Τροποποιούμε την ευθείας ανταλλαγής: αντί για A[j] < A[j-1], η συνθήκη αντιμετάθεσης γίνεται «το ζευγάρι (A[j−1], A[j]) δεν ακολουθεί τη σειρά R W B», δηλαδή οι τρεις «ανάποδες» περιπτώσεις (W πριν από R, B πριν από W, B πριν από R):

def dutchFlag( L ):
    N = len( L )
    for i in range( N-1 ):
        for j in range(N-1, i, -1) :
            if (L[ j ] == 'R' and L[ j-1 ] == 'W') \
            or (L[ j ] == 'W' and L[ j-1 ] == 'B') \
            or (L[ j ] == 'R' and L[ j-1 ] == 'B') :
                L[ j-1 ], L[ j ] = L[ j ], L[ j-1 ]
    return L

print dutchFlag(['B', 'W', 'R', 'B', 'R', 'W', 'B', 'R'])
# ['R', 'R', 'R', 'W', 'W', 'B', 'B', 'B']

(Το \ στο τέλος γραμμής συνεχίζει την εντολή στην επόμενη γραμμή.)
Κομψότερη παραλλαγή: ορίζουμε την τάξη κάθε χρώματος με ένα λεξικό rank = {'R': 0, 'W': 1, 'B': 2} και ταξινομούμε με τον αμετάβλητο αλγόριθμο συγκρίνοντας rank[L[j]] < rank[L[j-1]] — ίδια λογική με τη δραστηριότητα 2: αλλάζει μόνο η «στοιχειώδης» σύγκριση.
Το ίδιο πετυχαίνεται και με μέτρηση (όπως στη δρ. 5): μετράμε πόσα R, W, B υπάρχουν και ξαναγράφουμε τη λίστα — ένα πέρασμα, χωρίς αντιμεταθέσεις.

Σύνοψη: Ευθείας ανταλλαγής με συνθήκη αντιμετάθεσης «το ζευγάρι παραβιάζει τη σειρά R-W-B»: (R μετά από W) ή (W μετά από B) ή (R μετά από B)· ισοδύναμα σύγκριση με τάξεις rank = {R:0, W:1, B:2}.

Κριτήρια αξιολόγησης:

Σωστή τριπλή συνθήκη (ή rank) μέσα στον αλγόριθμο φυσαλίδας.

Δραστηριότητα 9 — Ανάγνωση αριθμών μέχρι None και τοποθέτηση σε φθίνουσα λίστα

Ερώτηση: Να γράψετε μια συνάρτηση σε Python η οποία διαβάζει αριθμούς από το χρήστη μέχρι να δοθεί η τιμή None, τους οποίους τοποθετεί σε μια λίστα σε φθίνουσα σειρά, την οποία και επιστρέφει. Κάθε φορά που διαβάζει έναν νέο αριθμό τον τοποθετεί στη σωστή θέση στην ήδη ταξινομημένη λίστα, ώστε να διατηρείται η φθίνουσα διάταξη των στοιχείων της λίστας. Ποιον αλγόριθμο ταξινόμησης σας θυμίζει η παραπάνω λειτουργία; Σε τι διαφέρει η συνάρτηση που θα αναπτύξετε από τον αλγόριθμο αυτόν;

Απάντηση:

Κάθε νέος αριθμός προστίθεται στο τέλος της λίστας και στη συνέχεια «σπρώχνεται» προς την αρχή όσο τα προηγούμενα στοιχεία είναι μικρότερα (φθίνουσα διάταξη) — αναζήτηση της θέσης και μετακίνηση (shift) ταυτόχρονα, όπως στη συνοπτική έκδοση insertionSortOpt (σελ. 83) με τη σύγκριση αντεστραμμένη:

def insertDescending( ) :
    print "* Δώσε την τιμή None για να σταματήσεις *"
    L = []
    number = input("number = ")
    while number != None :
        L.append(number)                  # νέο στοιχείο στο τέλος
        value = L[ len(L) - 1 ]
        j = len(L) - 1
        while j > 0 and L[ j-1 ] < value :   # όσο το προηγούμενο είναι μικρότερο
            L[ j ] = L[ j-1 ]                #   μετακίνησέ το μία θέση δεξιά
            j = j - 1
        L[ j ] = value                    # τοποθέτηση στη σωστή θέση
        number = input("number = ")
    return L

print insertDescending()      # π.χ. είσοδος 5, 12, 3, 12, 8, None -> [12, 12, 8, 5, 3]

Ποιον αλγόριθμο θυμίζει: την ταξινόμηση με εισαγωγή (insertion sort) — βρίσκουμε τη θέση και παρεμβάλλουμε το νέο στοιχείο στο ήδη ταξινομημένο τμήμα.
Σε τι διαφέρει: ① ο κλασικός αλγόριθμος δέχεται μια έτοιμη λίστα σταθερού μεγέθους και τη διατρέχει με for i in range(1, len(array))· εδώ τα στοιχεία έρχονται ένα-ένα από τον χρήστη, το μέγεθος δεν είναι γνωστό εκ των προτέρων και η λίστα παραμένει ταξινομημένη σε κάθε στιγμή — δηλαδή είναι η άμεση (online) εκδοχή του αλγορίθμου, κατάλληλη για συνεχή ροή δεδομένων (σελ. 84)· ② η διάταξη είναι φθίνουσα (σύγκριση < αντί >)· ③ δεν χρειάζεται να ξαναταξινομηθεί όλη η λίστα σε κάθε νέο στοιχείο.

Σύνοψη: Κάθε νέος αριθμός μπαίνει στο τέλος και μετακινείται προς την αρχή όσο L[j−1] < value (shift), όπως στην ταξινόμηση με εισαγωγή· διαφέρει στο ότι είναι online (άγνωστο πλήθος, η λίστα πάντα ταξινομημένη) και φθίνουσα.

Κριτήρια αξιολόγησης:

Κώδικας με while j > 0 and L[j-1] < value· ονομασία «ταξινόμηση με εισαγωγή» + διαφορές (online, φθίνουσα).

Δραστηριότητα 10 — Δύο λίστες: ταξινόμηση της Α και πλήθος κοινών με τη Β (δυαδική αναζήτηση)

Ερώτηση: Να γράψετε ένα πρόγραμμα το οποίο θα διαβάζει από το χρήστη δύο λίστες αριθμών Α και Β και θα ταξινομεί σε αύξουσα σειρά τους αριθμούς της λίστας Α. Στη συνέχεια θα εμφανίζει πόσοι από τους αριθμούς της λίστας Β εμφανίζονται στην λίστα Α. Υπόδειξη: Να θεωρήσετε ότι οι αριθμοί της λίστας Β είναι όλοι διαφορετικοί μεταξύ τους. Επίσης, να εκμεταλλευτείτε το γεγονός ότι τα στοιχεία της λίστας Α είναι ταξινομημένα σε αύξουσα σειρά. Η εισαγωγή των αριθμών για κάθε λίστα σταματάει όταν δοθεί η τιμή None.

Απάντηση:

Σχέδιο: ① ανάγνωση των δύο λιστών με τη readList() (δραστηριότητα 6)· ② ταξινόμηση της Α με ευθείας ανταλλαγής· ③ για κάθε στοιχείο της Β, έλεγχος ύπαρξης στην ταξινομημένη Α με δυαδική αναζήτηση (αυτό είναι το «εκμεταλλευτείτε τη διάταξη») και μέτρηση· επειδή τα στοιχεία της Β είναι όλα διαφορετικά, κάθε επιτυχία μετρά έναν διαφορετικό κοινό αριθμό.

def bubbleSort( A ):
    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 ]

def binarySearch( A, key ):
    first = 0
    last = len( A ) - 1
    found = False
    while first <= last and not found:
        mid = (first + last) / 2
        if A[ mid ] == key :
            found = True
        elif A[ mid ] < key :
            first = mid + 1
        else:
            last = mid - 1
    return found

# Κύριο πρόγραμμα
print "Λίστα Α:"
A = readList()
print "Λίστα Β:"
B = readList()
bubbleSort( A )
print "Η ταξινομημένη λίστα Α:", A
common = 0
for key in B :
    if binarySearch( A, key ) :
        common = common + 1
print "Αριθμοί της Β που υπάρχουν στην Α:", common

Παράδειγμα: Α = [30, 5, 17, 45, 10], Β = [45, 7, 10, 60] → Α ταξινομημένη [5, 10, 17, 30, 45] → κοινοί: 45 και 10 → 2.
Γιατί δυαδική και όχι σειριακή αναζήτηση: για κάθε στοιχείο της Β χρειάζονται το πολύ log₂|A| συγκρίσεις αντί για |A|· γι’ αυτό «πληρώνουμε» πρώτα την ταξινόμηση της Α. Το πρόγραμμα λειτουργεί απαράλλακτο και για αλφαριθμητικά (πολυμορφισμός, σελ. 72).

Σύνοψη: readList για Α και Β· bubbleSort(A)· για κάθε key της Β binarySearch(A, key) και μέτρηση· εμφάνιση της ταξινομημένης Α και του πλήθους.

Κριτήρια αξιολόγησης:

Ταξινόμηση + δυαδική αναζήτηση (όχι σειριακή) + σωστός μετρητής.

Ερώτηση 1 — Λειτουργία της δυαδικής αναζήτησης με παράδειγμα

Ερώτηση: Να περιγράψετε τη λειτουργία του αλγορίθμου της δυαδικής αναζήτησης, δίνοντάς και ένα παράδειγμα εκτέλεσής του.

Απάντηση:

Λειτουργία (σελ. 64, 69-71): η δυαδική αναζήτηση αναζητά ένα στοιχείο (key) σε ταξινομημένη λίστα εκμεταλλευόμενη τη διάταξη. Κρατά δύο δείκτες, first (αρχή) και last (τέλος) του διαστήματος αναζήτησης, και σε κάθε βήμα: ① υπολογίζει το μέσο mid = (first + last) / 2· ② αν array[mid] == key το στοιχείο βρέθηκε· ③ αν array[mid] < key, το ζητούμενο είναι δεξιά → first = mid + 1· ④ αλλιώς είναι αριστερά → last = mid − 1. Επαναλαμβάνει όσο first <= last και δεν βρέθηκε. Σε κάθε βήμα ο χώρος αναζήτησης μειώνεται στο μισό, γι’ αυτό λέγεται «δυαδική». Αν το διάστημα αδειάσει (first > last) το στοιχείο δεν υπάρχει (επιστροφή False ή θέση −1).
Παράδειγμα εκτέλεσης (σελ. 70): λίστα [5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70] (θέσεις 0-13), key = 45. Βήμα 1: first = 0, last = 13, mid = 6 → array[6] = 35 < 45 → first = 7. Βήμα 2: first = 7, last = 13, mid = 10 → array[10] = 60 > 45 → last = 9. Βήμα 3: first = 7, last = 9, mid = 8 → array[8] = 45 → βρέθηκε στη θέση 8, με 3 συγκρίσεις (η σειριακή θα χρειαζόταν 9).
Στο παιχνίδι «μάντεψε τον αριθμό» στο [1,16] με μυστικό το 11: 8 (>), 12 (<), 10 (>), 11 ✓ — 4 συγκρίσεις αντί 16· γενικά περίπου log₂N (1024 στοιχεία → 10).

Σύνοψη: (ενδεικτική) Διχοτόμηση ταξινομημένου διαστήματος [first, last] με mid = (first+last)/2: ίσο → βρέθηκε, μικρότερο → first = mid+1, μεγαλύτερο → last = mid−1, μέχρι first > last· παράδειγμα: 45 στη λίστα των 14 → 35, 60, 45 (3 συγκρίσεις).

Κριτήρια αξιολόγησης:

Τα τέσσερα βήματα + η προϋπόθεση ταξινόμησης + πλήρες ίχνος εκτέλεσης.

Ερώτηση 2 — Λειτουργία της ταξινόμησης ευθείας ανταλλαγής με παράδειγμα

Ερώτηση: Να περιγράψετε τη λειτουργία του αλγορίθμου της ταξινόμησης ευθείας ανταλλαγής και να δώσετε ένα παράδειγμα εκτέλεσής του.

Απάντηση:

Λειτουργία (σελ. 73-78): ο αλγόριθμος βασίζεται στη σύγκριση και αντιμετάθεση γειτονικών ζευγών που δεν ακολουθούν τη διάταξη. Σε κάθε πέρασμα (εξωτερική επανάληψη i) διατρέχουμε τη λίστα από το τέλος προς την αρχή (for j in range(N-1, i, -1)) και, αν A[j] < A[j-1], αντιμεταθέτουμε τα δύο στοιχεία. Έτσι το μικρότερο στοιχείο του αταξινόμητου τμήματος «ανεβαίνει σαν φυσαλίδα» στη θέση i. Χρειάζονται Ν−1 περάσματα (στο τελευταίο το εναπομένον στοιχείο είναι ήδη στη θέση του) και σε κάθε πέρασμα η εσωτερική επανάληψη φτάνει μέχρι j = i+1, γιατί οι θέσεις 0…i−1 είναι ήδη ταξινομημένες. Θεωρείται από τους πιο αργούς, αλλά μπορεί να τερματίζει νωρίς με λογική μεταβλητή.
Παράδειγμα εκτέλεσης — λίστα [21, 13, 8, 5, 3, 2] (Εικ. 5-2, 5-3, Ν = 6): Πέρασμα i = 0: j = 5: 2 < 3 → [21,13,8,5,2,3]· j = 4: 2 < 5 → [21,13,8,2,5,3]· j = 3: 2 < 8 → [21,13,2,8,5,3]· j = 2: 2 < 13 → [21,2,13,8,5,3]· j = 1: 2 < 21 → [2,21,13,8,5,3] — το 2 στη θέση 0. Πέρασμα i = 1: το 3 ανεβαίνει → [2, 3, 21, 13, 8, 5]. i = 2: [2, 3, 5, 21, 13, 8]. i = 3: [2, 3, 5, 8, 21, 13]. i = 4: [2, 3, 5, 8, 13, 21] — ταξινομημένη μετά από Ν−1 = 5 περάσματα.
Στο μικρό παράδειγμα των μαθητών (σελ. 73), ο «Αλέξανδρος» από το τέλος συγκρίνεται με τον μπροστινό του και αλλάζει θέση μέχρι τη θέση 0 — ένα πέρασμα.

Σύνοψη: (ενδεικτική) Σύγκριση/αντιμετάθεση γειτονικών από το τέλος προς την αρχή· σε κάθε πέρασμα το μικρότερο ανεβαίνει στη θέση i· Ν−1 περάσματα, εσωτερικό range(N−1, i, −1)· παράδειγμα [21,13,8,5,3,2] → μετά το 1ο πέρασμα [2,21,13,8,5,3] … → [2,3,5,8,13,21].

Κριτήρια αξιολόγησης:

Περιγραφή + ίχνος με τουλάχιστον το πρώτο πέρασμα αναλυτικά.

Ερώτηση 3 — Λειτουργία της ταξινόμησης με εισαγωγή με παράδειγμα

Ερώτηση: Να περιγράψετε τη λειτουργία του αλγορίθμου της ταξινόμησης με εισαγωγή και να δώσετε ένα παράδειγμα εκτέλεσής του.

Απάντηση:

Λειτουργία (σελ. 80-84): η λίστα χωρίζεται σε ταξινομημένο τμήμα (αρχικά μόνο το πρώτο στοιχείο) και αταξινόμητο. Για κάθε επόμενο στοιχείο value = array[i] (i = 1 … N−1): ① αναζητούμε τη θέση του μέσα στο ταξινομημένο τμήμα, σαρώνοντάς το από δεξιά προς αριστερά όσο τα στοιχεία είναι μεγαλύτερα από το value· ② μετακινούμε αυτά τα μεγαλύτερα στοιχεία μία θέση δεξιά (shift), για να ανοίξει χώρος· ③ τοποθετούμε το value στη θέση που άνοιξε. Στη συνοπτική έκδοση αναζήτηση και μετακίνηση γίνονται ταυτόχρονα (while j > 0 and array[j-1] > value: array[j] = array[j-1]; j -= 1 και τέλος array[j] = value). Το ταξινομημένο τμήμα είναι ταξινομημένο μεταξύ των στοιχείων του, αλλά όχι στις τελικές θέσεις (μπορεί να έρθει μικρότερο στοιχείο και να τα σπρώξει).
Παράδειγμα εκτέλεσης — λίστα [13, 8, 21, 3, 10, 2] (Εικ. 5-6): i = 1, value = 8: το 13 > 8 → μετακίνηση, 8 στη θέση 0 → [8, 13, 21, 3, 10, 2]. i = 2, value = 21: 13 < 21 → μένει → [8, 13, 21, 3, 10, 2]. i = 3, value = 3: 21, 13, 8 όλα > 3 → μετακινούνται, 3 στη θέση 0 → [3, 8, 13, 21, 10, 2]. i = 4, value = 10: 21 και 13 > 10 → μετακίνηση, 8 < 10 → στοπ → [3, 8, 10, 13, 21, 2]. i = 5, value = 2: όλα > 2 → 2 στη θέση 0 → [2, 3, 8, 10, 13, 21] — ταξινομημένη.
Παρατήρηση: το πλήθος συγκρίσεων/μετακινήσεων ανά βήμα εξαρτάται από τα δεδομένα (i = 2: καμία μετακίνηση, i = 5: πέντε) — γι’ αυτό ο αλγόριθμος είναι πολύ γρήγορος σε σχεδόν ταξινομημένες λίστες.

Σύνοψη: (ενδεικτική) Για κάθε στοιχείο από το 2ο και μετά: αναζήτηση της θέσης του στο ταξινομημένο τμήμα από δεξιά, shift των μεγαλύτερων μία θέση δεξιά, τοποθέτηση· παράδειγμα [13,8,21,3,10,2] → [8,13,21,3,10,2] → … → [2,3,8,10,13,21].

Κριτήρια αξιολόγησης:

Τρία βήματα (αναζήτηση, shift, τοποθέτηση) + ίχνος ανά i.

Ερώτηση 4 — Συνεχής ροή δεδομένων με μόνιμα ταξινομημένα δεδομένα

Ερώτηση: Αν έχουμε συνεχή ροή δεδομένων, αλλά θέλουμε τα δεδομένα μας να είναι μονίμως ταξινομημένα, ποιον αλγόριθμο θα χρησιμοποιήσουμε και γιατί;

Απάντηση:

Θα χρησιμοποιήσουμε την ταξινόμηση με εισαγωγή (insertion sort).
Γιατί (σελ. 84): ο αλγόριθμος δεν χρειάζεται να γνωρίζει εκ των προτέρων όλα τα δεδομένα ούτε το μέγεθος της λίστας — κάθε νέο στοιχείο που φτάνει παρεμβάλλεται στη σωστή θέση του ήδη ταξινομημένου τμήματος (αναζήτηση θέσης + μετακίνηση των μεγαλύτερων), οπότε η λίστα παραμένει ταξινομημένη σε κάθε στιγμή, χωρίς να ξαναταξινομείται από την αρχή. Το βιβλίο σημειώνει ότι «μπορεί να εφαρμοστεί σε λίστες οι οποίες δεν έχουν σταθερό μέγεθος και υλοποιούν συνεχή ροή δεδομένων, όπως τα δίκτυα αισθητήρων»· οι αλγόριθμοι που επεξεργάζονται συνεχείς ροές λέγονται άμεσοι αλγόριθμοι (online algorithms).
Αντίθετα, η ταξινόμηση με επιλογή και η ευθείας ανταλλαγής απαιτούν ολόκληρη τη λίστα και θα έπρεπε να επανεκτελούνται σε κάθε νέα άφιξη (η επιλογή μάλιστα με σταθερό πλήθος συγκρίσεων, ακόμη και σε ήδη ταξινομημένα δεδομένα). Παράδειγμα υλοποίησης: η δραστηριότητα 9 (ανάγνωση μέχρι None με άμεση τοποθέτηση).

Σύνοψη: (ενδεικτική) Την ταξινόμηση με εισαγωγή: κάθε νέο στοιχείο τοποθετείται αμέσως στη σωστή θέση του ταξινομημένου τμήματος, χωρίς γνώση του πλήθους και χωρίς επαναταξινόμηση — online αλγόριθμος για ροές δεδομένων (δίκτυα αισθητήρων).

Κριτήρια αξιολόγησης:

Ονομασία + αιτιολόγηση «σταδιακή/online» + αντιπαραβολή με επιλογή/φυσαλίδα.

Ερώτηση 5 — Η προϋπόθεση της δυαδικής αναζήτησης

Ερώτηση: Ποια είναι η απαραίτητη προϋπόθεση για να χρησιμοποιήσουμε τη δυαδική αναζήτηση;

Απάντηση:

Η απαραίτητη προϋπόθεση είναι τα στοιχεία της συλλογής να είναι ταξινομημένα — διατεταγμένα σε αύξουσα ή φθίνουσα σειρά (σελ. 70: «μπορεί να εφαρμοστεί μόνο όταν τα στοιχεία είναι διατεταγμένα σε αύξουσα ή φθίνουσα σειρά»· σελ. 72: «χρησιμοποιείται μόνο σε ταξινομημένες συλλογές δεδομένων»).
Γιατί: ο αλγόριθμος αποφασίζει προς ποια πλευρά του μέσου θα συνεχίσει (array[mid] < key → δεξιά, αλλιώς αριστερά)· η απόφαση αυτή είναι σωστή μόνο αν όλα τα στοιχεία αριστερά του mid είναι μικρότερα και δεξιά μεγαλύτερα, δηλαδή αν η λίστα είναι ταξινομημένη. Σε μη ταξινομημένη λίστα θα απέρριπτε λανθασμένα το μισό που περιέχει το ζητούμενο.
Συνέπεια (σύνοψη, σελ. 88): για μη ταξινομημένα δεδομένα πρέπει πρώτα να ταξινομηθούν (π.χ. δραστηριότητα 10: ταξινόμηση της Α πριν την αναζήτηση). Η διάταξη μπορεί να είναι αριθμητική ή αλφαβητική — αρκεί να ορίζονται οι τελεστές == και <.

Σύνοψη: (ενδεικτική) Τα στοιχεία να είναι ταξινομημένα (αύξουσα ή φθίνουσα σειρά) — αλλιώς η επιλογή «αριστερά/δεξιά του μέσου» δεν είναι έγκυρη· μη ταξινομημένα δεδομένα ταξινομούνται πρώτα.

Κριτήρια αξιολόγησης:

Η προϋπόθεση + ο λόγος + τι κάνουμε αν δεν ισχύει.

Προηγούμενο Στοιχείο

Επιστροφή στην Ενότητα

Επόμενο Στοιχείο