Είδαμε, καθ' οδόν προς την περιγραφή του quicksort, τη μέθοδο ταξινόμησης mergesort. Αυτή δουλεύει ως εξής: όταν είναι να ταξινομήσει μια λίστα μεγέθους $n$ τη μοιράζει σε δύο ισομεγέθεις λίστες (σχεδόν, αν το $n$ είναι περιττός) τις οποίες ταξινομεί καλώντας τον εαυτό της αναδρομικά και μετά συγχωνεύει τις δύο ταξινομημένες μισές λίστες σε μία παίρνοντας κάθε φορά το μικρότερο (αν υποθέσουμε ότι ταξινομούμε σε αύξουσα σειρά) από τα δύο πρώτα στοιχεία των μισών λιστών.
Το υλοποιήσαμε αυτό στην παρακάτω συνάρτηση msort.
def msort(a): # ταξινομεί τη λίστα αριθμών a σε αύξουσα σειρά
if len(a)==1:
#print("Επιστροφή λόγω μήκους 1")
return
if len(a)==2:
x=min(a[0], a[1])
y=max(a[0], a[1])
a[0] = x
a[1] = y
#print("Επιστροφή λόγω μήκους 2")
return
n = len(a)
k = n//2
L = a[0:k] # η αριστερή μισή λίστα
R = a[k:] # η δεξιά μισή λίστα
#print(f"Χωρίζω σε L={L} και R={R}")
msort(L) # ταξινομούμε αναδρομικά τις L και R
msort(R)
# Τα l1, r1 δείχνουν τα πρώτα (μικρότερα) μη χρησιμοποιημένα στοιχεία των L, R
l1 = r1 = 0
for i in range(n):
if l1>=len(L): # Έχει τελειώσει η λίστα L
a[i:] = R[r1:]
break
if r1>=len(R): # Έχει τελειώσεη η λίστα R
a[i:] = L[l1:]
break
if L[l1] <= R[r1]: # παίρνουμε το μικρότερο από τα δύο πρώτα στοιχεία και το βάζουμε στην a
a[i] = L[l1]
l1 += 1
else:
a[i] = R[r1]
r1 += 1
# Δοκιμάζουμε τη συνάρτηση
x = [1, 2, 3, 5, 5, -2, 4, 3, 2, 1, -1, 0, 0, 2, 3, 4]
msort(x)
print(x)
Έπειτα περιγράψαμε τη μέθοδο quicksort. Δείτε την ανάλυση για το μέσο χρόνο εκτέλεσης εδώ, σελ. 63-66.
Ακολουθεί μια υλοποίηση σε python. Στην πρώτη υλοποίηση (συνάρτηση qsort) επιλέγουμε πάντα ως pivot (διαχωριστικό στοιχείο) το πρώτο στοιχείο της λίστας.
Στη δεύτερη υλοποίηση (συνάρτηση qsortr) επιλέγουμε τυχαία ένα στοιχείο της λίστας ως pivot (αυτή είναι η συνάρτηση που χρησιμοποιείται στην πράξη και αυτή αφορά η ανάλυση που είδαμε).
def qsort(a): # Ταξινομούμε τη λίστα a με τη μέθοδο quicksort (με το πρώτο στοιχείο πάντα ως διαχωριστικό)
# Η συνάρτηση επιστρέφει τον αριθμό των συγκρίσεων που κάνει κάθε φορά (μέτρο του χρόνου που παίρνει)
if len(a)<=1:
#print("Επιστροφή λόγω μήκους 1")
return 0
if len(a)==2:
x=min(a[0], a[1])
y=max(a[0], a[1])
a[0] = x
a[1] = y
#print("Επιστροφή λόγω μήκους 2")
return 1
n = len(a)
x = a[0] # pivot
L = [] ; R = []
for i in range(1,n): # χωρίζουμε στις λίστες L (στοιχεία μικρότερα του x) και R (τα υπόλοιπα)
if a[i] < x:
L.append(a[i])
else:
R.append(a[i])
nl = qsort(L) # ταξινομούμε αναδρομικά τις δύο λίστες L, R
nr = qsort(R)
a[:len(L)] = L # Συγκολλούμε στη λίστα a τις λίστες L και R με το στοιχείο x ανάμεσά τους
a[len(L)] = x
a[len(L)+1:] = R
return nl+nr+n-1
# Δοκιμές της συνάρτησης
data = [1, 2, 1, -1, 0, 2, 3, 5, 5, -2, 4, 3, 0, 2, 3, 4]
data = data+data
n = qsort(data)
print(n, data)
data1 = data[::-1]
n = qsort(data1)
print(n, data1)
import numpy as np
def qsortr(a): # Ταξινομούμε τη λίστα a με τη μέθοδο quicksort (με ένα τυχαίο στοιχείο ως διαχωριστικό)
# Η συνάρτηση επιστρέφει τον αριθμό των συγκρίσεων που κάνει κάθε φορά (μέτρο του χρόνου που παίρνει)
if len(a)<=1:
#print("Επιστροφή λόγω μήκους 1")
return 0
if len(a)==2:
x=min(a[0], a[1])
y=max(a[0], a[1])
a[0] = x
a[1] = y
#print("Επιστροφή λόγω μήκους 2")
return 1
n = len(a)
r = np.random.randint(n)
x = a[r] # pivot
L = [] ; R = []
for i in range(n): # χωρίζουμε στις λίστες L (στοιχεία μικρότερα του x) και R (τα υπόλοιπα)
if i == r: continue
if a[i] < x:
L.append(a[i])
else:
R.append(a[i])
nl = qsortr(L)
nr = qsortr(R)
a[:len(L)] = L # Συγκολλούμε στη λίστα a τις λίστες L και R με το στοιχείο x ανάμεσά τους
a[len(L)] = x
a[len(L)+1:] = R
return nl+nr+n-1
# Δοκιμές της συνάρτησης
data = [1, 2, 1, -1, 0, 2, 3, 5, 5, -2, 4, 3, 0, 2, 3, 4]
data = data+data
n = qsortr(data)
print(n, data)
data1 = data[::-1]
n = qsortr(data1)
print(n, data1)