Skip to content

Sorting

Bubble Sort

Bubble sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The process is repeated until the list is sorted.

  • Time complexity: O(n^2)
  • Space complexity: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
array_to_bubble_sorting = [-5, 3, 2, 1, -3, -3, 7, 2, 2]


def bubble_sort(array):
    n = len(array)
    flag = True
    while flag:
        flag = False
        for index in range(1, n):
            if array[index - 1] > array[index]:
                flag = True
                array[index - 1], array[index] = array[index], array[index - 1]


bubble_sort(array_to_bubble_sorting)

array_to_bubble_sorting

[-5, -3, -3, 1, 2, 2, 2, 3, 7]

Insertion Sort

Insertion sort is a simple comparison-based sorting algorithm. It builds the sorted array one item at a time by repeatedly taking the next unsorted item and inserting it into the correct position in the already sorted portion of the array.

  • Time complexity: O(n^2)
  • Space complexity: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
array_to_insertion_sorting = [-5, 3, 2, 1, -3, -3, 7, 2, 2]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if array[j - 1] > array[j]:
                array[j - 1], array[j] = array[j], array[j - 1]
            else:
                break


insertion_sort(array_to_insertion_sorting)

array_to_insertion_sorting

[-5, -3, -3, 1, 2, 2, 2, 3, 7]

Selection Sort

Selection sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and swapping it with the first unsorted element until the entire list is sorted.

  • Time complexity: O(n^2)
  • Space complexity: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
array_to_selection_sorting = [-5, 3, 2, 1, -3, -3, 7, 2, 2]


def selection_sort(array):
    n = len(array)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if array[j] < array[min_index]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]


selection_sort(array_to_selection_sorting)

array_to_selection_sorting

[-5, -3, -3, 1, 2, 2, 2, 3, 7]

Merge Sort

Merge sort is a divide-and-conquer algorithm that works by recursively dividing the list into smaller sublists until each sublist contains a single element. Then, it merges those sublists back together in a sorted order.

  • Time complexity: O(n log n)
  • Space complexity: O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
array_to_merge_sorting = [-5, 3, 2, 1, -3, -3, 7, 2, 2]


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

    if n == 1:
        return array

    m = len(array) // 2
    L = array[:m]
    R = array[m:]

    L = merge_sort(L)
    R = merge_sort(R)
    l, r = 0, 0
    L_len = len(L)
    R_len = len(R)

    sorted_array = [0] * n
    i = 0

    while l < L_len and r < R_len:
        if L[l] < R[r]:
            sorted_array[i] = L[l]
            l += 1
        else:
            sorted_array[i] = R[r]
            r += 1

        i += 1

    while l < L_len:
        sorted_array[i] = L[l]
        l += 1
        i += 1

    while r < R_len:
        sorted_array[i] = R[r]
        r += 1
        i += 1

    return sorted_array


merge_sort(array_to_merge_sorting)

[-5, -3, -3, 1, 2, 2, 2, 3, 7]

Quick Sort

Quick sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

  • Time complexity: O(n log n) on average, O(n^2) in the worst case
  • Space complexity: O(log n) on average, O(n) in the worst case
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
array_to_quick_sorting = [-5, 3, 2, 1, -3, -3, 7, 2, 2]


def quick_sort(array):
    if len(array) <= 1:
        return array

    p = array[-1]

    L = [x for x in array[:-1] if x <= p]
    R = [x for x in array[:-1] if x > p]

    L = quick_sort(L)
    R = quick_sort(R)

    return L + [p] + R


quick_sort(array_to_quick_sorting)

[-5, -3, -3, 1, 2, 2, 2, 3, 7]

Counting Sort

Counting sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each unique element in the input array. It then uses this count to determine the position of each element in the output array.

  • Time complexity: O(n + k), where n is the number of elements in the input array and k is the range of the input values

  • Space complexity: O(n + k)

  • k: the range of the input values (the difference between the maximum and minimum values in the input array)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
array_to_counting_sorting = [5, 3, 2, 1, 3, 3, 7, 2, 2]


def counting_sort(array):
    """
    Implementation just for positive values
    """
    n = len(array)
    maxx = max(array)
    counts = [0] * (maxx + 1)

    for x in array:
        counts[x] += 1

    i = 0
    for c in range(maxx + 1):
        while counts[c] > 0:
            array[i] = c
            i += 1
            counts[c] -= 1


counting_sort(array_to_counting_sorting)

array_to_counting_sorting

[1, 2, 2, 2, 3, 3, 3, 5, 7]

Python Sort methods

Tim sort is the built-in sorting algorithm in Python, which is a hybrid sorting algorithm derived from merge sort and insertion sort. It is designed to perform well on many kinds of real-world data.

  • Time complexity: O(n log n) on average, O(n) in the best case (when the input is already sorted)
  • Space complexity: O(n)

Methods:

  • sorted: returns a new sorted list from the items in an iterable.
  • list.sort: sorts the list in place and returns None.
1
2
3
4
5
array_to_python_sorted = [5, 3, 2, 1, 3, 3, 7, 2, 2]

new_sorted_array = sorted(array_to_python_sorted)

array_to_python_sorted, new_sorted_array

([5, 3, 2, 1, 3, 3, 7, 2, 2], [1, 2, 2, 2, 3, 3, 3, 5, 7])

Sorting a list of tuples

1
2
3
4
tuples_array = [(-5, 3), (2, 1), (-3, -3), (7, 2), (2, 2)]
sorted_tuples_array = sorted(tuples_array, key=lambda t: t[0])

sorted_tuples_array

[(-5, 3), (-3, -3), (2, 1), (2, 2), (7, 2)]