Join Login Create a Request

Sorting algorithms in Python

Here is a list of sorting algorithms in python 

Bubble sort in Python

Bubble sort derives its name from the fact that the bigger element in the array is bubbled up on each iteration.

def bubble_sort(array):
    n = len(array)

    for i in range(n):
        already_sorted = True

        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

                # you had to swap two elements, set the `already_sorted` flag to `False` so the algorithm can keep going
                already_sorted = False

        # If there were no swaps during the last iteration, the array is sorted
        if already_sorted:
            break

    return array

Insertion sort in Python

This is an algorithm that inserts an unsorted element at a suitable array index in each iteration. Here is how you can implement it using Python.

def insertion_sort(array):
    n = len(array)

    for i in range(1, n):
        # This is the element we want to insert at a right place
        key_item = array[i]
        j = i - 1

        while j >= 0 and array[j] > key_item:
            array[j + 1] = array[j]
            j -= 1

        array[j + 1] = key_item

    return array

Merge Sort in Python

This is a divide and conquer sorting algorithm. Merge sort continuously cuts an array into sub-arrays and then merges them at the end.Here is how it's implemented in python.

def merge(left, right):

    if len(left) == 0:
        return right

    if len(right) == 0:
        return left

    result = []
    index_left = index_right = 0

    while len(result) < len(left) + len(right):

        if left[index_left] <= right[index_right]:
            result.append(left[index_left])
            index_left += 1
        else:
            result.append(right[index_right])
            index_right += 1

        if index_right == len(right):
            result += left[index_left:]
            break

        if index_left == len(left):
            result += right[index_right:]
            break

    return result

Quick Sort Algorithm

It also applies the divide and conquer strategy. It divides the unsorted array into two arrays, one with few elements and the other with more elements. The subarrays are then sorted recursively. Here is how it is implemented in python:

from random import randint

def quicksort(array):

    if len(array) < 2:
        return array

    low, same, high = [], [], []

    pivot = array[randint(0, len(array) - 1)]

    for item in array:

        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)

    return quicksort(low) + same + quicksort(high)

Related Snippets