Uitwerking: Inlever optie 1: Sorteren
import random
import time
import matplotlib.pyplot as plt
import numpy as np
def selectionSort(L):
for i in range(len(L)-1):
largest = L[i]
largestIndex = i
for j in range (i+1, len(L)):
if L[j] > largest:
largestIndex = j
largest = L[j]
L[i], L[largestIndex] = L[largestIndex], L[i]
return L
def bubbleSort(L):
for i in range(len(L), 0, -1):
for j in range(0, i-1):
if L[j] > L[j+1]:
L[j], L[j+1] = L[j+1], L[j]
return L
def mergeSort(L):
if len(L) > 1:
# long list: we have to split in into two lists, and sort those
half1 = L[:len(L)//2]
half1 = mergeSort(half1)
half2 = L[len(L)//2:]
half2 = mergeSort(half2)
# merge the sorted lists
result = mergeSortedLists(half1, half2)
return result
else:
return L
def mergeSortedLists(L1, L2):
i1, i2 = 0, 0
result = []
# while we haven't reached the end of one of the lists
while i1 < len(L1) and i2 < len(L2):
# from the current elements of both lists, pick the highest
# and continue to the next element in that list
if L1[i1] < L2[i2]:
result += [L1[i1]]
i1 += 1
else:
result += [L2[i2]]
i2 += 1
# at the end of one list: add all elements of the other lists
# that have not been processed yet
if i1 < len(L1):
result += L1[i1:]
else:
result += L2[i2:]
return result
i = 100
xrange = []
times = [[],[],[]]
for _ in range(5):
xrange += [i]
i = i*2
randoms = []
for _ in range(0, i):
randoms += [random.randrange(0, 10000)]
lastTime = time.time()
mergeSort(randoms)
times[0] += [time.time() - lastTime]
lastTime = time.time()
bubbleSort(randoms)
times[1] += [time.time() - lastTime]
lastTime = time.time()
selectionSort(randoms)
times[2] += [time.time() - lastTime]
plt.plot(xrange, times[0], label="merge sort")
plt.plot(xrange, times[1], label="bubble sort")
plt.plot(xrange, times[2], label="selection sort")
plt.legend()
plt.show()
