← RU Pythoncursus

Uitwerking: 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()