Quartz 5

Searching and Sorting Algorithms Complete

7 min read

Searching and Sorting Algorithms Complete

Searching and Sorting Algorithms

Searching Algorithms:

  1. Linear / Sequential Search
  2. Binary Search
  3. Hash Table Search

Sorting Algorithms:

  1. Bubble Sort
  2. Insertion Sort
  3. Merge Sort
  4. QuickSort
numberList = [6, 172, 331, 363, 497, 525, 552, 611, 723, 949]
key = 611
fake = 412

Linear Search

def linearSearch(numberList, key):
    start = 0
    end = len(numberList) - 1
    for i in numberList:
        if start == end:
            print('Not Found')
        elif i == key:
            print("Found")
            return(i)
        else:
            start += 1
 
linearSearch(numberList, key)
linearSearch(numberList, fake)

Output:

Found
Not Found

Binary Search

Binary Search operates on the basis that the list is already sorted, and it essentially guesses higher lower until it can get the correct value if not it quits

Iterative Version

def binarySearch(numberList, key):
    max = len(numberList) -1
    min = 0
    
    while min <= max:
        mid = (min + max) // 2
        if key == numberList[mid]:
            print('found')
            break
        elif key < numberList[mid]:
            max = mid -1
        else:
            min = mid + 1
    else:
        print('not found')

Recursive Version

def binarySearchRecursive(numberList, key):
    return binarySearchRecursive2(numberList, key, 0, len(numberList) -1)
 
def binarySearchRecursive2(numberList, key, min, max):
    mid = (min + max) // 2
    if numberList[mid] == key:
        return 'Found'
    elif min > max:
        return 'Not Found'
    else:
        if numberList[mid] < key: # when guess is too low
            min = mid + 1
        else: #numberList[mid] > key, guess is too high
            max = mid - 1
        return binarySearchRecursive2(numberList, key, min, max)
    
print(binarySearchRecursive(numberList, key))
print(binarySearchRecursive(numberList, fake))

Output:

Found
Not Found

The location of each item is determined by a hash function of the item itself. This makes hash table search at the designated location of the item and thus less comparisons.

There are two main collision strategies - linear probing, as well as chaining

def hashValue(value,hashNum):
    return value%hashNum

Hash Table with Linear Probing

When items have the same hash, the later item is simply just shifted to the next available index.

def hashTableLinearProbe(numberList):
    hashList = [0 for i in numberList]
    for number in numberList:
        value = hashValue(number, len(numberList))
        if hashList[value] == 0:
            hashList[value] = number
        else:
            while hashList[value] != 0:
                value += 1
                if value == len(numberList):
                    value = 0
            hashList[value] = number  
    return(hashList)
            
print(numberList)
print([hashValue(i,len(numberList)) for i in numberList])
hashTableLinearProbe(numberList)

Output:

[6, 172, 331, 363, 497, 525, 552, 611, 723, 949]
[6, 2, 1, 3, 7, 5, 2, 1, 3, 9]

Output:

[949, 331, 172, 363, 552, 525, 6, 497, 611, 723]

Hash Table with Chaining

Instead of using probing, just have a list of all the values that correspond to each hash

def hashTableChaining(numberList):
    hashList = [['Null'] for i in numberList]
    for number in numberList:
        value = hashValue(number, len(numberList))
        hashList[value] = [number] + hashList[value]
    
    return(hashList)
    
hashTableChaining(numberList)

Output:

[['Null'],
 [611, 331, 'Null'],
 [552, 172, 'Null'],
 [723, 363, 'Null'],
 ['Null'],
 [525, 'Null'],
 [6, 'Null'],
 [497, 'Null'],
 ['Null'],
 [949, 'Null']]

Sorting Algorithms

Bubble Sort

Bubble sort works by swapping one item at a time. It compares an item with the next item, and swaps the position of items when the one on the left is higher than that on the right. If the two items in comparison are already sorted, it chooses the higher item and uses that to sort instead. (You can see that with how it sorts the 12, 15, 20)

This ensures that with each round, the far right is has increased number of sorted items. (i.e 1st round, highest item would be on far right, 2nd round, the two highest items would be on the right)

unsorted = [45,12,4,15,20,3]
unsortedLong = [45,12,4,15,20,3,39,5,9,30]
 
def bubbleSort(unsorted):
    lastSorted = len(unsorted) - 1
    while lastSorted > 0:
        lastExchangeIndex = 0 # Take note: the last exchange index is of each round. Last sorted is the things that are already done
        for i in range(lastSorted):
            if unsorted[i] > unsorted[i+1]:
                unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i]
                lastExchangeIndex = i 
            lastSorted = lastExchangeIndex
    return unsorted        
                
bubbleSort(unsorted)

Output:

[3, 4, 12, 15, 20, 45]

FUNCTION BUBBLESORT RETURNS ARRAY
LASTSORTED <- LENTH(ARRAY) -1
WHILE LASTSORTED > 0 DO
LASTEXCHANGE <- 0
FOR i 0 TO LASTSORTED DO
IF ARRAY[i] > ARRAY[i+1]
temp <- ARRAY[i+1]
ARRAY[i+1] <- ARRAY[i]
ARRAY[i] <- temp
LASTEXCHANGE <- i
ENDIF
ENDFOR
LASTSORTED <- LASTEXCHANGE
ENDWHILE
ENDFUNCTION

Insertion Sort

Essentially, everything on the left is sorted. The next item on the right that is unsorted (seen as the red numbers that are brought down) is compared with sorted elements on the left individually, from highest to lowest. This continues until a suitable slot is found to put the item in.

unsorted = [45,12,4,15,20,3]
unsortedLong = [45,12,4,15,20,3,39,5,9,30]
 
def insertionSort(unsorted):
    for index in range(len(unsorted)): # this gets one element at a time, starting with second element
        swapItem = unsorted[index] # holds the item to be swapped separately (visualised as shifting down above)
        comparison = index # defines where the comparison starts, it goes downwards from here.
        while comparison > 0 and swapItem < unsorted[comparison-1]: # i keep forgetting the -1 here
            unsorted[comparison] = unsorted[comparison -1] # visualised as green shifting to the right
            comparison -= 1 # visualised as the empty space shifting
        unsorted[comparison] = swapItem # visualised as the holding data being put back into main array
        
    return unsorted
    
insertionSort(unsortedLong)

Output:

[3, 4, 5, 9, 12, 15, 20, 30, 39, 45]
# i actually prefer this version, where i just swap each data but idk if its allowed ? 
# does not really look the same as animation ..
 
def linearSort(unsorted):
    for i in range(len(unsorted)):
        comparison = i
        swapItem = unsorted[i]
        while comparison > 0 and swapItem < unsorted[comparison -1]:
            unsorted[comparison], unsorted[comparison-1] = unsorted[comparison-1], unsorted[comparison]
            comparison -= 1
    return unsorted
 
 
linearSort(unsorted)

Output:

[3, 4, 12, 15, 20, 45]

MergeSort

Merge sort essentially continues splitting the original array into arrays until they form arrays of size 2. In the example below, 10 items are split into 5/5 then 3/2 each.

When the subarray is of size 3 - this gets further split into 1, and 2. Take note that this differs from the visualisation below. In the vis, the single item (4) is compared with the first pair (45, 12). In the code below, it is compared with the second pair (15, 20).

After the splitting, comparison occurs, in such order:

  1. Within the 2 element subarray
  2. Within the 3 element subarray
  3. Between the 2 and 3 element subarray, forming a 5 element sorted subarray
  4. Between the two 5 element subarray, which after comparison forms the full sorted array.
unsorted = [45,12,4,15,20,3]
unsortedLong = [45,12,4,15,20,3,39,5,9,30]
 
def mergeSort(Array):
    if len(Array) > 1: # remember that it is >1, because the minimum length size is 2 in order to do swapping.
        # recursive splitting into small groups. the if statement above is important.
        mid = len(Array) // 2
        left = mergeSort(Array[:mid])
        right = mergeSort(Array[mid:])
        
       # here is the comparison
        Array = []
        while len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                Array.append(left.pop(0))
            else:
                Array.append(right.pop(0))
        
        # this is in the case where either left or right is empty already, 
        # since the other side is sorted and more than Array, we can just dump it as such.
        Array += left + right
    return Array
 
mergeSort(unsortedLong)

Output:

[3, 4, 5, 9, 12, 15, 20, 30, 39, 45]

QuickSort

# unsorted = [45,12,4,15,20,3]
unsorted = [45,12,4,15,20,3,39,5,9,30]
 
def split(Array, low, high):
    middle = (low + high) // 2
    pivot = Array[middle]
    
    left = low + 1
    right = high
    
    # swapping to set the pivot on the left
    Array[low], Array[middle] = Array[middle], Array[low] 
    
    while left <= right:
        # because i want left to be more than right, and i
        # want  the left pointer to be <= right pointer
        while  left <= right and Array[left] <= pivot: # the <= IS CRUCIALL
            left += 1    
        while Array[right] > pivot: # bc i want the right to be a value < pivot
            right -= 1
        if left < right:
            Array[left], Array[right] = Array[right], Array[left]
    
    Array[low], Array[right] = Array[right], Array[low] # the swap back
    
    return right
 
def quickSort(Array, low, high):
    if low < high: # i keep forgetting this
        pivot = split(Array, low, high)
        quickSort(Array, low, pivot -1)
        quickSort(Array, pivot + 1, high)
        # notice how pivot is not included, because it is 'locked in'
        
quickSort(unsorted, 0, len(unsorted) -1)
print(unsorted)

Output:

[3, 4, 5, 9, 12, 15, 20, 30, 39, 45]

Graph View