Les 3: Sorteer Algoritmes

Bubble Sort

Sorteert een rij van elementen door herhaaldelijk door de rij te lopen, opeenvolgende elementen met elkaar te vergelijken, en deze van plek te verwisselen indien de volgorde incorrect is.

Python code:

def bubbleSort(arr): 
    n = len(arr) 
  
    # Traverse through all array elements 
    for i in range(n-1): 
    # range(n) also work but outer loop will repeat one time more than needed. 
  
        # Last i elements are already in place 
        for j in range(0, n-i-1): 
  
            # traverse the array from 0 to n-i-1 
            # Swap if the element found is greater 
            # than the next element 
            if arr[j] > arr[j+1] : 
                arr[j], arr[j+1] = arr[j+1], arr[j] 
  
# Driver code to test above 
arr = [64, 34, 25, 12, 22, 11, 90] 
  
bubbleSort(arr) 
  
print ("Sorted array is:") 
for i in range(len(arr)): 
    print ("%d" %arr[i]),   

Recurssie:

Als je een bepaalde actie herhaaldelijk moet laten uitvoeren wordt vaak gebruik gemaakt van loops (for loops of while loops). Een andere aanpak is Recursie.

Stel je ziet een reclame op TV. En in die reclame zie je iemand naar TV kijken. Op de TV in de reclamespot zie je weer iemand naar TV kijken. Het herhaaldelijk iemand naar een TV kijken wordt ook wel recursie genoemd. Een ander voorbeeld van recursie zie je ook bij de cacaobus van Droste, waarop een verpleegster te zien is, die op een dienblad een cacaobus heeft, waarop een verpleegster te zien is, die .... etc..Dit noemt men soms ook het Droste effect.

Merge sort [vwo]

Divide and conquer algoritme Divide: Verdeel het probleem in subproblemen van hetzelfde type. Conquer: Los de subproblemen op bijv. met behulp van recursie. Combine: Combineer de antwoorden van de subproblemen.

# Python program for implementation of MergeSort 
  
# Merges two subarrays of arr[]. 
# First subarray is arr[l..m] 
# Second subarray is arr[m+1..r] 
def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
    # create temp arrays 
    L = [0] * (n1) 
    R = [0] * (n2) 
  
    # Copy data to temp arrays L[] and R[] 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
  
    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 
  
    # Merge the temp arrays back into arr[l..r] 
    i = 0     # Initial index of first subarray 
    j = 0     # Initial index of second subarray 
    k = l     # Initial index of merged subarray 
  
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    # Copy the remaining elements of L[], if there 
    # are any 
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    # Copy the remaining elements of R[], if there 
    # are any 
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
# l is for left index and r is right index of the 
# sub-array of arr to be sorted 
def mergeSort(arr,l,r): 
    if l < r: 
  
        # Same as (l+r)//2, but avoids overflow for 
        # large l and h 
        m = (l+(r-1))//2
  
        # Sort first and second halves 
        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 
  
  
# Driver code to test above 
arr = [12, 11, 13, 5, 6, 7] 
n = len(arr) 
print ("Given array is") 
for i in range(n): 
    print ("%d" %arr[i]), 
  
mergeSort(arr,0,n-1) 
print ("\n\nSorted array is") 
for i in range(n): 
    print ("%d" %arr[i]), 
  
# This code is contributed by Mohit Kumra 

Opdrachten

Probeer deze sorteer algortimes op papier stap voor stap uit te schrijven. [kan een vraag op de toets zijn]