Sorting Algorithms and Searching algorithms like insertion sort, selection sort are essential to learning as a programmer because these form the base of any programmer. As a programmer, you have to deal with large amounts of data from time to time. This data needs to be sorted in a logical manner. You will also have to search through the data-set to find a unique item in the list.
Sorting and searching can be achieved in Python through the use of simple statements and algorithms. A sorting algorithm is used to rearrange a given list or an array of elements in a defined order, either increasing or decreasing. A searching algorithm is used to check the presence of an element in a list or array and displays the position of the element in the list or array or will return a False if it is non-existent in the list. In this article, we are discussing the basic Sorting Algorithms and Searching Algorithms in Python.
Sorting Algorithms
Let us begin with a sorting algorithm. We all know that python comes with an inbuilt function to sort an array of numbers.
a = [1,2,3,4,5,6,7] a.sort()
Python even makes it more interesting in that you can sort the numbers in a descending order.
a = [1,2,3,4,5,6,7] a.sort(reverse = True)
However, in this article, we shall discuss other ways of sorting arrays through custom algorithms. We shall look at three algorithms.
1. Insertion Sort
This sorting algorithm involves finding the right place for each element in the array. We begin by taking the first two elements and finding the position of each relative to the other. We then add the third element and compare it to the previous elements and find its position. Other elements are added gradually to the sorted list until the list is exhausted.
#Insert sort method.
def insertion_sort(unordered_list):
#Takes in the list to be sorted as parameter.
for i in range(1,len(unordered_list)):
#We start from one since the iteration occurs upto the lenght of the list.
j = i - 1
#j is the position of the current element.
#i is the position of the next element.
next_element = unordered_list[i]
while (unordered_list[j] > next_element) and (j >=0 ):
#We swap the elements if the current element is larger that the next element.
unordered_list[j+1] = unordered_list[j]
j = j - 1
#We move to the next element.
unordered_list[j+1] = next_element
#We print out the ordered_list but its name is still unordered_list
print(unordered_list)2. Bubble sort
This is quite similar to insertion sorting algorithm but differs in some ways. In this algorithm, we only compare adjacent elements and we then swap them if they are not in order. It is way much simpler to understand as compared to the previous algorithms.
#Bubble sort method.
def bubblesort(unordered_list):
#Takes in the list to be sorted as a parameter.
for num in range(len(unordered_list)-1,0,-1):
#We iterate over the positions in the list.
#We start with the last element and move leftwards, one step upto the first element.
for idx in range(num):
#We take a position 'idx' in the list to compare with the adjacent numbes.
if unordered_list[idx] > unordered_list[idx+1]:
#We swap the numbers if they're not in order.
temp = unordered_list[idx]
unordered_list[idx] = unordered_list[idx+1]
unordered_list[idx+1] = temp
#We print out the ordered list but retained its name which was 'unordered_lis'
print(unordered_list)3. Selection sort
This sorting algorithm is quite different from the previous ones. Here, we get the smallest element in a list and take it to a copy list, then repeat the process for the remaining elements until all of the elements have been sorted in the list.
#Selection sort method.
def selection_sort(unordered_list):
#The function takes the list to be sorted as a parameter.
for idx in range(len(unordered_list)):
#We take the position 'idx' for the lenght of the list.
min_idx = idx
#We assume the position of the smallest element is idx hence min_idx.
for j in range(idx+1, len(unordered_list)):
if unordered_list[min_idx] > unordered_list[j]:
#We check if it is indeed the smallest number and record its position
min_idx = j
#We swap the elements so that they can be in order
unordered_list[idx], unordered_list[min_idx] = unordered_list[min_idx], unordered_list[idx]
#We print out the sorted list but we retained its name as unordered_list
print(unordered_list)There are several ways of sorting using python algorithms. Each one of them is different from the other and they will vary with your level of skill in working with data structures. Some will be easier than others and some will run faster than others.
Searching algorithms
This involves looking for a specific element in a list or array of elements. It detects its presence and will return a True or false if present or absent respectively. It can also return the position of the element in the list if it is present and return an ‘absent statement’ if it’s absent.
There are two ways of searching through a list. We shall discuss them, how to code their algorithms and their advantages and disadvantages.
1. Linear searching
This is one of the searching algorithms that involves sequentially going through every element in the list until the element is located and its position is enumerated. This method might take a long time to run if the list or array is quite long and the element being searched is deep in the array. This is the disadvantage of this method. However, this method is quite handy as it can search in an unsorted list unlike the other method of searching that we will come to later.
#Linear search method.
def linear_search(values, searched):
#The function takes in only two parameters.
#'Searched' is the element being looked for.
#'Values' is the list in which the element is searched.
for i in range(0, len(values)):
#We iterate over every element in the list.
if (values[i] == searched):
#If we find the element, we return the position of the element in the list.
return "Element " + str(searched) + " is at " + str(i+1)
#If we don't find the element, we return an 'absent statement'
return "Element has not been found"2. Binary searching
This is a Searching algorithm that is quite different from its counterpart. It involves getting a sorted list and dividing it into two. Since it is sorted, the numbers are in order. We check if the number to be searched is larger or smaller than the middle number. If it is larger, we take the second half and if it is smaller we take the first half. We do this consequently until we find the element being searched. We then return its position in the list if it is present or return an ‘absent statement’ if it isn’t present in the list.
This algorithm will run faster than the linear search since it doesn’t iterate over every element in the list. However, this algorithm prerequisite is that the list should be sorted. You can sort the list inside the function but that will take up time too.
#Binary search method.
def binary_search(values, l, r, searched):
#The fucntion takes four parameters.
#'Values' is the list in which a value is being searched.
#'Searched' is the element being looked for.
#r is the lenght of the list.
#The lenght of the list keeps on changing every time we split the list
values.sort()
#We sort the list since the function needs the list to be sorted.
if r >= 1:
#For as long as the lenght of the list is not less than one.
mid = l + (r - 1) // 2
#The above line splits the list.
if values[mid] == searched:
#We check if the value is the element being searched for.
return "Element " + str(searched) + " is at " + str(mid+1)
elif values[mid] > searched:
#We check if the middle value is bigger than the element being searched.
return binary_search(values, l, mid-1, searched)
#We recall the function over the second half.
else:
#If the mid value is smaller that the element being searched
#We recall the fucntion over the first half.
return binary_search(values, mid+1, r, searched)
else:
#If we searched through the list after spliting it several times and failed to get the element, we return an 'absent statement'.
return "Element is not present in the array"Thank you for reading through my post. Please leave a comment below on any query you might have.
You can check other posts below:
Download Chrome Driver for selenium
Shutting down windows using voice command in python
Guess the number game in python
