<jupyter_start><jupyter_text>Quick sorthttps://www.geeksforgeeks.org/quick-sort/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.The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.    3,1,4,1,2    parition pivot_index = 4    1,1,2,3,4    pivot index = 2        3, 1 ----> partition: 1,   3 pivot index = 0    1, 2 ----> partition: 1,    2 pivot index = 1Time complexity: O(nlogn) average and O(n^2) worstSpace complexity: O(1)<jupyter_code>class QuickSort():
    def __call__(self, arr):
        self.sort(arr, 0, len(arr)-1)
        return arr
    
    def sort(self,arr,low, high):#0,1
        if low < high:
            pivot_index = self.parition(arr,low, high)
            self.sort(arr, low, pivot_index-1)
            self.sort(arr, pivot_index+1, high)

    def parition(self,arr,low, high):
        pivot_index = high
        i = low
        for j in range(low, high):
            if a[j] < arr[pivot_index]:
                a[i] , a[j]= a[j], a[i]
                i += 1
        a[i],a[pivot_index] = a[pivot_index], a[i]
        return i

import numpy as np
a = np.random.randint(0,1000, size = (1000,))
print(a[:10])
%timeit QuickSort()(a)<jupyter_output>[485 808 999 932 267 183 358 614 642 890]
215 ms ± 28.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)<jupyter_text>MergeSort 1. divide the array2. Sort both the arrays3. MergeO(nlogn) time O(n) space<jupyter_code>class MergeSort(QuickSort):
    def sort(self, arr, low, high):
        if low<high:
            mid = low + (high-low+1)//2
            self.sort(arr, low, mid-1)
            self.sort(arr, mid, high)
            self.merge(arr, low, high, mid)
    def merge(self, arr , low, high, mid):
        left = arr[low:mid]#[1]
        right = arr[mid:high+1]#[2]
        ri = 0
        li = 0
        ai = low
        while li < len(left):
            if ri == len(right) or left[li]<right[ri]:
                arr[ai] = left[li]
                li += 1
            else:
                arr[ai] = right[ri]
                ri += 1
            ai += 1            
        
print(a[:10])
%timeit MergeSort()(a)<jupyter_output>[ 0  5  6  7  7  7  8  8  9 13]
5.08 ms ± 607 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)<jupyter_text>BinarySearch<jupyter_code>def binary_search(arr, low, high, elem):
    # assume arr is sorted
    print('searching')
    if low > high:
        return -1
    
    mid = low + (high-low+1)//2 # right preference

    if arr[mid] == elem:
        return mid
    elif arr[mid]> elem:
        return binary_search(arr, low, mid-1, elem)
    else:
        return binary_search(arr, mid+1, high, elem)
a = list(range(100))
print(a)
binary_search(a, 0, len(a)-1, 19)<jupyter_output>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
searching
searching
searching
searching
{'fraction_non_alphanumeric': 0.1307277628032345, 'fraction_numerical': 0.08733153638814016, 'mean_word_length': 2.445682451253482, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 29, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '460965', 'license': 'Apache-2.0', 'n_tokens_mistral': 1603, 'n_tokens_neox': 1300, 'n_words': 484, 'path': 'interview/coding/Sorting_Searching.ipynb', 'repo_name': 'krishansubudhi/krishanAI', 'size': '3710'}