Searching and Sorting Algorithms Practice

Searching Algos

numberList = [6, 172, 331, 363, 497, 525, 552, 611, 723, 949]
key = 611
fake = 412

Linear Search

def linearSearch(numberList, key):
    for i in range(len(numberList)):
        if numberList[i] == key:
            return f'Found, {i}'
    else:
        return 'Not Found'
    
print(linearSearch(numberList,  key))
print(linearSearch(numberList, fake))

Output:

Found, 7
Not Found

Binary Search

def binarySearch(numberList, key):
    low = 0
    high = len(numberList)-1
    
    while low < high:
        mid = (low+high)//2
        if numberList[mid] == key:
            return 'found'
        elif numberList[mid] > key:
            high = mid-1
        else:
            low = mid+1
    else:
        return 'not found'
    
    
print(binarySearch(numberList, key))
print(binarySearch(numberList, fake))

Output:

found
not found

def binarySearch(numberList, key):
    return binarySearchRecursive(numberList, key, 0, len(numberList)-1)
 
def binarySearchRecursive(numberList, key, low, high):
    if low > high:
        return 'Not Found'
    else:
        mid = (low + high) // 2
        if numberList[mid] == key:
            return 'Found'
        elif numberList[mid] > key:
            return binarySearchRecursive(numberList, key, low, mid-1)
        elif numberList[mid] < key:
            return binarySearchRecursive(numberList, key, mid+1, high)
        
        
print(binarySearch(numberList, key))
print(binarySearch(numberList, fake))

Output:

Found
Not Found

Hash Table Searching

def returnHash(key): # lets let this hash be hash of 11
    return (key % 11)
 
def hashTableChaining(numberList): 
    hashList = [['Null'] for i in numberList]
    for i in numberList:
        hashValue = returnHash(i)
        hashList[hashValue] = [i] + hashList[hashValue] 
 
def hashTableLinearProbing(numberList):
   
    return (hashList)
    
print(hashTableLinearProbing(numberList))

Sorting Algos

Bubble Sort

from random import randint
unsorted = [randint(0,1000) for i in range(10)]
print(unsorted)
 
def bubbleSort(Array):
    lastSorted = len(Array)-1
    while lastSorted >0:
        for i in range(lastSorted):
            lastExchange = 0
            if Array[i] > Array[i+1]:
                temp = Array[i+1]
                Array[i+1] = Array[i]
                Array[i] = temp
                lastExchange = i 
        lastSorted = lastExchange
    return Array
    
print(bubbleSort(unsorted))
sortedList = sorted(unsorted)
unsorted == sortedList

Output:

[212, 276, 142, 231, 138, 983, 42, 946, 884, 173]
[42, 138, 142, 173, 212, 231, 276, 884, 946, 983]

Output:

True

Insertion Sort

not too sure about this, need to practice this shit

from random import randint
unsorted = [randint(0,1000) for i in range(10)]
print(unsorted)
 
def insertionSort(unsorted):
    for i in range(len(unsorted)):
        comparison = i
        swapItem = unsorted[i]
        while comparison > 0 and unsorted[comparison-1] > swapItem:
            unsorted[comparison] = unsorted[comparison-1]
            comparison -=1
        unsorted[comparison] = swapItem
    return unsorted
 
    
print(insertionSort(unsorted))
sortedList = sorted(unsorted)
unsorted == sortedList

Output:

[136, 677, 526, 294, 852, 254, 152, 929, 370, 813]
[136, 152, 254, 294, 370, 526, 677, 813, 852, 929]

Output:

True

MergeSort

from random import randint
unsorted = [randint(0,1000) for i in range(10)]
print(unsorted)
 
def mergeSort(Array):
    if len(Array) > 1:
        mid = len(Array)//2
        left = mergeSort(Array[:mid])
        right = mergeSort(Array[mid:])
        
        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))
        Array += left + right
        
    return Array
    
print(mergeSort(unsorted))
sortedList = sorted(unsorted)
mergeSort(unsorted) == sortedList

Output:

[85, 911, 551, 970, 870, 609, 175, 448, 805, 195]
[85, 175, 195, 448, 551, 609, 805, 870, 911, 970]

Output:

True

QuickSort

from random import randint
unsorted = [randint(0,100) for i in range(10)]
print(unsorted)
 
def split(Array, low, high):
    mid = (low+high)//2
    pivot = Array[mid]
    
    Array[low], Array[mid] = Array[mid], Array[low]
    
    left = low+1
    right = high
    
    while left <= right:
        while left <= right and Array[left] <= pivot:
            left += 1
        while Array[right] > pivot:
            right -= 1
        if left < right:
            Array[left], Array[right] = Array[right], Array[left]
    
    Array[right], Array[low] = Array[low], Array[right]
    return right
 
def quickSort(Array, low, high):
    if low<high:
        pivot = split(Array, low, high)
        Array = quickSort(Array, low, pivot-1)
        Array = quickSort(Array, pivot+1, high)
    return Array
 
 
sortedList = quickSort(unsorted, 0, len(unsorted) -1)
print(sortedList)
sortedList = sorted(unsorted)
unsorted == sortedList

Output:

[5, 75, 59, 66, 5, 2, 22, 51, 16, 56]
[2, 5, 5, 16, 22, 51, 56, 59, 66, 75]

Output:

True