Python Sorting Algorithms

1. bubbleSort

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

2. radixSort

def radix(arr):

    digit = 0
    max_digit = 1
    max_value = max(arr)
    while 10**max_digit < max_value:
        max_digit = max_digit + 1

    while digit < max_digit:
        temp = [[] for i in range(10)]
        for i in arr:
            t = int((i/10**digit)%10)
            temp[t].append(i)

        coll = []
        for bucket in temp:
            for i in bucket:
                coll.append(i)

        arr = coll
        digit = digit + 1

    return arr

3. selectionSort

def selectionSort(arr):
    for i in range(len(arr) - 1):
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # exchange when i is not the min
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

4. insertionSort

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

5. shellSort

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

6. mergeSort

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

7. quickSort

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

10 Replies to “Python Sorting Algorithms”

  1. I just could not leave your website before suggesting that I actually enjoyed
    the standard info a person provide on your guests?
    Is going to be again continuously to inspect new posts

  2. Hi, I do think this is an excellent site. I stumbledupon it 😉 I will
    come back yet again since I book marked it. Money and freedom
    is the best way to change, may you be rich and continue to help others.

  3. Hello very cool website!! Man .. Excellent .. Wonderful ..
    I’ll bookmark your website and take the feeds additionally…I am
    glad to search out a lot of helpful information here in the submit,
    we need work out extra techniques on this regard,
    thank you for sharing.

    my homepage: Carb Cycle Keto

  4. Hey There. I found your blog using msn. This is a very well written article. I抣l make sure to bookmark it and return to read more of your useful information. Thanks for the post. I will certainly return.

Leave a Reply

Your email address will not be published. Required fields are marked *