Quick Sort + Binary Search

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.

DynamicArray=[]
#
#...Fill DynamicArray...
#
DynamicArray.sort()

I know it’s very simple. But It’s working really fast.

Another quick sort :

In the first step we need to partitioning :

def partitioning(UnSortedArray, StartFrom, EndTo):
    pivot_point = UnSortedArray[StartFrom]
    low_id = StartFrom + 1
    high_id = EndTo
    while True:
        while low_id <= high_id and UnSortedArray[high_id] >= pivot_point:
            high_id = high_id - 1
        while low_id <= high_id and UnSortedArray[low_id] <= pivot_point:
            low_id = low_id + 1
        if low_id <= high_id:
            UnSortedArray[low_id], UnSortedArray[high_id] = UnSortedArray[high_id], UnSortedArray[low_id]
        else:
            break
    UnSortedArray[StartFrom], UnSortedArray[high_id] = UnSortedArray[high_id], UnSortedArray[StartFrom]
    return high_id

def QuickSort(Unsorted_Array, start_from, end_to):
    if start_from >= end_to:
        return
    partitionA = partitioning(Unsorted_Array, start_from, end_to)
    QuickSort(Unsorted_Array, start_from, partitionA-1)
    QuickSort(Unsorted_Array, partitionA+1, end_to)


# TEST :
unsorted=[234,234,2343,42,4,565,13,76,133,899,343,8,45,23,2]
QuickSort(unsorted,0,len(unsorted)-1)
print(unsorted)

Binary Search (Recursive) :

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Very important : Sort the array before Binary Search

def Binary_Search(Sorted_Array, StrToFind):
    StartFrom = 0
    EndTo = len(Sorted_Array) - 1
    while StartFrom <= EndTo:
        MiddleID = (StartFrom + EndTo) // 2
        MiddlePoint = Sorted_Array[MiddleID]
        if MiddlePoint > StrToFind:
            EndTo = MiddleID - 1
        elif MiddlePoint < StrToFind:
            StartFrom = MiddleID + 1
        else:
            return MiddlePoint

#Test 1 :
Sorted=[2, 4, 8, 13, 23, 42, 45, 76, 133, 234, 234, 343, 565, 899, 2343]
FindResult=Binary_Search(Sorted,76)
print("Test 1",FindResult)

#Test 2 :
FindResult=Binary_Search(Sorted,77)
print("Test 2",FindResult)

#Test 3 :
Sorted=['Arnold','Bamboo','Honda','Suzuki','Tornado','Underwater','Zebra']
FindResult=Binary_Search(Sorted,'Honda')
print("Test 3",FindResult)

#Test 4 :
FindResult=Binary_Search(Sorted,'Sepandar')
print("Test 4",FindResult)

Problems and issue:

Sometimes you have many items in the array. So the Python may raise error in Quick Sort or Binary Search recursive procedure during run :

for example test this bad program :

# BAD TEST :
unsorted=[ai for ai in range(99999)]
QuickSort(unsorted,0,len(unsorted)-1)
print(unsorted)

1. RecursionError: maximum recursion depth exceeded in comparison

Solution :

First it’s better to know when you execute a recursive function in Python on a large input ( > 10^4), you might encounter a “maximum recursion depth exceeded error”.

The sys module in Python have a function getrecursionlimit() can show the recursion limit in your Python version.

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

The default in some version of Python is 1000 and in some other it was 1500

You can change this limitation but it’s very important to know if you increase it very much you will have memory overflow error.

So be careful before increase it. You can use setrecursionlimit() to increase this limitation in Python.

import sys
sys.setrecursionlimit(3000)