Divide and conquer algorithms

divideAndConquerAlgorithms.py

import random

'''Course: https://www.coursera.org/learn/algorithmic-toolbox#about'''



def linearSearchRecursive(searchList, minIndex, maxIndex, key):
    '''not the fastest approach to return index of element in list'''

    if maxIndex < minIndex:
        return "NOT FOUND"

    if searchList[minIndex] == key:
        return minIndex

    return linearSearchRecursive(searchList, minIndex+1, maxIndex, key)




def linearSearchIterative(searchList, minIndex, maxIndex, key):
    '''not the fastest approach to return index of element in list'''

    for i in range(minIndex, maxIndex+1):
        if searchList[i] == key:
            return i

    return "NOT FOUND"




def binarySearchRecursive(searchList, minIndex, maxIndex, key):
    '''fast recursive approach to return index of element in list'''

    if maxIndex < minIndex:
        return "NOT FOUND"

    middleIndex = int(minIndex + ((maxIndex -minIndex)/2))

    if searchList[middleIndex] == key:
        return middleIndex
    elif key < searchList[middleIndex]:
        return binarySearchRecursive(searchList, minIndex, middleIndex-1, key)
    else:
        return binarySearchRecursive(searchList, middleIndex+1, maxIndex, key)




def binarySearchIterative(searchList, minIndex, maxIndex, key):
    '''fast iterative approach to return the index of element in list'''

    while (minIndex <= maxIndex):
        middleIndex = int(minIndex + ((maxIndex - minIndex) / 2))

        if searchList[middleIndex] == key:
            return middleIndex
        elif key < searchList[middleIndex]:
            maxIndex = middleIndex - 1
        else:
            minIndex = middleIndex + 1

    return "NOT FOUND"



def swapElements(listToSort, index1, index2):

    temp = listToSort[index1]
    listToSort[index1] = listToSort[index2]
    listToSort[index2] = temp




def selectionSort(listToSort):
    '''not the fastest approach to sort a list'''

    length = len(listToSort)

    for i in range(length):
        minIndex = i

        for j in range(i+1, length):
            if listToSort[j] < listToSort[minIndex]:
                minIndex = j

        swapElements(listToSort, i, minIndex)

    return listToSort



def merge(leftHalfList, rightHalfList):
    '''Used in the merge sort function below.
    Creates a sorted list by taking elements from leftHalfList and rightHalfList'''

    sortedList = []
    i = 0
    j = 0
    while( i < len(leftHalfList) and j < len(rightHalfList)):

        leftListElement = leftHalfList[i]
        rightListElement = rightHalfList[j]

        if leftListElement <= rightListElement:
            sortedList.append(leftListElement)
            i+=1
        else:
            sortedList.append(rightListElement)
            j+=1

    sortedList += leftHalfList[i:]
    sortedList += rightHalfList[j:]
    return sortedList




def mergeSort(listToSort):
    '''Fast recursive approach to sort a list'''

    length = len(listToSort)
    if length == 1:
        return listToSort

    middleIndex = int(length/2)

    leftHalfList = mergeSort(listToSort[ : middleIndex])
    rightHalfList = mergeSort(listToSort[middleIndex : ])

    sortedList = merge(leftHalfList, rightHalfList)

    return sortedList





def countSort(countListToSort, maxValue):
    '''non-comparison based sort. It is fast and can be used only when sorting a range of integers or
    sorting objects whose keys are integers'''

    countList = [0] * (maxValue+1)
    length = len(countListToSort)
    sortedList = [None]*length

    for i in range(length):
        countList[countListToSort[i]] += 1

    positionList = [0] * (maxValue+1)
    for j in range(1, maxValue+1):
        positionList[j] = positionList[j-1] + countList[j-1]

    for i in range(length):
        sortedList[positionList[countListToSort[i]]] = countListToSort[i]
        positionList[countListToSort[i]] += 1

    return sortedList





def partition(listToSort, minIndex, maxIndex):
    '''Used in quickSort function below.
    Sets pivot element to an index where all elements <= it are left side to it
    and all elements > it are right side to it.
    This index for the pivot element would remain same in the final sorted array'''

    pivotElement = listToSort[minIndex]
    index = minIndex

    for i in range(index+1, maxIndex+1):
        if listToSort[i] <= pivotElement:
            index+=1

            swapElements(listToSort, i, index)

    swapElements(listToSort, index, minIndex)

    return index




def quickSort(listToSort, minIndex, maxIndex):
    '''average case: fast, worst case is not fast. More efficient than mergeSort in practice'''

    if maxIndex < minIndex:
        return

    index = partition(listToSort, minIndex, maxIndex)

    quickSort(listToSort, minIndex, index-1)
    quickSort(listToSort, index+1, maxIndex)

    return listToSort





def randomizedQuickSort(listToSort, minIndex, maxIndex):
    '''average case: fast, worst case is not fast. Worst case doesnt occur often.
    Before call to partition(), find randomIndex and swap it with first element'''

    if maxIndex < minIndex:
        return

    randomIndex = random.randint(minIndex, maxIndex)
    swapElements(listToSort, randomIndex, minIndex)

    index = partition(listToSort, minIndex, maxIndex)

    randomizedQuickSort(listToSort, minIndex, index-1)
    randomizedQuickSort(listToSort, index+1, maxIndex)

    return listToSort




def partition3(listToSort, minIndex, maxIndex):
    '''Used in randomizedQuickSortForEqualElements function below.
    Sets pivot element to an index where all elements < it are left side to it,
    all elements > it are right side to it, and in the middle lies, all elements equal to the pivot element'''

    pivotElement = listToSort[minIndex]
    index = minIndex
    index2 = minIndex

    for i in range(index+1, maxIndex+1):
        if listToSort[i] < pivotElement:
            index+=1
            index2+=1
            swapElements(listToSort, i, index)
            swapElements(listToSort, i, index2)

        elif listToSort[i] == pivotElement:
            index2+=1
            swapElements(listToSort, i, index2)

    swapElements(listToSort, index, minIndex)
    return index, index2



def randomizedQuickSortForEqualElements(listToSort, minIndex, maxIndex):
    '''faster than quickSort/randomizedQuickSort when list have equal elements'''

    if maxIndex < minIndex:
        return

    randomIndex = random.randint(minIndex, maxIndex)
    swapElements(listToSort, randomIndex, minIndex)

    index, index2 = partition3(listToSort, minIndex, maxIndex)

    randomizedQuickSortForEqualElements(listToSort, minIndex, index-1)
    randomizedQuickSortForEqualElements(listToSort, index2+1, maxIndex)

    return listToSort




def quickSortTailRecursionElimination(listToSort, minIndex, maxIndex):
    '''quickSort used recursive approach.
    When a recursive call is made, information is stored in stack (regarding memory used).
    Average recursion depth was logarithmic.
    For the below implementation, worst case is logarithmic
    because recursive call is only made to the shorter list and while loop for longer list'''

    while minIndex < maxIndex:

        index = partition(listToSort, minIndex, maxIndex)

        if (index - minIndex) < (maxIndex - index):
            quickSortTailRecursionElimination(listToSort, minIndex, index-1)
            minIndex = index+1

        else:
            quickSortTailRecursionElimination(listToSort, index+1, maxIndex)
            maxIndex = index-1

    return listToSort





def introSort(listToSort, minIndex, maxIndex):
    '''similar to randomizedQuickSort, but a heuristic is used instead of random.
    Heuristic: before call to partition();
    find the median of first, middle, and last element and swap it with first element'''

    if maxIndex < minIndex:
        return

    middleIndex = int(minIndex + ((maxIndex -minIndex)/2))

    if listToSort[minIndex] >= listToSort[middleIndex] and listToSort[minIndex] <= listToSort[maxIndex]:
        pass
    elif listToSort[middleIndex] >= listToSort[minIndex] and listToSort[middleIndex] <= listToSort[maxIndex]:
        swapElements(listToSort, middleIndex, minIndex)
    elif listToSort[maxIndex] >= listToSort[minIndex] and listToSort[maxIndex] <= listToSort[middleIndex]:
        swapElements(listToSort, maxIndex, minIndex)

    index = partition(listToSort, minIndex, maxIndex)

    introSort(listToSort, minIndex, index-1)
    introSort(listToSort, index+1, maxIndex)

    return listToSort





if __name__ == '__main__':

    print("\nIndex at which ab present (recursive linear search): ", linearSearchRecursive(['ab','ac','cd','ef'], 0, 3, 'ab'))
    print("Index at which ac present (iterative linear search): ", linearSearchIterative(['ab','ac','cd','ef'], 0, 3, 'ac'))

    print("\nIndex at which cd present (recursive binary search): ", binarySearchRecursive(['ab', 'ac', 'cd', 'ef'], 0, 3, 'cd'))
    print("Index at which ef present (iterative binary search): ", binarySearchIterative(['ab', 'ac', 'cd', 'ef'], 0, 3, 'ef'))

    print("\n(selection sort) Before: [3,5,1,2,6,5,4], After:", selectionSort([3,5,1,2,6,5,4]))
    print("(merge sort) Before: [3,5,1,2,6,5,4], After:", mergeSort([3,5,1,2,6,5,4]))

    print("\n(count sort) Before: [3,3,2,1,1,2,0,3,1,2], After:", countSort([3,3,2,1,1,2,0,3,1,2], 3))

    print("\n(quick sort) Before: [3,5,1,2,6,5,4], After:", quickSort([3,5,1,2,6,5,4], 0, 6))
    print("(randomized quick sort) Before: [3,5,1,2,6,5,4], After:", randomizedQuickSort([3,5,1,2,6,5,4], 0, 6))
    print("(randomized quick sort for equal elements) Before: [3,3,3,2,6,2,4], After:", randomizedQuickSortForEqualElements([3,3,3,2,6,2,4], 0, 6))

    print("\n(quick sort tail recursion elimination) Before: [3,5,1,2,6,5,4], After:", quickSortTailRecursionElimination([3,5,1,2,6,5,4], 0, 6))
    print("\n(intro sort) Before: [3,5,1,2,6,5,4], After:", introSort([3,5,1,2,6,5,4], 0, 6))