Sorting Algorithms in Python

Sorting is a basic building block that many other algorithms are built upon. It’s related to several exciting ideas that you’ll see throughout your programming career. Understanding how sorting algorithms in Python work behind the scenes is a fundamental step toward implementing correct and efficient algorithms that solve real-world problems.

In this tutorial, you’ll learn:

• How different sorting algorithms in Python work and how they compare under different circumstances
• How Python’s built-in sort functionality works behind the scenes
• How different computer science concepts like recursion and divide and conquer apply to sorting
• How to measure the efficiency of an algorithm using Big O notation and Python’s timeit module

By the end of this tutorial, you’ll understand sorting algorithms from both a theoretical and a practical standpoint. More importantly, you’ll have a deeper understanding of different algorithm design techniques that you can apply to other areas of your work. Let’s get started!

Free Bonus: Click here to get access to a chapter from Python Tricks: The Book that shows you Python's best practices with simple examples you can apply instantly to write more beautiful + Pythonic code.

The Importance of Sorting Algorithms in Python

Sorting is one of the most thoroughly studied algorithms in computer science. There are dozens of different sorting implementations and applications that you can use to make your code more efficient and effective.

You can use sorting to solve a wide range of problems:

• Searching: Searching for an item on a list works much faster if the list is sorted.

• Selection: Selecting items from a list based on their relationship to the rest of the items is easier with sorted data. For example, finding the k^th-largest or smallest value, or finding the median value of the list, is much easier when the values are in ascending or descending order.

• Duplicates: Finding duplicate values on a list can be done very quickly when the list is sorted.

• Distribution: Analyzing the frequency distribution of items on a list is very fast if the list is sorted. For example, finding the element that appears most or least often is relatively straightforward with a sorted list.

From commercial applications to academic research and everywhere in between, there are countless ways you can use sorting to save yourself time and effort.

Python’s Built-In Sorting Algorithm

The Python language, like many other high-level programming languages, offers the ability to sort data out of the box using sorted(). Here’s an example of sorting an integer array:

>>>

>>> array = [8, 2, 6, 4, 5]
>>> sorted(array)
[2, 4, 5, 6, 8]

You can use sorted() to sort any list as long as the values inside are comparable.

Note: For a deeper dive into how Python’s built-in sorting functionality works, check out How to Use sorted() and sort() in Python and Sorting Data With Python.

The Significance of Time Complexity

This tutorial covers two different ways to measure the runtime of sorting algorithms:

1. For a practical point of view, you’ll measure the runtime of the implementations using the timeit module.
2. For a more theoretical perspective, you’ll measure the runtime complexity of the algorithms using Big O notation.

Timing Your Code

When comparing two sorting algorithms in Python, it’s always informative to look at how long each one takes to run. The specific time each algorithm takes will be partly determined by your hardware, but you can still use the proportional time between executions to help you decide which implementation is more time efficient.

In this section, you’ll focus on a practical way to measure the actual time it takes to run to your sorting algorithms using the timeit module. For more information on the different ways you can time the execution of code in Python, check out Python Timer Functions: Three Ways to Monitor Your Code.

Here’s a function you can use to time your algorithms:

 1 from random import randint
 2 from timeit import repeat
 3 
 4 def run_sorting_algorithm(algorithm, array):
 5     # Set up the context and prepare the call to the specified
 6     # algorithm using the supplied array. Only import the
 7     # algorithm function if it's not the built-in `sorted()`.
 8     setup_code = f"from __main__ import {algorithm}" \
 9         if algorithm != "sorted" else ""
10 
11     stmt = f"{algorithm}({array})"
12 
13     # Execute the code ten different times and return the time
14     # in seconds that each execution took
15     times = repeat(setup=setup_code, stmt=stmt, repeat=3, number=10)
16 
17     # Finally, display the name of the algorithm and the
18     # minimum time it took to run
19     print(f"Algorithm: {algorithm}. Minimum execution time: {min(times)}")

In this example, run_sorting_algorithm() receives the name of the algorithm and the input array that needs to be sorted. Here’s a line-by-line explanation of how it works:

• Line 8 imports the name of the algorithm using the magic of Python’s f-strings. This is so that timeit.repeat() knows where to call the algorithm from. Note that this is only necessary for the custom implementations used in this tutorial. If the algorithm specified is the built-in sorted(), then nothing will be imported.

• Line 11 prepares the call to the algorithm with the supplied array. This is the statement that will be executed and timed.

• Line 15 calls timeit.repeat() with the setup code and the statement. This will call the specified sorting algorithm ten times, returning the number of seconds each one of these executions took.

• Line 19 identifies the shortest time returned and prints it along with the name of the algorithm.

Read the full article at https://realpython.com/sorting-algorithms-python/ »

---

[ Improve Your Python With 🐍 Python Tricks 💌 – Get a short & sweet Python Trick delivered to your inbox every couple of days. >> Click here to learn more and see examples ]

from Real Python
read more