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]