Sorting and Searching in Python

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 any order (e.g. alphabetical order), it would be very frustrating, wouldn't it? Putting that list in order, although it takes a long time, makes finding the name 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.

Let's move to the computer world, where the lists one may be required to search are very 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, an American computer scientist, mathematician, and professor emeritus at Stanford University mentioned in The Art of Computer Programming, vol.3, Sorting and Searching, page 3:

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.

In this tutorial, I will specifically describe the Selection Sort algorithm (sorting) and the Linear Search algorithm (searching).

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

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 this page.

by A. Ahmed via Envato Tuts+ Code