👀 Voorbeeld – Random Sort is heel traag

Onderstaande code toont aan hoe traag Random Sort is. Hoe langer het duurt voor de uitvoer verschijnt, hoe langer het algoritme bezig is. Na een tijdje meldt de computer dat de uitvoering te lang duurt — dan mag je stoppen.

Zelfs een lijst met maar 6 elementen ([60, 50, 40, 30, 20, 10]) sorteren duurt een tiental seconden!

💻 Programmeeroefening – Heel inefficiënt sorteren

Schrijf een functie random_sort(rij) die de gegeven lijst rij van klein naar groot sorteert door gebruik te maken van het Random Sort algoritme.

---

In deze oefening kan je gebruikmaken van de volgende functies:

• is_gesorteerd(rij): geeft True als de lijst oplopend gesorteerd is
• wissel(rij, index1, index2): wisselt de elementen op index1 en index2 in de lijst rij van plaats
• willekeurige_indexen(rij): geeft een tupel met 2 willekeurige indexen van de lijst rij terug

Kopieer en plak deze functies in de editor hieronder, boven de functie random_sort(rij)

import random

def is_gesorteerd(rij):
    # Ga elk element vergelijken met het volgende
    for i in range(len(rij) - 1):
        if rij[i] > rij[i + 1]:
            return False
    return True

def wissel(rij, index1, index2):
    # Wissel de twee elementen van plaats
    tijdelijk = rij[index1]
    rij[index1] = rij[index2]
    rij[index2] = tijdelijk


def willekeurige_indexen(rij):
    # Kies twee willekeurige indexen
    i1 = random.randint(0, len(rij) - 1)
    i2 = random.randint(0, len(rij) - 1)
    return (i1, i2)