sort_search.py

# https://www.interviewbit.com/tutorial/quicksort-algorithm
def binary_search(A, target, start, end):
    while(start<=end):
        m = (start+end)//2
        if(A[m]==target):
            return True
        elif (A[m] < target):
            start = m+1
        else:
            end = m-1
    return False
    
def binary_search_recursive(A, target, start, end):
    if(start<=end):
        m = (start+end)//2
        if(A[m] == target):
            return True
        elif (A[m] < target):
            return binary_search_recursive(A,target,m+1,end)
        else:
            return binary_search_recursive(A,target,start,m-1)
    return False
    
lst = [1, 3, 4, 6, 8, 9, 17]
print(binary_search_recursive(lst, 4, 0, len(lst)-1))
    
def swap(A,i,j):
    A[i], A[j] = A[j], A[i]
    
def bubblesort(A):
    n = len(A)
    for i in range(len(A)):
        for j in range(n-i-1):
            if A[j]>A[j+1]:
                swap(A,j,j+1)


def selectionsort(A):
    n = len(A)
    for i in range(n-1):
        m = min(A[i+1:])
        if m < A[i]:
            swap(A,i,A.index(m))


def insertionsort(A):
    n = len(A)
    for i in range(1,n):
        comp = i-1
        while(comp>=0 and A[comp]>A[i]):
            swap(A,i,comp)
            comp-=1
            i-=1
            
def shellsort(A):
    n = len(A)
    gap = n//2
    
    while gap>0:
        for i in range(gap,n):
            tmp = A[i]
            j = i
            
            while j>=gap and A[j-gap] > tmp:
                A[j] = A[j-gap]
                j-=gap
                
            A[j] = tmp 
        
        gap//=2

# left = 0, right = 6
def mergesort(self,A,left,right):
    if left < right:
        middle = (left+right)//2
        self.mergesort(A,left,middle)
        self.mergesort(A,middle+1,right)
        self.merge(A,left,middle,right)

def merge(self,A,left,mid,right):
    tmp = []

    i,j = left,mid+1
    while i<=mid and j<=right:
        if A[i] < A[j]:
            tmp.append(A[i])
            i+=1
        else:
            tmp.append(A[j])
            j+=1

    while i<=mid:
        tmp.append(A[i])
        i+=1
    while j<=right:
        tmp.append(A[j])
        j+=1

    for i in range(left,right+1):
        A[i] = tmp[i-left]

def quicksort(self,A,start,end):
    if start<end:
        part = self.partition(A,start,end)
        self.quicksort(A,start,part-1)
        self.quicksort(A,part+1,end)

def partition(self,A,start,end):
    pivot = A[end]
    i = (start-1)

    for j in range(start,end):
        if A[j] < pivot:
            i+=1
            A[i],A[j] = A[j],A[i]

    A[i+1],A[end] = A[end],A[i+1]
    return i+1 # return new pivot