<jupyter_start><jupyter_text>Sorting  Bubble Sort<jupyter_code>def bubbleSort(customList):
    for i in range(len(customList)):
        for j in range(len(customList)-i-1): # since at the top of the part is filled with maximum value, we need to subtract i
            if customList[j] > customList[j+1]:
                customList[j], customList[j+1] = customList[j+1], customList[j]
    print(customList)
    
cList = [2,1,7,6,5,3,4,9,8]
bubbleSort(cList)<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9]<jupyter_text>Selection Sort<jupyter_code>def selectionSort(customList):
    sortedList = []
    for i in range(len(customList)):
        min_index = i
        for j in range(i+1, len(customList)):
            if customList[min_index] > customList[j]:
                min_index = j
        customList[i], customList[min_index] = customList[min_index], customList[i]
    print(customList)
    
cList = [2,1,7,6,5,3,4,9,8]
selectionSort(cList)<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9]<jupyter_text>Insertion Sort<jupyter_code>def insertionSort(customList):
    # for: i is right side of the criteria / j is left side of the criteria
    for i in range(1, len(customList)):
        key = customList[i]
        j = i-1
        while j >= 0 and customList[j] > key:
            customList[j+1]=customList[j]
            j -= 1
        customList[j+1]=key
    return customList
    
    
cList = [2,1,7,6,5,3,4,9,8]
print(insertionSort(cList))<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9]<jupyter_text>Bucket Sort<jupyter_code>import math
def bucketSort(customList):
    numberofBuckets = round(math.sqrt(len(customList)))
    maxValue = max(customList)
    arr = []
    
    # make buckets
    for i in range(numberofBuckets):
        arr.append([])
    
    # bucker selection
    for j in customList:
        index_b = math.ceil(j*numberofBuckets/maxValue)
        arr[index_b-1].append(j)
        
    # sort inside of the buckets
    for i in range(numberofBuckets):
        arr[i] = insertionSort(arr[i])
        
    
    k = 0
    for i in range(numberofBuckets):
        for j in range(len(arr[i])):
            customList[k] = arr[i][j]
            k+=1
    return customList

    
cList = [2,1,7,6,5,3,4,9,8]
print(bucketSort(cList))<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9]<jupyter_text>Merge Sort<jupyter_code>def merge(customList, l, m, r):
    # number of elements in first sub array
    n1 = m-l+1
    # number of elements in second sub array
    n2 = r-m
    
    L = [0]*(n1)
    R = [0]*(n2)
    
    # divide array as two
    for i in range(0, n1):
        L[i] = customList[l+i]
        
    for j in range(0, n2):
        R[j] = customList[m+1+j]
        
    i = 0 # initial index of first sub array
    j = 0 # initial index of second sub array
    k = l # initial index of merged array
    
    # combine arrays as one
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            customList[k] = L[i]
            i+=1
        else:
            customList[k] = R[j]
            j+=1
        k+=1
    # since one of the arrays amog L or R is reached the last index, we can use the following loop
    while i < n1:
        customList[k] = L[i]
        i+=1
        k+=1
    while j < n2:
        customList[k] = R[j]
        j+=1
        k+=1
        
def mergeSort(customList, l, r):
    if l < r:
        m = (l+(r-1))//2
        mergeSort(customList, l, m)
        mergeSort(customList, m+1, r)
        merge(customList, l, m, r)
    return customList
    
cList = [2,1,7,6,5,3,4,9,8]
mergeSort(cList, 0, len(cList)-1)<jupyter_output><empty_output><jupyter_text>Quick Sort<jupyter_code>def partition(customList, low, high):
    i = low - 1
    pivot =customList[high] # We chose the index at the last node as a pivot
    for j in range(low, high):
        if customList[j] <= pivot:
            i+=1
            customList[i],customList[j] = customList[j], customList[i]
    customList[i+1], customList[high] = customList[high], customList[i+1]
    return (i+1)

def quickSort(customList, low, high):
    if low < high:
        pi = partition(customList, low, high)
        quickSort(customList, low, pi-1)
        quickSort(customList, pi, high)
        
cList = [2,1,7,6,5,3,4,9,8]
quickSort(cList, 0, len(cList)-1)
print(cList)<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9]<jupyter_text>Heap Sort<jupyter_code>def heapify(customList, n, i):
    smallest = i
    l = 2*i + 1
    r = 2*i + 2
    if l<n and customList[l]<customList[smallest]:
        smallest = l
    if r<n and customList[r]<customList[smallest]:
        smallest = r
    if smallest != i:
        customList[i], customList[smallest] = customList[smallest], customList[i]
        heapify(customList, n, smallest)

def heapSort(customList):
    n = len(customList)
    for i in range(int(n/2)-1,-1,-1):
        heapify(customList,n,i)
        
    for i in range(n-1,0,-1):
        customList[i],customList[0] = customList[0], customList[i]
        heapify(customList, i, 0)
    customList.reverse()
    
cList = [2,1,7,6,5,3,4,9,8]
heapSort(cList)
print(cList)<jupyter_output>[1, 2, 3, 4, 5, 6, 7, 8, 9]
{'fraction_non_alphanumeric': 0.13663133097762073, 'fraction_numerical': 0.035924617196702, 'mean_word_length': 2.5729312762973353, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 27, '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': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '478257', 'license': 'CECILL-B', 'n_tokens_mistral': 2005, 'n_tokens_neox': 1922, 'n_words': 478, 'path': '.ipynb_checkpoints/17_Sorting-checkpoint.ipynb', 'repo_name': 'ChicagoPark/DSA', 'size': '5094'}