Introduction to sorting and searching

Sorting and searching are two fundamental operations in computer science.

Sorting refers to the process of arranging a collection of items in a specific order, typically in ascending or descending order based on a certain criteria.

Searching, on the other hand, is the process of finding a specific item or value within a collection of items.

Sorting and searching operations goes hand in hand this is partly because it is far easier to locate a specific element when the dataset is sorted than when it is unsorted. Thus sorting greatly improves search efficiency and hence data retrieval.

Both sorting and searching algorithms are used widely in all sort of applications. Understanding them is a fundamental part of  programming and computer science in general.

In this article you will get a glimpse on the various sorting and searching algorithms without immersing into intricate implementation details.

Sorting algorithms

Sorting algorithms are used to arrange data in a specific order, usually from smallest to largest or vice versa. This makes it easier to search for specific items as well as  to perform other operations on the data.

Sorting algorithms can be broadly classified into two categories:

1. comparison-based sorting
2. non-comparison-based sorting.

Comparison-based sorting algorithms compare elements in a specific order and make decisions based on the result of the comparison. Examples of comparison-based sorting algorithms include

Non-comparison-based sorting algorithms do not rely on comparisons between elements. Instead, they use the existing order of the elements to sort them efficiently. The include:

Differences between comparison and non-comparison-based sorting algorithms

Builtin sorting Utilities

The builtin  sorted() function and the list.sort() method are some of the most used sorting utilities in Python.

Both sorted() and list.sort() are comparison based, they uses a hybrid of some of the comparison algorithms.

The sorted() function takes in an iterable whose elements are comparable as its arguments, It returns a list containing the elements in a sorted order.

items = (1, 0, 5, 3, 7, 6, 2, 4)

sorted_items = sorted(items)
print(sorted_items)
 Visualize 
copycopied!

Output:
[0, 1, 2, 3, 4, 5, 6, 7]
[Finished in 0.010559807997196913s]

In the above example, we used the sorted() function to create a sorted list of elements from a tuple.

The sorted() function works with any iterable such as sets, dictionaries, lists, e.t.c. 

The list.sort() method, is specially built for sorting lists in-place. This means that it sorts the elements on the original list by rearranging their positions, it does not create a new list.

items = [1, 0, 5, 3, 7, 6, 2, 4]

items.sort() #call the sort() method
print(items)
 Visualize 
copycopied!

Output:
[0, 1, 2, 3, 4, 5, 6, 7]
[Finished in 0.010391562711447477s]

As you can see above, after calling the sort() method, the original list is sorted.

Both sorted(), and list.sort() takes two optional arguments:

items = [1, 0, 5, 3, 7, 6, 2, 4]

items.sort(reverse = True) #call the sort() method
print(items)
 Visualize 
copycopied!

Output:
[7, 6, 5, 4, 3, 2, 1, 0]
[Finished in 0.009519766084849834s]

In the above example, the reverse parameter is set to True, the elements are therefore sorted in descending order.

Key functions are normally single-argument functions that gets called with each of the elements to be sorted. The results after applying the key function to each element are used rather than the actual elements. Consider the following example 

items = [-8, 5, 0, -6, 2, -4, 7, -1, 9, 3]

sorted_items = sorted(items, key = abs)
print(sorted_items)
 Visualize 
copycopied!

Output:
[0, -1, 2, 3, -4, 5, -6, 7, -8, 9]
[Finished in 0.010337885934859514s]

In the above example, the builtin abs() function is passed as the key parameter. This makes the elements to be sorted based on theirs absolute value rather than their numeric values.

Searching Algorithms

Searching algorithms are used to find a given item in a dataset. They can be categorized into two:

Linear search involves sequentially checking each element in a collection until the desired item is found or the end of the collection is reached. Binary search, on the other hand, is more efficient as it  divides the search space in half with each iteration, reducing the number of elements to search and thus improving the overall performance.