Σημειωματάριο Τρίτης 1 Δεκμεβρίου 2015

Bubble sort

Εδώ δείχνουμε το πώς λειτουργεί μια πολύ απλή μέθοδος ταξινόμησης, η bubble sort. Έχουμε να ταξινομήσουμε μια λίστα L αριθμών σε αύξουσα σειρά. Ο τρόπος που το κάνουμε είναι ο εξής. Κάνουμε πολλαπλές συγκρίσεις ανάμεσα σε ζεύγη θέσεων της λίστας. Σε κάθε τέτοια σύγκριση αν τα περιεχόμενα των δύο θέσεων δεν είναι στη σωστή σειρά τότε εναλλάσουμε τα περιεχόμενά τους. Έχει βέβαια μεγάλη σημασία το με ποια σειρά κάνουμε τους ελέγχους αυτούς. Αν n είναι το μήκος της λίστας (θέσεις από 0 έως n-1) τότε κάνουμε τους παρακάτω ελέγχους ζευγών:

(0, 1), (1, 2), (2, 3), ... , (n-4, n-3), (n-3, n-2), (n-2, n-1),
(0, 1), (1, 2), (2, 3), ... , (n-4, n-3), (n-3, n-2),
(0, 1), (1, 2), (2, 3), ... , (n-4, n-3),
...
(0, 1), (1, 2), (2, 3),
(0, 1), (1, 2),
(0, 1)

Η βασική παρατήρηση τώρα είναι ότι στο τέλος της πρώτης σειράς ελέγχων το μεγαλύτερο στοιχείο της L (ή ένα από τα μεγαλύτερα, αν έχει παραπάνω από ένα) έχει πάει στη θέση του, δηλ. στη θέση n-1. Μετά το τέλος της δεύτερης σειράς ελέγχων έχει πάει στη θέση του το δεύτερο μεγαλύτερο στοιχείο της L, δηλ. στη θέση n-2, κλπ. Έτσι μετά τον τελευταίο έλεγχο που γίνεται η λίστα είναι πλήρως ταξινομημένη σε αύξουσα σειρά.

In [44]:

def bsort(L):
    """
    Ταξινομεί τη λίστα L σε αύξουσα σειρά
    """
    for n in range(len(L)-1, 0, -1): # η μεταβλητή n παίζει το ρόλο της τελευταίας θέσης της λίστας που δεν έχει ακόμη
                                     # πάρει το τελικό της περιεχόμενο. Αρχίζει από την τελευταία θέση και μειώνεται κατά
                                     # ένα σε κάθε βήμα.
        for k in range(n): # Αυτό το loop είναι υπεύθυνο για να κάνει μια σειρά ελέγχων από (0,1), (1, 2), ... , (n-1, n)
            if L[k]>L[k+1]: # Αντα περιεχόμενα δεν είναι στη σωστή σειρά
                L[k], L[k+1] = L[k+1], L[k] # τα ανταλλάσουμε
                
L = [5, 4, 3, 3.2, -1, 2, 2, 1]       
bsort(L)

print L

[-1, 1, 2, 2, 3, 3.2, 4, 5]

Πολλές φορές έχουμε να ταξινομήσουμε μια λίστα που τα στοιχεία της δεν είναι αριθμοί ή strings, αλλά πιο πολύπλοκα αντικείμενα, και η σχέση διάταξης ανάμεσά τους δεν είναι προφανής. Σε αυτό το παράδειγμα βλέπουμε πώς πρέπει να τροποποιηθεί η bubble sort που δώσαμε προηγουμένως για να ταξινομήσουμε μια λίστα από ζεύγη (λίστες αριθμών μήκους δύο), όπου η σχέση διάταξης ανάμεσα στα ζεύγη είναι η λεγόμενη λεξικογραφική διάταξη: $ (x_1, y_1) (x_2, y_2) (x_1 < x_2) (x_1 = x_2 y_1 y_2). $

Με απλά λόγια το για να συγκρίνουμε δύο ζεύγη συγκρίνουμε πρώτα τα πρώτα μέλη τους. Αν μπορούμε να βγάλουμε συμπέρασμα από αυτά τελειώσαμε, αλλιώς κοιτάμε και τα δεύτερα μέλη τους.

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

In [45]:

def bsort(L):
    """
    Ταξινομεί τη λίστα L (από ζεύγη αριθμών) σε αύξουσα σειρά
    """
    for n in range(len(L)-1, 0, -1):
        for k in range(n):
            [x1, y1] = L[k]
            [x2, y2] = L[k+1]
            if x2 <= x1 and ( x1 != x2 or y2 < y1 ): # Η μόνη γραμμή που άλλαξε από το προηγούμενο
                L[k], L[k+1] = L[k+1], L[k]
                
L = [ [1, 2], [1, -2], [0, 0], [4, 3] ]       
bsort(L)

print L

[[0, 0], [1, -2], [1, 2], [4, 3]]

Από την εμπειρία μας από την προηγούμενη αλλαγή φαίνεται ότι μπορούμε να κάνουμε τη συνάρτηση bsort πολύ πιο γενική, ώστε να μη χρειάζεται να την τροποποιούμε κάθε φορά που είναι να ταξινομήσουμε με διαφορετικό τρόπο.

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

Το όνομα της παραμέτρου αυτής στην bsort είναι f, και η συνάρτηση f πρέπει να παίρνει δύο ορίσματα, έστω a και b. Τα a και b αυτά θα είναι οι τιμές που υπάρχουν σε δύο θέσεις της λίστας (a για τη θέση που προηγείται και b για τη θέση που έπεται). Η συνάρτηση f πρέπει να επιστρέφει True αν και μόνο αν τα στοιχεία a και b δεν είναι στη σωστή σειρά, αλλιώς επιστρέφει False.

Και πάλι η μόνη αλλαγή που έχουμε να κάνουμε στη bsort είναι να αλλάξουμε τη γραμμή όπου ελέγχεται το αν τα περιεχόμενα των δύο θέσεων είναι στη σωστή σειρά. Αυτό τώρα γίνεται απλά με μια κλήση στην f.

Τέλος, για να χρησιμοποιήσουμε αυτή τη γενική bsort για να ταξινομήσουμε με λεξικογραφικό διάταξη την ίδια λίστα όπως και πριν πρέπει να γράψουμε τη συνάρτηση f την οποία περνάμε στην bsort. Αυτή είναι η συνάρτηση lex που φαίνεται παρακάτω και η οποία υλοποιεί ακριβώς τον έλεγχο που πρέπει για τη λεξικογραφική διάταξη (συγκρίνετε με το αμέσως προηγούμενο πρόγραμμα).

In [47]:

def bsort(L, f):
    """
    Ταξινομεί τη λίστα L (από ζεύγη αριθμών) σε αύξουσα σειρά.
    Η συνάρτηση f(a, b) είναι True αν και μόνο αν τα a, b δεν είναι στη σωστή σειρά,
    δηλ. δεν ισχύει ότι a <= b.
    """
    for n in range(len(L)-1, 0, -1):
        for k in range(n):
            [x1, y1] = L[k]
            [x2, y2] = L[k+1]
            if f(L[k], L[k+1]): # Μόνο αυτή η γραμμή έχει αλλάξει από πριν
                L[k], L[k+1] = L[k+1], L[k]

def lex(a, b):
    """
    Τα a, b είναι λίστες δύο αριθμών. Επιστρέφει True αν και μόνο αν το a δεν είναι
    λεξικογραφικά μικρότερο ή ίσο του b.
    """
    [x1, y1] = a
    [x2, y2] = b
    return (x2 <= x1) and (x1 != x2 or y2 < y1)

L = [ [1, 2], [1, -2], [0, 0], [4, 3] ]       
bsort(L, lex)

print L

[[0, 0], [1, -2], [1, 2], [4, 3]]

List comprehensions

Στην python υπάρχει ένας σύντομος τρόπος ορισμού λιστών που πολλές φορές είναι και πιο σύντομος και πιο ευανάγνωστος από το να γράψουμε ένα loop για να ορίσουμε τη λίστα. Αυτά είναι τα list comprehensions, παραδείγματα από τα οποία δείχνουμε παρακάτω.

In [48]:

A = [1, 2, 3.2, 5, -1]

S = [x*x for x in A] # Η S είναι η λίστα με τα τετράγωνα των στοιχείων της λίστας A

print S

[1, 4, 10.240000000000002, 25, 1]

In [14]:

N = ["Mihalis", "Manolis", "Yannis"]

L = ["Kyrios " + x for x in N] # Προσθέτουμε το string "Kyrios " μπροστά από κάθε στοιχείο της N

print L

['Kyrios Mihalis', 'Kyrios Manolis', 'Kyrios Yannis']

In [50]:

A = [1, 2, 3]
B = [6, 9, 10, 11]

print [[x, y] for x in A for y in B] # Διπλό list comprehension. Τα x και y παίρνουν ανεξάρτητα όλες τις τιμές από
                                     # τις αντίστοιχες λίστες. Φτιάνχουμε όλα τα ζεύγη (σα καρτεσιανό γινόμενο)

print [x*y for x in A for y in B] # Διπλό list comprehension. Φτιάχνουμε όλα τα δυνατά γινόμενα ενός στοιχείου από το A
                                  # κι ενός στοιχείου από το B. Κάποια εμφανίζονται παραπάνω από μια φορά.

[[1, 6], [1, 9], [1, 10], [1, 11], [2, 6], [2, 9], [2, 10], [2, 11], [3, 6], [3, 9], [3, 10], [3, 11]]
[6, 9, 10, 11, 12, 18, 20, 22, 18, 27, 30, 33]

In [51]:

A = [1, 2, 3, 4]
B = [6, 9, 10, 11]

print [[x, y] for x in A for y in B if x%2==0] # Τα list comprehensions επιτρέπουν και μια συνθήκη if στο τέλος
                                               # που "φιλτράρει" το ποια στοιχεία θα μπούν στην τελιή λίστα.
                                               # Εδώ κρατάμε μόνο τα στοιχεία που αντιστοιχούν σε άρτιο x

[[2, 6], [2, 9], [2, 10], [2, 11], [4, 6], [4, 9], [4, 10], [4, 11]]

Γραφικά

Εδώ βλέπουμε το πώς μπορούμε να κάνουμε διάφορα σχέδια με τη συνάρτηση γραφικών pyplot (τμήμα της ευρύτερης συνάρτησης matplotlib) την οποία κάνουμε import στο πρόγραμμά μας όπως φαίνεται παρακάτω. Εδώ ο ρόλος του as plt δίπλα στην εντολή import είναι να ορίσει ένα μικρό συνώνυμο του matplotlib.pyplot ώστε να μη χρειάζεται να γράφουμε όλο αυτό το όνομα κάθε φορά που καλούμε μια συνάρτηση από αυτή τη βιβλιοθήκη αλλά μόνο το plt.

Η συνάρτηση plot, στην απλούστερή της μορφή, παίρνει ως παραμέτρους δύο λίστες αριθμών $[x_1, x_2, \ldots, x_N]$ και $[y_1, y_2, \ldots, y_N]$ και σχεδιάζει την πολυγωνική γραμμή $(x_1, y_1) \to (x_2, y_2) \to \cdots \to (x_N, y_N)$

Η συνάρτηση axis παίρνει 4 ορίσματα $x,X, y, Y$ και σχεδιάζει τους άξονες ώστε ο άξονας των $x$ να πηγαίνει από $x$ έως $X$ και ο άξονας των $y$ να πηγαίνει από $y$ έως $Y$. Αν δεν χρησιμοποιήσουμε την axis τότε το "παράθυρο" του επιπέδου που θα δούμε θα υπολογιστεί αυτόματα από τις ελάχιστες και μέγιστες τιμές των $x$ και $y$ που εμφανίζονται στο σχήμα μας (συνήθως όμως θέλουμε το παράθυρο αυτό να είναι λίγο μεγαλύτερο ώστε να φαίνεται καλά το σχήμα μας).

Ο τελικός σχεδιασμός στην οθόνη γίνεται μόνο μετά την κλήση της συνάρτησης show. Οι προηγούμενεες συναρτήσεις σχεδιάζουν ό,τι σχεδιάζουν κάπου εσωτερικά και το σχήμα τοποθετείται στην οθόνη από την show.

In [52]:

import matplotlib.pyplot as plt

plt.plot( [1, 2, 3, 4], [1, 4, 9, 16] ) # Τυπώνει την πολυγωνική γραμμή που ορίζουν τα σημεία
                                        # (1,1), (2, 4), (3, 9), (4, 16) με τη σειρά αυτή.                    
plt.axis([0, 6, 0, 20]) # Ορίζει το παράθυρο του επιπέδου που βλέπουμε να είναι το [0, 6] x [0, 20]
plt.show() # Δείχνει στην οθόνη ό,τι έχει σχεδιαστεί μέχριτώρα.

Στο επόμενο δείχνουμε πώς να κάνουμε το γράφημα μιας συνάρτησης (αυτής που ορίσαμε ως f παρακάτω) σε ένα διάστημα (το [-10,10] παρακάτω). Για να το κάνουμε αυτό θα πρέπει να βρούμε πολλά σημεία της μορφής $(x_i, y_i)$ όπου $y_i = f(x_i)$ και με τα $x_i$ να αυξάνουν και να δείξουμε την πολυγωνική γραμμή που αυτά ορίζουν. Αν τα σημεία είναι αρκετά πυκνά τότε αυτή η πολυγωνική γραμμή προσεγγίζει πάρα πολύ καλά (για το μάτι τουλάχιστον) την πραγματική καμπύλη $y=f(x)$.

Αν το διάστημά μας είναι το $[a,b]$ και $N$ είναι ένας μεγάλος ακέραιος τότε αν $h=(b-a)/N$ παίρνουμε από ένα $x_i$ κάθε μήκος $h$, παίρνοντας έτσι τα $N+1$ σημεία $x_0 = a, x_1 = a+h, x_2 = a+2h, \ldots, x_{N-1} = a+(N-1)h, x_N = b$

Τη λίστα αυτή των $x$ τη φτιάχνουμε με το list comprehension

x = [a+i*h for i in range(N+1)]

ενώ την αντίστοιχη λίστα των $y$ με το list comprehension

y = [f(t) for t in x]

Το επιπλέον όρισμα r στην plot σημαίνει να ζωγραφιστεί η γραμμή με κόκκινο (red).

In [31]:

import matplotlib.pyplot as plt
import math

def f(x): # Η συνάρτηση της οποίας το γράφημα ζωγραφίζουμε
    return math.cos(x)*x

a = -10.
b = 10.
N = 100
h = (b-a)/N

x = [a+i*h for i in range(N+1)]
y = [f(t) for t in x]

plt.plot(x, y, 'r')

plt.show()

Παρακάτω ζωγραφίζουμε δύο γραφήματα, ένα για τη συνάρτηση f κι ένα για τη συνάρτηση g που είναι ορισμένες, και πάνω στο ίδιο διάστημα, το ένα με μπλέ ('b') και το άλλο με κόκκινο ('r').

In [54]:

import matplotlib.pyplot as plt
import math

def f(x):
    return math.cos(x)*x
def g(x):
    return math.sin(x)

a = -10.
b = 10.
N = 100
h = (b-a)/N

x = [a+i*h for i in range(N+1)]
y1 = [f(t) for t in x]
y2 = [g(t) for t in x]

plt.plot(x, y1, 'r')
plt.plot(x, y2, 'b')

plt.show()

Εδώ δείχνουμε πώς να ζωγραφίσουμε ένα τρτράγωνο δίνοντας τις κατάλληλες λίστες συντεταγμένων στην plot.

Πρέπει επίσης να χρησιμοποιήσουμε τη συνάρτηση plt.axes().set_aspect('equal') ώστε οι μονάδες στους δύο άξονες να αντιστοιχούν στο ίδιο φυσικό μήκος πάνω στην οθόνη μας. Αλλιώς το τετράγωνο θα βγεί ορθογώνιο (δοκιμάστε το).

In [36]:

import matplotlib.pyplot as plt

plt.plot([0, 1, 1, 0, 0], [0, 0, 1, 1, 0])
plt.axis([-0.5, 1.5, -0.5, 1.5])
plt.axes().set_aspect('equal')
plt.show()

Εδώ φτιάχνουμε μια συνάρτηση plot_polygon που ζωγραφίζει ένα κλειστό πολύγωνο στην οθόνη μας, που περιγράφεται από τα σημεία στη λίστα L (μια λίστα ζευγών, από λίστες δηλ. μήκους 2). Η συνάρτηση αυτή διαβάζει από τη λίστα L τις αντίστοιχες λίστες x και y και τις περνάει στην plot αφού πρώτα προσθέσει μια ακόμη φορά, στο τέλος, τις συντεταγμένες του πρώτου σημείου της καμπύλης (αλλιώς δε θα κλείσει η γραμμή).

Η συνάρτηση plot_polygon υπολογίζει επίσης (κοιτώντας τις ελάχιστες και μέγιστες τιμές των x και y που εμφανίζονται) το ποιο πρέπει να είναι το παράθυρο του επιπέδου που πρέπει να χρησιμοποιήσουμε. Το παίρνει να είναι κατά 10% μεγαλύτερο από το ελάχιστο παράθυρο από κάθε πλευρά.

In [55]:

import matplotlib.pyplot as plt

def plot_polygon(L):
    """
    L είναι μια λίστα ζευγών (λίστες μήκους δύο, [x, y]) και ζωγραφίζουμε
    το πολύγωνο που ορίζουν οι κορυφές αυτές.
    """
    x = [pair[0] for pair in L] + [ L[0][0] ] # Οι λίστες που περνάμε στην plot
    y = [pair[1] for pair in L] + [ L[0][1] ]
    
    minx = min(x)
    maxx = max(x)
    miny = min(y)
    maxy = max(y) # Μέγιστες και ελάχιστες τιμές των x, y
    wx = maxx-minx # Πλάτος σχεδίου στη x κατεύθυνση
    wy = maxy-miny # Πλάτος σχεδίου στη y κατεύθυνση
    minx -= 0.1*wx
    maxx += 0.1*wx
    miny -= 0.1*wy
    maxy += 0.1*wy # Αυξάνουμε το παράθυρο κατά 10% από κάθε μεριά.
    plt.plot(x, y)
    plt.axis([minx, maxx, miny, maxy])
    plt.show()
    
plot_polygon([ [0, 0], [0, 2], [1, 2], [1, .5], [2, .5], [2, 2], [3, 2], [3, 0] ])

Πώς θα ζωγραφίσουμε ένα κύκλο, π.χ. τον κύκλο με κέντρο το 0 και ακτίνα 1;

Πολύ απλά ζωγραφίζοντας μια πολύ πυκνή πολυγωνική γραμμή με τις κορυφές της πάνω στην καμπύλη. Παρακάτω ζωγραφίζουμε ένα κανονικό 200-γωνο, χρησιμοποιώντας τη συνάρτηση plot_polygon που φτιάξαμε προηγουμένως.

Για να βρούμε τις κορυφές του κανονικού 200-γώνου χρησιμοποιούμε την παραμέτριση του κύκλου $x(\theta) = \cos\theta,\ \ y(\theta) = \sin\theta$, με $0 \le \theta \le 2\pi$.

Φτιάχνουμε πρώτα 201 τιμές του $\theta$ ισοκατανεμημένες στο διάστημα $[0,2\pi]$ και από τη λίστα των $\theta$ φτιάχνουμε, χρησιμοποιώντας τους παραπάνω τύπους, τη λίστα των x και τη λίστα των y.