Searching and Sorting Algorithms in Python

Searching Algorithms

Searching algorithms play a vital role in the performance of any program or application. An application’s ability to respond quickly, being reliable, and showing stability depends upon the correct use of searching algorithms during its development.

Types of Searching Algorithms

There are numerous types of searching algorithms implemented in Python. Some of them are the following:

Membership Operators
Linear Search
Binary Search
Jump Search
Fibonacci Search
Exponential Search
Interpolation Search

Linear Search

In this type of search technique, the program searches for a specific element in the array and matches every element with the given one. On finding the element, the function provides its located position as the output. Otherwise, it returns a unique message or false flag as a result. The time complexity of Linear Search is O(n). Sample code of Linear Search algorithm is the following:

#Linear Search in Python

#function for search

def LinearSearch ( array, element ) :
                for i in range ( len ( array ) ):
                                if array [ i ] == element :
                                                return i
                return -1

#Testing code
array = [ ‘1’ , ‘2’, ‘3’, ‘4’, ‘5’ ]
element = ‘3’
print ( “ Given element is located on index “ + str ( LinearSearch ( array, element ) ) )

The output of the above program is the following:

Given element is located on index 2

Binary Search

Binary Search works on the principle of dividing the sorted array in half in every interval. If the searching element is precisely the middle element, the function returns its index. On the other hand, if the element that it has to search is less than the middle element of the array, the divided first half of the array is searched. But if the element is greater than the middle one, the algorithm searches the right half of the divided array. The algorithm repeats the above steps in each interval till it has found the element. Otherwise, it concludes that the element is not in the array. As this algorithm sorts the array along with searching, the time complexity of the algorithm is O (log n). Sample code of recursive Binary Search algorithm is the following:

#Binary Search in Python
def BinarySearch ( array , first, last, element ) :
                if first < = last :
                                middle = ( first + last )// 2
                                if array [ middle ] == element :
                                                return middle
                                elif array [ middle ] > element :
                                                retun BinarySearch ( array, first, middle -1, element )
                                else:
                                                return BinarySearch ( array, Middle + 1, last, element )
                else:
                                return -1
#Testing code
array [ 1, 2, 3, 4, 5 ]
 element = 3
print ( “ Given element is located on index “ , str ( BinarySearch ( array , 0, len (array) -1, element )

The output of the above code is the following:

Given element is located on index 2

Jump Search

Jump Search and Binary Search are similar in the sense of working with already sorted arrays. The primary purpose behind jump search is to minimize the number of searching elements than in the Linear Search. To achieve this goal, jump search works by jumping a few steps and skipping some elements to avoid searching all of the elements. The basic idea is to split the data of a sorted array into subsets of some elements. These elements are blocks. The algorithm finds the search key by comparing the search candidate in every block of elements. The assumption is that the search candidate is the highest value of a block in the sorted array. Following are 1 of the 3 things that can happen while comparing the search key to a search candidate:

The algorithm checks the subsequent block if the search candidate is lesser than the search key.
The algorithm performs a linear search on the current block if the search candidate is greater than the search key.
The algorithm returns the candidate if the search key is a match with the search candidate.

The most important thing here is to choose the correct size for the block. For this purpose, the algorithm chooses the size of a block by taking a square root of the array’s length. Therefore, choosing this size gives the best performance in most of the arrays. Following code shows the implementation of Jump Search:

import math
def jumpSearch( arr , k , s ):
           bs = math.sqrt(s)
           p = 0
           while arr[int(min(bs, s)-1)] < k:
                                    p = bs
                                    bs += math.sqrt(s)
                                    if p >= s:
                                                return -1
           while arr[int(p)] < k:
                                    p+= 1
                                    if p == min(bs, s):
                                               return -1
           if arr[int(p)] == k:
                                    return 
           return -1
# Testing Code
arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21,34, 55, 89, 144, 233, 377, 610 ]
k = 55
s = len(arr)
in = jumpSearch(arr, k, s)
print("Number" , k, "is at index" ,"%.0f"%in)

The output of the above code is :

Number 55 is at index 10

Sorting Algorithms

Sorting algorithms prove helpful in applications where desired results depend upon the integration of sorted data. It is likely easier to process sorted data instead of working with the random allocation of data. Visible patterns can be identified and used as desired after proper sorting of the given information. Therefore, developers use various sorting algorithms varying from the scenarios and the problems they need to solve.

Types of Sorting Algorithms

There are various sorting algorithms in Python programming. Some of them are the following:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Heap Sort
Quick Sort

Bubble Sort

The basic technique behind bubble sort is to compare adjacent elements of an array and swap them according to their order. It is a repeated algorithm to put the elements of the array in the desired order. The whole array is checked by comparing pairs of adjacent elements to swap if their order is wrong until no more swap is needed. The name bubble comes from the idea to put smaller elements on top of the array. The time complexity of this algorithm is O(n^2). It is also known as comparison sort. The sample code for comparison sort is the following:

#Bubble Sort in Python
def BubbleSort ( array )
                for i in range ( len ( array ) -1, 0, -1 )
                                for j in range ( i )
                                                if array [ j ] > array [ j+1 ]
                                                                temp = array [ j ]
                                                                array [ j ] = array [ j+1 ]
                                                                array [ j+1 ] = temp

#Test code
array = [ 15, 7, 10, 9, 5 ]
BubbleSort ( array )
print ( array )

The output of the above code is the following:

[ 5, 7, 9, 10, 15 ]

Selection Sort

In this technique, the function assumes that the leftmost part of the array is at its right position,i.e. sorted. It then searches the smallest element in the given array and swaps it by the first element of the array. Similarly, it searches the new smallest element from the rest of the array and swaps it by the second element of the array. This searching and swapping go on till the function has sorted the complete array. The time complexity of this algorithm is known to be O(n^2). Sample code for selection sort algorithm is the following:

#Selection sort in Python
def SelectionSort ( array, length )
                for j in range ( length ) :
                                index_1 = j
                                for k in range ( j+1, length ):
                                                if array [ k ] < array [ index_1 ]:
index_1 = k
                                ( array [ j ] , array [ index_1 ] ) = ( array [ index_1 ] , array [ j ] )
#Testing code
array = [ 15, 7, 10, 9, 5 ]
SelectionSort ( array, len ( array ) )
print ( array )

The output of the above program is the following:

[ 5, 7, 9, 10, 15 ]

Insertion Sort

Insertion sort algorithm works similarly with the concept of sorting cards in hands while playing rummy. There are sorted and unsorted parts of the array. The algorithm works with the unsorted parts of the array and helps in sorting them. Insertion sort works best for nearly sorted or small arrays. There is no need to know the entire array before sorting. At receiving the new element, the algorithm sorts the whole array without redoing the sort. The algorithm uses the following steps to perform the sorting in ascending order:

Perform iteration from array [1] to array[n] over the array.
Comparing the current element to its predecessor.
If the predecessor is greater than the key, the algorithm compares the key to the elements before. The algorithm moves the greater elements from one position up to make space for the swapping element.

Following is an implementation of the insertion sort code:

def insertionSort(array):
           for i in range(1, len(array)):
                                    k = array[i]
                                    l = i-1
                                    while l >= 0 and k < array[l] :
                                                           array[l + 1] = array[l]
                                                           l -= 1
                                    array[l + 1] = k
array = [12, 11, 13, 5, 6]
insertionSort(array)
for i in range(len(array)):
           print ("% d" % array[i])

The output of the above code is following:

5 6 11 12 13

Other useful articles: