# 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.

{% embed url="<https://youtu.be/6Gv8vg0kcHc>" %}

#### Python code:

```python
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.

{% embed url="<https://www.youtube.com/watch?v=KEEKn7Me-ms&list=PLQbxgIKVVeTM1hG0CJDOHOBriqFJJPM20>" %}

## 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.

{% embed url="<https://youtu.be/KF2j-9iSf4Q>" %}

```python
# 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]


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://metis-montessori-lyceum.gitbook.io/informatica/modules/algortime/les-3-sorteer-algoritmes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.