Sorting Algorithms in Python - GeeksforGeeks (2024)

Sorting is defined as an arrangement of data in a certain order. Sorting techniques are used to arrange data(mostly numerical) in an ascending or descending order. It is a method used for the representation of data in a more comprehensible format. It is an important area of Computer Science. Sorting a large amount of data can take a substantial amount of computing resources if the methods we use to sort the data are inefficient. The efficiency of the algorithm is proportional to the number of items it is traversing. For a small amount of data, a complex sorting method may be more trouble than it is worth. On the other hand, for larger amounts of data, we want to increase the efficiency and speed as far as possible. We will now discuss the several sorting techniques and compare them with respect to their time complexity.

Sorting Algorithms in Python - GeeksforGeeks (1)

Some of the real-life examples of sorting are:

  • Telephone Directory: It is a book that contains telephone numbers and addresses of people in alphabetical order.
  • Dictionary: It is a huge collection of words along with their meanings in alphabetical order.
  • Contact List: It is a list of contact numbers of people in alphabetical order on a mobile phone.

Before discussing the different algorithms used to sort the data given to us, we should think about the operations which can be used for the analysis of a sorting process. First, we need to compare the values to see which one is smaller and which one is larger so that they can be sorted into an order, it will be necessary to have an organized way to compare values to see that if they are in order.

The different types of order are:

  • Increasing Order: A set of values are said to be increasing order when every successive element is greater than its previous element. For example: 1, 2, 3, 4, 5. Here, the given sequence is in increasing order.
  • Decreasing Order: A set of values are said to be in decreasing order when the successive element is always less than the previous one. For Example: 5, 4, 3, 2, 1. Here the given sequence is in decreasing order.
  • Non-Increasing Order: A set of values are said to be in non-increasing order if every ith element present in the sequence is less than or equal to its (i-1)th element. This order occurs whenever there are numbers that are being repeated. For Example: 5, 4, 3, 2, 2, 1. Here 2 repeated two times.
  • Non-Decreasing Order: A set of values are said to be in non-decreasing order if every ith element present in the sequence is greater than or equal to its (i-1)th element. This order occurs whenever there are numbers that are being repeated. For Example: 1, 2, 2, 3, 4, 5. Here 2 repeated two times.

Sorting Techniques

The different implementations of sorting techniques in Python are:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort

Bubble Sort

Bubble Sort is a simple sorting algorithm. This sorting algorithm repeatedly compares two adjacent elements and swaps them if they are in the wrong order. It is also known as the sinking sort. It has a time complexity of O(n2) in the average and worst cases scenarios and O(n) in the best-case scenario. Bubble sort can be visualized as a queue where people arrange themselves by swapping with each other so that they all can stand in ascending order of their heights. Or in other words, we compare two adjacent elements and see if their order is wrong, if the order is wrong we swap them. (i.e arr[i] > arr[j] for 1 <= i < j <= s; where s is the size of the array, if array is to be in ascending order, and vice-versa).


Here we sort the following sequence using bubble sort

Sequence: 2, 23, 10, 1

First Iteration

(2, 23, 10, 1) –> (2, 23, 10, 1), Here the first 2 elements are compared and remain the same because they are already in ascending order.

(2, 23, 10, 1) –> (2, 10, 23, 1), Here 2nd and 3rd elements are compared and swapped(10 is less than 23) according to ascending order.

(2, 10, 23, 1) –> (2, 10, 1, 23), Here 3rd and 4th elements are compared and swapped(1 is less than 23) according to ascending order

At the end of the first iteration, the largest element is at the rightmost position which is sorted correctly.

Second Iteration

(2, 10, 1, 23) –> (2, 10, 1, 23), Here again, the first 2 elements are compared and remain the same because they are already in ascending order.

(2, 10, 1, 23) –> (2, 1, 10, 23), Here 2nd and 3rd elements are compared and swapped(1 is less than 10) in ascending order.

At the end of the second iteration, the second largest element is at the adjacent position to the largest element.

Third Iteration

(2, 1, 10, 23) –> (1, 2, 10, 23), Here the first 2 elements are compared and swap according to ascending order.

The remaining elements are already sorted in the first and second Iterations. After the three iterations, the given array is sorted in ascending order. So the final result is 1, 2, 10, 23.

Implementation of Bubble Sort:

# Python3 program for Bubble Sort Algorithm Implementationdef bubbleSort(arr): n = len(arr) # For loop to traverse through all  # element in an array for i in range(n): for j in range(0, n - i - 1): # Range of the array is from 0 to n-i-1 # Swap the elements if the element found  #is greater than the adjacent element if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] # Driver code# Example to test the above codearr = [ 2, 1, 10, 23 ]bubbleSort(arr)print("Sorted array is:")for i in range(len(arr)): print("%d" % arr[i])


Sorted array is:121023

Time Complexity: O(n2)
Auxiliary Space: O(1)

Selection Sort

This sorting technique repeatedly finds the minimum element and sort it in order. Bubble Sort does not occupy any extra memory space. During the execution of this algorithm, two subarrays are maintained, the subarray which is already sorted, and the remaining subarray which is unsorted. During the execution of Selection Sort for every iteration, the minimum element of the unsorted subarray is arranged in the sorted subarray. Selection Sort is a more efficient algorithm than bubble sort. Sort has a Time-Complexity of O(n2) in the average, worst, and in the best cases.


Here we sort the following sequence using the selection sort

Sequence: 7, 2, 1, 6

(7, 2, 1, 6) –> (1, 7, 2, 6), In the first traverse it finds the minimum element(i.e., 1) and it is placed at 1st position.

(1, 7, 2, 6) –> (1, 2, 7, 6), In the second traverse it finds the 2nd minimum element(i.e., 2) and it is placed at 2nd position.

(1, 2, 7, 6) –> (1, 2, 6, 7), In the third traverse it finds the next minimum element(i.e., 6) and it is placed at 3rd position.

After the above iterations, the final array is in sorted order, i.e., 1, 2, 6, 7.

Implementation of Selection Sort

# Selection Sort algorithm in Pythondef selectionSort(array, size): for s in range(size): min_idx = s for i in range(s + 1, size): # For sorting in descending order # for minimum element in each loop if array[i] < array[min_idx]: min_idx = i # Arranging min at the correct position (array[s], array[min_idx]) = (array[min_idx], array[s])# Driver codedata = [ 7, 2, 1, 6 ]size = len(data)selectionSort(data, size)print('Sorted Array in Ascending Order is :')print(data)

Time Complexity: O(n2)
Auxiliary Space: O(1)

Insertion Sort

This sorting algorithm maintains a sub-array that is always sorted. Values from the unsorted part of the array are placed at the correct position in the sorted part. It is more efficient in practice than other algorithms such as selection sort or bubble sort. Insertion Sort has a Time-Complexity of O(n2) in the average and worst case, and O(n) in the best case.


Here we sort the following sequence using the insertion sort

Sequence: 7, 2, 1, 6

(7, 2, 1, 6) –> (2, 7, 1, 6), In the first iteration, the first 2 elements are compared, here 2 is less than 7 so insert 2 before 7.

(2, 7, 1, 6) –> (2, 1, 7, 6), In the second iteration the 2nd and 3rd elements are compared, here 1 is less than 7 so insert 1 before 7.

(2, 1, 7, 6) –> (1, 2, 7, 6), After the second iteration (1, 7) elements are not in ascending order so first these two elements are arranged. So, insert 1 before 2.

(1, 2, 7, 6) –> (1, 2, 6, 7), During this iteration the last 2 elements are compared and swapped after all the previous elements are swapped.

Implementation of Insertion Sort

# Creating a function for insertion sort algorithmdef insertion_sort(list1): # Outer loop to traverse on len(list1)  for i in range(1, len(list1)): a = list1[i] # Move elements of list1[0 to i-1],  # which are greater to one position # ahead of their current position  j = i - 1 while j >= 0 and a < list1[j]: list1[j + 1] = list1[j] j -= 1 list1[j + 1] = a return list1 # Driver codelist1 = [ 7, 2, 1, 6 ] print("The unsorted list is:", list1) print("The sorted new list is:", insertion_sort(list1)) 


The unsorted list is: [7, 2, 1, 6]The sorted new list is: [1, 2, 6, 7]

Time Complexity: O(n2)
Auxiliary Space: O(1)




Next Article

Bucket Sort in Python

Please Login to comment...

Sorting Algorithms in Python - GeeksforGeeks (2024)


What algorithm does Python use for sorting? ›

Python's default sort uses Tim Sort, which is a combination of both merge sort and insertion sort. Implementation of that will be covered in another article.

What is the most efficient sorting algorithm in Python? ›

The Merge Sort Algorithm in Python. Merge sort is a very efficient sorting algorithm. It's based on the divide-and-conquer approach, a powerful algorithmic technique used to solve complex problems. To properly understand divide and conquer, you should first understand the concept of recursion.

How to do sorting in Python? ›

The syntax of the sort() function in Python is as follows.
  1. Syntax: list_name.sort(key=…, reverse=…)
  2. Parameters:
  3. Return value: The sort() does not return anything but alters the original list according to the passed parameter.
Dec 18, 2023

How is Python sorted so fast? ›

Key Functions

The value of the key parameter should be a function (or other callable) that takes a single argument and returns a key to use for sorting purposes. This technique is fast because the key function is called exactly once for each input record.

Which algorithm is best for sorting? ›

Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.

What is the best sorting function in Python? ›

The easiest way to sort is with the sorted(list) function, which takes a list and returns a new list with those elements in sorted order. The original list is not changed. It's most common to pass a list into the sorted() function, but in fact it can take as input any sort of iterable collection. The older list.

What is the fastest sorting algorithm? ›

Quicksort is the fastest known comparison-based sorting algorithm when applied to large, unordered, sequences. It also has the advantage of being an in-place (or nearly in-place) sort.

Which is the most stable sorting algorithm? ›

Several common sorting algorithms are stable by nature, such as Merge Sort, Timsort, Counting Sort, Insertion Sort, and Bubble Sort. Others such as Quicksort, Heapsort and Selection Sort are unstable. We can modify unstable sorting algorithms to be stable.

What is the easiest sorting algorithm to understand? ›

Bubble sort is widely recognized as the simplest sorting algorithm out there. Its basic idea is to scan through an entire array and compare adjacent elements and swap them (if necessary) until the list is sorted.

What is the oldest sorting algorithm? ›

The first sorting algorithm that was actually used on a device was undoubtedly Radix sort . This sorting algorithm has been used since as early as 1887 to sort punch cards (see also IBM card sorter ).

Should I learn all sorting algorithms? ›

It's generally not super-important to learn a bunch of different sorts. Sorts are often used when teaching algorithms for the same reason that factorial is used when teaching recursion: it's something that you either know how to do or is easily explained, and the solution is easy to look at and see how it works.

What is the simplest sorting algorithm in Python? ›

The bubble, insertion and selection sort algorithms are one of the simplest algorithms for array sorting because they only require the knowledge of a list data structure and for loops.

What is the Python module for sorting? ›

The two built-in Python sort functions are list. sort() and sorted(). Both these have an optional parameter 'reverse' that accepts a Boolean value. Boolean value 'true' does the descending order and Boolean value 'false' does the ascending order.

What is the difference between sort and sorted in Python? ›

sort() will sort the list in-place, mutating its indexes and returning None , whereas sorted() will return a new sorted list leaving the original list unchanged. Another difference is that sorted() accepts any iterable while list. sort() is a method of the list class and can only be used with lists.

Does Python still use Timsort? ›

Timsort is a sorting algorithm developed by Tim Peters in 2002. It was originally developed for use in Python and is now the standard sorting algorithm that the Python standard library uses.

What is the sorting algorithm for selection sort in Python? ›

Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

What is the internal sorting algorithm in Python? ›

The Python way is a hybrid sorting algorithm which is derived from merge and insertion sort. For smaller runs (up to a minimum run size of 64) Timsort internally picks insertion sort, otherwise merge sort is being used. Its worst-case and average complexity is O(n log n), but the best-case performance is O(n).

What is the searching algorithm in Python? ›

Searching algorithms In Python. This involves looking for a specific element in a list or array of elements. It detects its presence and will return a True or false if present or absent respectively.


Top Articles
Latest Posts
Article information

Author: Manual Maggio

Last Updated:

Views: 6134

Rating: 4.9 / 5 (69 voted)

Reviews: 92% of readers found this page helpful

Author information

Name: Manual Maggio

Birthday: 1998-01-20

Address: 359 Kelvin Stream, Lake Eldonview, MT 33517-1242

Phone: +577037762465

Job: Product Hospitality Supervisor

Hobby: Gardening, Web surfing, Video gaming, Amateur radio, Flag Football, Reading, Table tennis

Introduction: My name is Manual Maggio, I am a thankful, tender, adventurous, delightful, fantastic, proud, graceful person who loves writing and wants to share my knowledge and understanding with you.