<jupyter_start><jupyter_text>Various Sorting Algorithms  Selection Sort* Time : $O(n^2)$* Space: $O(1)$<jupyter_code>def selection_sort(a):
    for i in range(0, len(a)-1):
        imin = i
        for j in range(imin+1, len(a)):
            if a[j] < a[imin]:
                imin = j
        temp = a[imin]
        a[imin] = a[i]
        a[i] = temp
    return a
a = [1]
b = [1,4,5,2,7,6]
print(selection_sort(a))
print(selection_sort(b))<jupyter_output>[1]
[1, 2, 4, 5, 6, 7]<jupyter_text>Insertion Sort  * Time : $O(n^2)$  * Space: $O(1)$<jupyter_code>def insertion_sort(a):
    if len(a) < 2:
        return a
    for i in range(1, len(a)):
        temp = a[i]
        hole = i
        while hole > 0 and a[hole-1] > temp:
            a[hole] = a[hole-1]
            hole -= 1
        a[hole] = temp
    return a
a = [1]
b = [1,0,4,5,2,7,6]
print(insertion_sort(a))
print(insertion_sort(b))<jupyter_output>[1]
[0, 1, 2, 4, 5, 6, 7]<jupyter_text>Quick Sort  * Time : $O(n log n)$  * Space: $O(log n)$<jupyter_code>def partition(a, start, end):
    pindex = end
    j = start
    for i in range(start, end):
        if a[i] < a[pindex]:
            a[i], a[j] = a[j], a[i]
            j += 1
    a[pindex], a[j] = a[j], a[pindex]
    return j

def quick_sort(a, start, end):
    if start < end:
        pindex = partition(a, start, end)
        quick_sort(a, start, pindex-1)
        quick_sort(a, pindex+1, end)
a = [1]
b = [1,4,5,2,7,0,6,3]
quick_sort(a, 0, len(a)-1)
quick_sort(b, 0, len(b)-1)
print(a)
print(b)<jupyter_output>[1]
[0, 1, 2, 3, 4, 5, 6, 7]<jupyter_text>Merge Sort  * Time : $O(nlogn)$  * Space: $O(n)$<jupyter_code>def merge(a, b):
    i = 0
    j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1
    if i < len(a):
        res = res + a[i:]
    if j < len(b):
        res = res + b[j:]
    return res

def merge_sort(a):
    if len(a) < 2:
        return a
    
    mid = len(a) // 2
    left = a[:mid]
    right = a[mid:]
    return merge(merge_sort(left), merge_sort(right))
a = [2,4,7,1,0,3,5]
b = [5,2,4,1,7,6,0,3]
print(merge_sort(a))
print(merge_sort(b))<jupyter_output>[0, 1, 2, 3, 4, 5, 7]
[0, 1, 2, 3, 4, 5, 6, 7]
{'fraction_non_alphanumeric': 0.19080962800875273, 'fraction_numerical': 0.045514223194748356, 'mean_word_length': 2.2750716332378222, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 15, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '148756', 'license': 'MIT', 'n_tokens_mistral': 1079, 'n_tokens_neox': 1023, 'n_words': 245, 'path': 'Algorithms/Sorting Algorithms.ipynb', 'repo_name': 'varian97/ComputerScience-Notebook', 'size': '2285'}