Searching and Sorting Algorithms in Python

Oct 01, 2019
hackajob Staff

There’s a common joke that software engineers always use the word ‘algorithm’ when they’ve done something they can’t explain. Although it has a pretty simple meaning, such is the mystic associated with the term. A formula for problem-solving based on performing specific and sequential actions, an algorithm is essentially a recipe.

Search and sort algorithms are a good place to start when practicing your skills and problem-solving prowess. With this in mind, we’ve compiled a list of some of the common 'search' and 'sort' algorithms that can be executed using python.

As the name suggests, ‘linear search’ checks items in a list sequentially from one end to the other, as per the example below:

In this code, we iterate over a list called ‘items’ in order to check whether an item at ‘index i’ is equal to the item we are searching for. The average complexity of this algorithm is O(n).

We recommend you try implementing this algorithm with a ‘while loop’ to see how well you understand the example above. If you’d like to see more Pythonic code, you can execute a linear search as per the next example below. The index method can be called on lists in Python to check whether an item is in a list, using the linear search algorithm.

The ‘binary search’ algorithm works by splitting a list into two, and then checks on which half the item being searched for can’t lie. The process of splitting is repeated on the half where the item can be until it’s found, or you have an empty list. Note: the first step in this algorithm is sorting the list. In addition, the algorithm’s complexity is O(log n). See below for an example of this algorithm applied in Python:

Just to clarify, Python has an inbuilt module called ‘statistics’ that has methods for calculating measures of central tendency such as median. The use of ‘median_low’ and ‘median_high’ is recommended for lists with an even number of items, because calling ‘median’ returns the average of the two mid values.

Additionally, the ‘print’ statement after the ‘while’ statement is not necessary, but it helps by showing you how many times the loop was repeated before your item was found. For an example, see the below:

Merge Sort

The ‘merge sort’ algorithm works by dividing the primary list into smaller lists containing only one element. The smaller lists are then merged as they are sorted until they create one list. The complexity of this algorithm is O(n log n).

Below is an example of merge sort implemented using Python:

The print statement at the end of the function helps us see what is happening in the background:

Quick Sort

The ‘quick sort’ algorithm is more efficient than the ‘merge sort’ algorithm. It has an average complexity of O(n log n), although in some rare cases it can go as high as O(n2).

This algorithm works by getting a pivot value from which items in a list are placed to the right if found to be ‘greater than’ or to the left if found to be ‘less than’. A pivot value is then derived for items on both sides, which are commonly placed in different lists. The process is then repeated until sorting is complete. Note: this sorting algorithm also works for comparable items, including ‘integers’. Below, we’ve created an example implementation of a ‘quick sort’ algorithm using Python:

The ‘items’ list contains 250 elements. We recommend testing your implementation of both ‘sort’ and ‘search’ algorithms using different list sizes, so you can be sure that there are no recursion errors as the number of items goes up.

Ultimately, although algorithms are based on sequential and specific steps, this article shows how they can be implemented differently in code. For example, some people will opt for recursion and others for iteration. Go ahead and try implementing these algorithms differently - Have fun 😀

Like what you’ve read? Make sure to check out our blog for more!