Sorting and Searching inPython

If you were given a piece of paper with a list of 1,000 names, and you were asked to find some name, but this list was not in alphabetical order, it would be very frustrating, wouldn't it? Putting that list in order, although it takes a long time, makes finding names much easier. Thus, having things in order is a natural desire we human beings have, and searching this list would clearly take less effort than searching an unordered list. 

• Built-in Sorting Methods and Functions in Python


• Selection Sort Algorithm


• Linear Search Algorithm

Let's move to the computer world, where the lists one may be required to search are huge, and where performance might be affected even with fast computers. In this case, having a suitable sorting and searching algorithm would be a solution to such an issue. While sorting is about putting a list of values in order, searching is the process of finding the position of a value within a list.

To make it clear how critical this issue might be, let me show you what Donald Knuth, great American computer scientist, said:

Computer manufacturers of the 1960s estimated that more than 25 percent of the running time on their computers was spent on sorting, when all their customers were taken into account. In fact, there were many installations in which the task of sorting was responsible for more than half of the computing time. From these statistics, we may conclude that either (i) there are many important applications of sorting, or (ii) many people sort when they shouldn't, or (iii) inefficient sorting algorithms have been in common use.—The Art of Computer Programming Vol. 3: Sorting and Searching, page 3

In this tutorial, I will show you how to implement the selection sort algorithm and the linear search algorithm.

But before we start, if you just want to sort and search in your Python code, I'll show you the built-in methods to do that.

Built-in Sorting Methods and Functions in Python

There are a lot of sorting algorithms that you can create in Python. This is a great learning exercise, but for production applications, you should just stick with the built-in storing functions and methods in Python.

Python has a sorted() function that creates a new sorted list from an iterable. It also has a built-in list.sort() method which you can use to sort lists in-place. The sorting algorithm used by Python behind the scenes is called Timsort. It is a hybrid sorting algorithm based on insertion sort and merge sort while offering great performance for a lot of real-life situations. Here is an example of using both these functions and methods:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

There are a few things that you might notice in the above code. The function sorted() returned a new sorted list when we passed it marks_a. However, the original list remained unchanged. On the other hand, the sort() method returned None when we called it on marks_b. This is because it sorted the list in-place. We can see this when we print marks_b at the end.

You can pass a few arguments to modify the sorting behavior. For example, passing a function to the key argument will let you control what criteria is used to sort the elements. Similarly, you can set the value of reverse argument to True in order to reverse the order of elements. Here is an example:

words = ["School", "Ambulance", "Cat", "Banana", "Hotel", "Penguin", "Total", "Lot"]

list.sort(words)

# ['Ambulance', 'Banana', 'Cat', 'Hotel', 'Lot', 'Penguin', 'School', 'Total']
print(words)

list.sort(words, key = lambda word: len(word))

# ['Cat', 'Lot', 'Hotel', 'Total', 'Banana', 'School', 'Penguin', 'Ambulance']
print(words)

list.sort(words, key = lambda word: len(word), reverse=True)

# ['Ambulance', 'Penguin', 'Banana', 'School', 'Hotel', 'Total', 'Cat', 'Lot']
print(words)

Simply calling sort() without any arguments sorted our list of words in alphabetical order. In the second case, we used the key argument to tell Python that we want to use the length of words as our sorting criteria. Finally, we set the value of reverse to True in order to reverse the order of sorted words.

Selection Sort Algorithm

The Selection Sort algorithm is based on successive selection of minima or maxima values. Assume that we have a list which we want to sort in ascending order (from smaller to larger values). The smallest element will be at the beginning of the list, and the largest element will be at the end of the list.

Let's say that the original list looks as follows:

| 7 | 5 | 3.5 | 4 | 3.1 |

The first thing we do is find the minimum value in the list, which is in our case 3.1.

After finding the minimum value, swap that minimum value with the first element in the list. That is, swap 3.1 with 7. The list will now look as follows:

| 3.1 | 5 | 3.5 | 4 | 7 |

Now that we are certain that the first element is in the correct position in the list, we repeat the above step (finding the minimum value) starting from the second element in the list. We can find that the minimum value in the list (starting from the second element) is 3.5. We thus now swap 3.5 with 5. The list now becomes as follows:

| 3.1 | 3.5 | 5 | 4 | 7 |

At this point, we are certain that the first element and the second element are in their correct positions.

Now, we check the minimum value in the remainder of the list, that is starting from the third element 5. The minimum value in the remainder of the list is 4, and we now swap it with 5. The list thus becomes as follows:

| 3.1 | 3.5 | 4 | 5 | 7 |

So we are now certain that the first three elements are in the correct positions, and the process continues that way.

Let's see how the Selection Sort algorithm is implemented in Python (based on Isai Damier):

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k
                
        swap(aList, least, i)
        
def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

Let's test the algorithm by adding the following statements at the end of the above script:

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

In this case, you should get the following output:

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Linear Search Algorithm

The Linear Search algorithm is a simple algorithm, where each item in the list (starting from the first item) is investigated until the required item is found, or the end of the list is reached.

The Linear Search algorithm is implemented in Python as follows (based on Python School):

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

Let's test the code. Enter the following statement at the end of the Python script above:

bag = ['book','pencil','pen','note book','sharpener','rubber']
item = input('What item do you want to check for in the bag?')
itemFound = linearSearch(item,bag)
if itemFound:
    print('Yes, the item is in the bag')
else:
    print('Oops, your item seems not to be in the bag')

When you enter the input, make sure it is between single or double quotes (i.e. 'pencil'). If you input 'pencil', for instance, you should get the following output:

Yes, the item is in the bag

Whereas, if you enter 'ruler' as input, you will get the following output:

Oops, your item seems not to be in the bag

Conclusion

As we can see, Python proves itself again to be a programming language that makes it easy to program algorithmic concepts as we did here, dealing with sorting and searching algorithms.

It is important to note that there are other types of sorting and searching algorithms. If you want to delve deeper into such algorithms using Python, you can refer to the free Object-Oriented Programming in Python textbook.