simple algorithms explanation (bubble sort, merge sort, quick sort and binary search)

algorithms.md

Sorting

Buble sort

• Compares two numbers and swaps them if the 2nd > 1st
• Keeps repeating the process (up to length - 1 each iteration)
• Simple but not a practical solution due to its heavy performance

def bubble_sort(dataset):
    # start with the array length and decrement each time
    for i in range(len(dataset)-1, 0, -1):
        for j in range(i):
            if (dataset[j] > dataset[j+1]):
                temp = dataset[j]
                dataset[j] = dataset[j+1]
                dataset[j+1] = temp

nums = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]
print('Before: ', nums)
bubble_sort(nums)
print('After:  ', nums)

Before:  [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]
After:   [6, 8, 19, 20, 23, 41, 49, 53, 56, 87]

Merge sort

• Divide and conquer as it breaks a dataset into peices.
• Merges/sorts the pieces into larger sets walking its way up (recursively) to the original dataset.
• Performs well on large sets of data.

[31, 12, 19, 6] break ⬇️

[31, 12], [19, 6] break ⬇️

[31], [12], [19], [6] merge/sort ⬇️

[12, 31], [6, 19] merge/sort ⬇️

[6, 12, 19, 31] 🎉

def mergesort(dataset):
    if len(dataset) > 1:
        mid = len(dataset) // 2
        leftArr = dataset[:mid]
        rightArr = dataset[mid:]

        # recursively break down the arrays
        mergesort(leftArr)
        mergesort(rightArr)

        # now perform the merging
        leftIdx=0 # index into the left array
        rightIdx=0 # index into the right array
        dsIdx=0 # index into merged array (dataset)

        # while both arrays have content
        while leftIdx < len(leftArr) and rightIdx < len(rightArr):
            if (leftArr[leftIdx] < rightArr[rightIdx]):
                dataset[dsIdx] = leftArr[leftIdx]
                leftIdx += 1
            else:
                dataset[dsIdx] = rightArr[rightIdx]
                rightIdx += 1
            dsIdx += 1

        # if the left array still has values, add them
        while (leftIdx < len(leftArr)):
            dataset[dsIdx] = leftArr[leftIdx]
            leftIdx += 1
            dsIdx += 1

        # if the right array still has values, add them
        while (rightIdx < len(rightArr)):
            dataset[dsIdx] = rightArr[rightIdx]
            rightIdx += 1
            dsIdx += 1

nums = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]
print('Before: ', nums)
mergesort(nums)
print('After:  ', nums)

Before:  [6, 20, 8, 19, 56, 23, 87, 41, 49, 53]
After:   [6, 8, 19, 20, 23, 41, 49, 53, 56, 87]

Quick Sort

• Like Merge Sort, Quick Sort also uses divide and conquer to break a dataset into peices then merges the pieces recursively into one sorted set.
• Not ideal for datasets that are already sorted.

[20, 6, 8, 53, 23, 87, 42, 19]

1. Pick the following points

   • pivot point (pp): 20
   • lowest idx (li): 1 (6)
   • highest idx (hi): 7 (19)

   CONDITION: lowest idx < highest idx

2. On left side, increment li until we reach a value > pp then we stop (at index 3 [20, 6, 8, 53, 23, 87, 42, 19])

3. On right side, decrement hi until we reach a value < pp then stop (at index 7: [20, 6, 8, 53, 23, 87, 42, 19])

4. Once both li and hi have reached a stop, their values are swapped (move 53 to index 7, and 19 to index 3)

   • Before [20, 6, 8, 53, 23, 87, 42, 19]
   • After [20, 6, 8, 19, 23, 87, 42, 53]

5. li keeps incrementing until it stops at index 4 because its value > pp [20, 6, 8, 19, 23, 87, 42, 53]

6. hi keeps decrementing until it stops at index 3 because:

   • The value at index 3 < pp and
   • hi has crossed li [20, 6, 8, 19hi, 23li, 87, 42, 53] which means the split point has been identified.

7. At this point:

   • pp and hi are swapped [19, 6, 8, 20, 23, 87, 42, 53]
   • The array is split on pp into two: [19,6,8] and [23, 87, 42, 53]
   • Quick sort is recursively applied to each until each array ends up having one item (no longer splittable)

def quickSort(dataset, firstIdx, lastIdx):
    if firstIdx < lastIdx:
        # calculate the split point
        pivotIdx = partition(dataset, firstIdx, lastIdx)
        # now sort the two partitions
        quickSort(dataset, firstIdx, pivotIdx-1)
        quickSort(dataset, pivotIdx+1, lastIdx)


def partition(datavalues, firstIdx, lastIdx):
    # choose the first item as the pivot value
    pivotvalue = datavalues[firstIdx]
    # establish the upper and lower indexes
    lowerIdx = firstIdx + 1
    upperIdx = lastIdx

    # start searching for the crossing point
    done = False
    while not done:
        # advance the lower index
        while lowerIdx <= upperIdx and datavalues[lowerIdx] <= pivotvalue:
            lowerIdx += 1

        # advance the upper index
        while datavalues[upperIdx] >= pivotvalue and upperIdx >= lowerIdx:
            upperIdx -= 1

        # if the two indexes cross, we have found the split point
        if upperIdx < lowerIdx:
            done = True
        else:
            # exchange the two values
            temp = datavalues[lowerIdx]
            datavalues[lowerIdx] = datavalues[upperIdx]
            datavalues[upperIdx] = temp

    # when the split point is found, exchange the pivot value
    temp = datavalues[firstIdx]
    datavalues[firstIdx] = datavalues[upperIdx]
    datavalues[upperIdx] = temp

    # return the split point index
    return upperIdx


items = [20, 6, 8, 53, 56, 23, 87, 41, 49, 19]

print('Before: ', items)
quickSort(items, 0, len(items)-1)
print('After:  ', items)

Before:  [20, 6, 8, 53, 56, 23, 87, 41, 49, 19]
After:   [6, 8, 19, 20, 23, 41, 49, 53, 56, 87]

Searching

Binary search

• Start with determining: lowest & highest indexes, and the mid point
• If mid-point === search-item return it
• Otherwise pick the half where the midpoint > search-item and repeat

def binary_search(item, arr):
    lowestIdx = 0
    highestIdx = len(arr) - 1

    while lowestIdx <= highestIdx:
        midPt = (lowestIdx + highestIdx) // 2
        if arr[midPt] == item:
            return midPt

        if item > arr[midPt]:
            lowestIdx = midPt + 1
        else:
            highestIdx = midPt - 1

    if lowestIdx > highestIdx:
        return None

items = [6, 8, 19, 20, 23, 41, 49, 53, 56, 87]
print('items: ', items)
print(binary_search(23, items))
print(binary_search(87, items))
print(binary_search(250, items))

items:  [6, 8, 19, 20, 23, 41, 49, 53, 56, 87]
4
9
None