​      #  Selection Sort

​

def selectionsort(arr,n):
    for i in range(0,n):
        min_index=i
        for j in range(i+1,n):
            if arr[min_index]>arr[j]:
                min_index=j
        if min_index!=i:
            arr[i],arr[min_index] = arr[min_index],arr[i]
    

        #  Bubble Sort

def bubblesort(arr,n):
    for i in range(0,n-1):
        for j in range(0,n-i-1):
            if arr[j] >arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]

 

       # Insertion Sort

​

def insertionsort(arr,n):
    for i in range(1,n):
        temp=arr[i]
        j=i-1
        while j>=0 and temp<arr[j]:
            arr[j+1]=arr[j]
            j-=1
        arr[j+1]=temp
    

       # Quick Sort

def partition(low,high,arr):
    pivot=arr[high]
    i=low-1
    for j in range(low,high):
        if pivot>=arr[j]:
            i+=1
            arr[i],arr[j]=arr[j],arr[i]
    arr[i+1],arr[high]=arr[high],arr[i+1]
    return i+1

def quicksort(low,high,arr):
    if low<high:
        pivot = partition(low,high,arr)
        quicksort(low,pivot-1,arr)
        quicksort(pivot+1,high,arr)

 

      # Merge Sort

def merge(low,mid,high,arr):
    len1 = mid-low+1
    len2 = high-mid
    larr=[0]*len1
    rarr=[0]*len2
    
    for i in range(0,len1):
        larr[i]=arr[low+i]
    for j in range(0,len2):
        rarr[j]=arr[mid+j+1]
    
    i=0
    j=0
    k=low
    
    while i<len1 and j<len2:
        if larr[i]<=rarr[j]:
            arr[k]=larr[i]
            i+=1
            k+=1
        else:
            arr[k]=rarr[j]
            j+=1
            k+=1
    while i<len1:
        arr[k]=larr[i]
        i+=1
        k+=1
    while j<len2:
        arr[k]=rarr[j]
        j+=1
        k+=1
def mergesort(low,high,arr):
    if low<high:
        mid = low+(high-low)//2
        mergesort(low,mid,arr)
        mergesort(mid+1,high,arr)
        merge(low,mid,high,arr)
    

       # Binary Search

​

def binarysearch(arr,x):
    low=0
    high=len(arr)-1
    while low<=high:
        mid = high+low//2
        if arr[mid]==x:
            return mid
        elif arr[mid]>x:
            high = mid-1
        else:
            low = mid+1
    return -1
    
arr=[-5,8,0,4,3,2,1]
n=len(arr)

# selectionsort(arr,n)                      # Time Complexity:  O(n2)  |  Auxiliary Space: O(1)
# print('Selection sort ',arr)
# bubblesort(arr,n)                        # Time Complexity:  O(n2)  |  Auxiliary Space: O(1)
# print('Bubble sort ',arr)
# insertionsort(arr,n)                      # Time Complexity: O(N2) |  Auxiliary Space: O(1)
# print('Insertion sort ',arr)
# quicksort(0,n-1,arr)                     # Time Complexity: Worst case O(N2) | Average case O(N log N)    |   Auxiliary Space: O(1)
# print('QuickSort ',arr)
# mergesort(0,n-1,arr)                   # Time Complexity: O(n*log(n))  |  Auxiliary Space: O(n)
# print("MergeSort ",arr)

x=8
# index = binarysearch(arr,x)
# print('binarySearch found index : ',index)