Sorting algorithms in Python (Detailed Tutorial)

In this Python tutorial, we will discuss the sorting algorithms in python. Also, We will see these below topics as:

• What is an algorithm in python?
• What is sorting in python?
• Python built-in sorting algorithm
• Selection sort in python
• Insertion sort in python
• Bubble sort in python
• Merge sort in python
• Quicksort in python
• Python sorting algorithms time complexity
• A best sorting algorithm in python
• Python sorting algorithms using a library

What is an algorithm in python?

An algorithm in python is a step-by-step procedure, it defines a set of instructions to be executed in a certain order to get the output. An algorithm is generally created independent of the underlying language. This can be a simple process, such as sorting, multiplying two numbers, adding two numbers, etc.

What is sorting in python?

Sorting means arranging data in a particular order and most common orders are in numerical order. The importance of sorting is that data searching is optimized and also it represents the data in a more readable format. These algorithms can be used to organize messy data and make it easier to use.

Python built-in sorting algorithm

To sort elements in python, we can use the built-in function sorted() to sort any Python list. It offers the ability to sort data.

Example:

my_arr = [10, 3, 6, 8, 2, 9]
s = sorted(my_arr)
print(s)

After writing the above code (python built-in sorting algorithm), once you will print ” s “ then the output will be ”[2, 3, 6, 8, 9, 10] ”. We get the output in a sorted way with a new sorted list when we call sorted().

You can refer to the below screenshot for python built-in sorting algorithm.

Selection sort in python

Python Selection sort is a comparison sorting algorithm that is used to sort a list of elements in ascending order. In selection sort, we start by taking the minimum value in the given list and we compare with each element.

Example:

def sort(numbers):
    for i in range(4):
        min_pos = i
        for j in range(i,5):
            if numbers[j] < numbers[min_pos]:
               min_pos = j
        temp = numbers[i]
        numbers[i] = numbers[min_pos]
        numbers[min_pos] = temp
numbers = [8, 6, 4, 2, 3]
sort(numbers)
print(numbers)

After writing the above code (selection sort in python), once you will print ” numbers “ then the output will be ”[2, 3, 4, 6, 8] ”. Here, we repeat the process for each of the remaining elements in the unsorted list, and in the end, all the elements from the unsorted list are sorted.

You can refer to the below screenshot for Selection sort in python.

Insertion sort in python

Python Insertion sort is one of the simple sorting algorithms in Python. It involves finding the right place for a given element in the list.

We compare the first two elements and then we sort them by comparing and again we take the third element and find its position among the previous two and so on.

Example:

def insertion_sort(L):
    for i in range(1, len(L)):
        j = i-1
        next_e = L[i]
        while (L[j] > next_e) and (j >= 0):
            L[j+1] = L[j]
            j = j-1
            L[j+1] = next_e
my_list = [12,3,23,40,20,11]
insertion_sort(my_list)
print(my_list)

After writing the above code (insertion sort in python), once you will print ” my_list “ then the output will be ”[3, 11, 12, 20, 23, 40] ”. Here, the sorting involves finding the right place for the elements by comparing the current element with the next and sorting them in ascending order.

You can refer to the below screenshot for insertion sort in python

Bubble sort in python

Python Bubble sort is the simplest sorting algorithms in Python that works by repeatedly swapping the adjacent elements if they are not in proper order and it continues till we get the element sorted.

It consists of making multiple passes through a list by comparing one by one and swapping them.

Example:

def sort(numbers):
    for i in range(len(numbers)-1,0,-1);
        for j in range(i):
            if numbers[j]>numbers[j+1]:
               temp = numbers[j]
               numbers[j] = numbers[j+1]
               numbers[j+1] = temp
numbers = [6, 3, 7, 5, 8, 2]
sort(numbers)
print(numbers) 

After writing the above code (bubble sort in python), once you will print ” numbers “ then the output will be ”[2, 3, 5, 6, 7, 8] ”. Here, the element will be sorted in ascending order, and in each step, the largest elements will be bubbled at the end of the list.

You can refer to the below screenshot for bubble sort in python

Merge sort in python

Python Merge sort is based on the divide and conquer approach, it first divides the array into two equal-sized parts, sorts each half recursively, and then combines them in a sorted way.

Example:

def merge_sort(unsorted):
    if len(unsorted) <= 1:
        return unsorted
    middle = len(unsorted) // 2
    l_list = unsorted[:middle]
    r_list = unsorted[middle:]
    l_list = merge_sort(l_list)
    r_list = merge_sort(r_list)
    return list(merge(l_list, r_list))
def merge(l_half,r_half):
    s = []
    while len(l_half) != 0 and len(r_half)!=0:
        if l_half[0] < r_half[0]:
            s.append(l_half[0])
            l_half.remove(l_half[0])
        else:
            s.append(r_half[0])
            r_half.remove(r_half[0])
    if len(l_half) == 0:
       s = s + r_half
    else:
       s = s + l_half
    return s
unsorted = [34, 44, 22, 25, 18, 11]
print(merge_sort(unsorted))

After writing the above code (merge sort in python), once you will print ” merge_sort(unsorted)” then the output will be ”[11, 18, 22, 25, 34, 44] ”. Here, the element will be divided into two half and recursively splits the input in half.

A function that merges both halves producing a sorted array at the last.

You can refer to the below screenshot for merge sort in python

Quicksort in python

Python Quicksort is an algorithm based on the divide and conquer approach in which an array is split into subarrays. A pivot element is chosen from the array. Here, the pivot element is s[0], and the elements smaller than the pivot element are put on the left, and the greater element on the right.

Example:

def quick_sort(s):
    if len(s) == 1 or len(s) == 0:
       return s
    else:
        pivot = s[0]
        i = 0
        for j in range(len(s)-1):
            if s[j+1] < pivot:
               s[j+1],s[i+1] = s[i+1],s[j+1]
               i += 1
        s[0],s[i] = s[i],s[0]
        first_part = quick_sort(s[:i])
        second_part = quick_sort(s[i+1:])
        first_part.append(s[i])
        return first_part + second_part
my_list = [64,25,83,47,67,14]
quick_sort(my_list)
print(my_list)

After writing the above code (Quicksort in python), once you will print ” my_list “ then the output will be ”[14, 25, 47, 64, 67, 83] ”. Here, the element will be divided into two subarrays and these subarrays are recursively called to sort the element. A pivot element is compared with the element from the first index.

You can refer to the below screenshot for Quicksort in python

Python sorting algorithms time complexity

The efficiency of an Python sorting algorithms depends on two parameters:

1. Time Complexity – It is defined as the number of steps required depends on the size of the input.
2. Space Complexity – Space complexity is the total memory space required by the program for its execution.

Time Complexity of all sorting algorithm:

Algorithm	BEST	AVERAGE	WORST
Selection Sort	Ω(n^2)	θ(n^2)	O(n^2)
Insertion sort	Ω(n)	θ(n^2)	O(n^2)
Bubble sort	Ω(n)	θ(n^2)	O(n^2)
Merge sort	Ω(n log(n))	θ(n log(n))	O(n log(n))
Quicksort	Ω(n log(n))	θ(n log(n))	O(n^2)

A best sorting algorithm in python

• Quicksort algorithm is one of the most efficient sorting algorithms, and that’s why it is mostly used as it is one of the best algorithms.
• The quicksort uses a divide and conquers algorithm with recursion.
• The time complexity of quicksort is O(n log n) in the best case, O(n log n) in the average case, and O(n^2) in the worst case.
• Quicksort is also considered as the ” fastest” sorting algorithm because it has the best performance in the average case for most inputs.

Python sorting algorithms using a library

• Python has a powerful package that performs many different types of stable and unstable sorting algorithms on the list. This package is very helpful for programmers and developers based on their requirements they can perform any sorting.
• To perform a sorting algorithm we need to import the library first ” from sorting_techniques import pysort “.
• Creating a “s_obj” sort object.

Example:

from sorting_techniques import pysort
s_obj = pysort.Sorting()

Bubble sort using the library in python

Here, we will perform bubble sort by using the library in python.

Example:

from sorting_techniques import pysort
s_obj = pysort.Sorting()
my_list = [34,56,43,22,19,10]
l_sort = s_obj.bubbleSort(my_list)
print(l_sort)

After writing the above code (bubble sort using the library in python), once you will print ” l_sort” then the output will be ”[10, 19, 22, 34, 43, 56 ] ”. Here, we created a s_obj, and then l_sort will generate a sort result which will print the sorted list.

You can refer to the below screenshot for bubble sort using the library in python

Insertion sort using the library in python

Here, we will perform insertion sort by using the library in python.

Example:

from sorting_techniques import pysort
s_obj = pysort.Sorting()
my_list = [44,36,13,22,29,20]
l_sort = s_obj.insertionSort(my_list)
print(l_sort)

After writing the above code (insertion sort using the library in python), once you will print ” l_sort” then the output will be ” [13, 20, 22, 29, 36, 44] ”. Here, we created a s_obj, and then l_sort will generate a sort result which will print the sorted list.

You can refer to the below screenshot for insertion sort using the library in python

Selection sort using the library in python

We will perform insertion sort by using the library in python.

Example:

from sorting_techniques import pysort
s_obj = pysort.Sorting()
my_list = [64,86,33,32,29,30]
l_sort = s_obj.selectionSort(my_list)
print(l_sort)

After writing the above code (selection sort using the library in python), once you will print ” l_sort” then the output will be ” [29, 30, 32, 33, 64, 86] ”. Now, we created a s_obj, and then l_sort will generate a sort result which will print the sorted list.

You can refer to the below screenshot for selection sort using the library in python

Merge sort using the library in python

We will perform merge sort by using the library in python.

Example:

from sorting_techniques import pysort
s_obj = pysort.Sorting()
my_list = [14,16,13,22,25,30]
l_sort = s_obj.mergeSort(my_list)
print(l_sort)

After writing the above code (merge sort using the library in python), once you will print ” l_sort” then the output will be ” [13, 14, 16, 22, 25, 30] ”. Now, we created a s_obj, and then l_sort will generate a sort result which will print the sorted list.

You can refer to the below screenshot for merge sort using the library in python

You may like the following Python tutorials:

• Python convert list to string
• Python sort list of tuples
• Working with JSON data in Python
• Send email using Python
• Python get an IP Address
• Python – stderr, stdin and stdout
• Increment and Decrement operators in Python

In this Python tutorial, we learned about the sorting algorithms in python. Also, we covered these below topics:

• What is an algorithm in python?
• What is sorting in python?
• Python built-in sorting algorithm
• Selection sort in python
• Insertion sort in python
• Bubble sort in python
• Merge sort in python
• Quicksort in python
• Python sorting algorithms time complexity
• A best sorting algorithm in python
• Python sorting algorithms using a library