<jupyter_start><jupyter_text>Selection Sort<jupyter_code>def selection_sort(L):
    n = len(L)
    if n < 2:
        return
    for i in range(n - 1):
        smallest_idx = i
        for j in range(i + 1, n):
            if L[j] < L[smallest_idx]:
                smallest_idx = j
        if smallest_idx != i:
            L[smallest_idx], L[i] = L[i], L[smallest_idx]
L = list(np.random.randint(-100, 100, 10))
selection_sort(L)
L<jupyter_output><empty_output><jupyter_text>Time complexity is __$O(n^2)$__ assuming comparisons can be done in constant time ($O(1)$). It does not use any extra memory.  Bubble Sort<jupyter_code>def bubble_sort(L):
    n = len(L)
    if n < 2:
        return
    for i in range(n - 1):
        for j in range(n - i - 1):
            if L[j] > L[j + 1]:
                L[j], L[j + 1] = L[j + 1], L[j]
L = list(np.random.randint(-100, 100, 10))
bubble_sort(L)
L<jupyter_output><empty_output><jupyter_text>Time complexity is __$O(n^2)$__ assuming comparisons can be done in constant time ($O(1)$). It does not use any extra memory.<jupyter_code>def improved_bubble_sort(L):
    n = len(L)
    if n < 2:
        return
    for i in range(n - 1):
        sorted_flag = True
        for j in range(n - i - 1):
            if L[j] > L[j + 1]:
                L[j], L[j + 1] = L[j + 1], L[j]
                sorted_flag = False
        if sorted_flag: # The array is already sorted
            break
L = list(np.random.randint(-100, 100, 10))
improved_bubble_sort(L)
L<jupyter_output><empty_output><jupyter_text>Time complexity is __$O(n)$__ in the best case when the colloection is sorted; however, the average and worst case is __$O(n^2)$__.  Insertion Sort<jupyter_code>def insertion_sort(L):
    n = len(L)
    if n < 2:
        return
    for i in range(1, n):
        key = L[i]
        j = i
        while j > 0 and key < L[j - 1]:
            L[j] = L[j - 1]
            j -= 1
        L[j] = key
L = list(np.random.randint(-100, 100, 10))
insertion_sort(L)
L<jupyter_output><empty_output><jupyter_text>Time complexity is __$O(n)$__ in the best case when the colloection is sorted; however, the average and worst case is __$O(n^2)$__.  Merge Sort<jupyter_code>def merge(left, right, L):
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            L[i + j] = left[i]
            i += 1
        else:
            L[i + j] = right[j]
            j += 1
    while i < len(left):
        L[i + j] = left[i]
        i += 1
    while j < len(right):
        L[i + j] = right[j]
        j += 1

def merge_sort(L):
    n = len(L)
    if n < 2:
        return
    # divide
    mid = n // 2
    left = L[:mid]
    right = L[mid:]
    # concquer
    merge_sort(left)
    merge_sort(right)
    merge(left, right, L)
L = list(np.random.randint(-100, 100, 10))
merge_sort(L)
L<jupyter_output><empty_output><jupyter_text>Time complexity is __$O(nlogn)$__ in the worst case. Also, this is not an inplace sorting algorithm and it will take __$O(n)$__ extra memory for all the sub-lists.  Quick Sort  Time complexity is __$O(n^2)$__ in the worst case. However, we can get an average case of __$O(nlogn)$__ if we use randomized pivot. It is very widely used in practice due to its high efficiency with high probability. The worst case may happen when the array is already sorted or it is all duplicates.<jupyter_code>def quick_sort(L):
    n = len(L)
    if n < 2:
        return L
    L = list(L)
    pivot = np.random.choice(L)
    L.remove(pivot)
    left = [e for e in L if e <= pivot]
    right = [e for e in L if e > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)
L = list(np.random.randint(-100, 100, 10))
quick_sort(L)<jupyter_output><empty_output><jupyter_text>Counting Sort<jupyter_code>def count_sort(L, R):
    """Count sort using 0-k(inclusive) integers as the keys."""
    n = len(L)
    count = [0] * (R + 1)

    # count number of elements equal to index i
    for e in L:
        count[e + 1] += 1

    # cumsum of count where count[i] will be the number of elements <= index i
    for i in range(R):
        count[i + 1] += count[i]

    # Distribute the data into the correct order
    tmp = [0] * n
    for e in L:
        tmp[count[e]] = e
        count[e] += 1

    # copy the output back
    for i, e in enumerate(tmp):
        L[i] = e
L = [2, 5, 3, 0, 2, 3, 0, 3]
count_sort(L, 10)
L<jupyter_output><empty_output><jupyter_text>The running time is $O(n + k)$ which is linear as long as $k = n^{O(1)}$. Space complexity is $O(n + k)$. It works well with small range of integers.  LSD Radix Sort<jupyter_code>def lsd(L, w):
    n = len(L)
    R = 256

    for d in range(w - 1, -1, -1):
        count = [0] * (R + 1)

        # Build freq counts
        for key in L:
            count[ord(key[d]) + 1] += 1
        
        # Comp cumsum
        for i in range(R):
            count[i + 1] += count[i]
        
        # Distribute keys
        tmp = [0] * n
        for key in L:
            tmp[count[ord(key[d])]] = key
            count[ord(key[d])] += 1
        
        # Copy back sorted keY
        for i, key in enumerate(tmp):
            L[i] = key
L = ['123', '321', '000', '111']
lsd(L, len(L[0]))
L<jupyter_output><empty_output><jupyter_text>LSD radix sort running time is $O(d(N + R))$.  Bucket Sort<jupyter_code>def bucket_sort(L, k):
    n = len(L)
    bucket = [[] for _ in range(k)]
    for e in L:
        bucket[e].append(e)
    output = [0] * n
    i = 0
    for k in bucket:
        for e in k:
            output[i] = e
            i += 1
    return output
L = [2, 5, 3, 0, 2, 3, 0, 3]
bucket_sort(L, 5)<jupyter_output><empty_output><jupyter_text>The running time is $O(n + k)$ which is linear as long as $k = n^{O(1)}$. Space complexity is $O(n + k)$. It works well with small range of integers.  Heap Sort<jupyter_code>class HeapSort:
    @staticmethod
    def sort(arr):
        n = len(arr)
        HeapSort._heapify(arr)
        for i in range(1, n):
            HeapSort._swap(arr, 0, n - i)
            HeapSort._downheap(arr, 0, n - i)
    
    @staticmethod
    def _swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]
    
    @staticmethod
    def _heapify(arr):
        n = len(arr)
        parent = (n - 1) // 2
        for i in range(parent, -1, -1):
            HeapSort._downheap(arr, i, n)
    
    @staticmethod
    def _downheap(arr, i, j):
        if (2 * i) + 1 < j:
            child = left = (2 * i) + 1
            if (2 * i) + 2 < j:
                right = (2 * i) + 2
                if arr[right] < arr[left]:
                    child = right
            if arr[child] < arr[i]:
                HeapSort._swap(arr, i, child)
                HeapSort._downheap(arr, child, j)
L = list(np.random.randint(-100, 100, 10))
HeapSort.sort(L)
L, L[::-1]<jupyter_output><empty_output><jupyter_text>The running time is $O(nlogn)$.  Randomized Quick Select<jupyter_code>def quick_select(S, k):
    n = len(S)
    if n == 1:
        return S[0]
    pivot = np.random.choice(S)
    L = [e for e in S if e < pivot]
    E = [e for e in S if e == pivot]
    G = [e for e in S if e > pivot]
    
    if k <= len(L):
        return quick_select(L, k)
    elif k <= len(L) + len(E):
        return pivot
    else:
        j = k - len(L) - len(E)
        return quick_select(G, j)
for i in range(1000):
    try:
        k = np.random.randint(1, 11, 1)[0]
        quick_select(np.random.randint(-100, 100, 10), k)
    except:
        print('failed')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13563157194196726, 'fraction_numerical': 0.024623985092506323, 'mean_word_length': 2.1439330543933055, 'pattern_counts': {'":': 0, '<': 67, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '656941', 'license': 'Apache-2.0', 'n_tokens_mistral': 2940, 'n_tokens_neox': 2757, 'n_words': 873, 'path': 'sorting/Sorting.ipynb', 'repo_name': 'ImadDabbura/data-structures-and-algorithms', 'size': '7513'}