All Categories

Sorting and Searching Program in Python

Sorting is a technique by which we arrange the elements of a list or an array in a specified order. By default, the order is Ascending order. 

Searching is a technique of finding a particular element in a list

In our previous blog, we have learned about sorting and searching algorithms in detail along with all the sorting types and its working with examples. 

You can refer to the blog by the below link:

Introduction_to_Data_Structure

In this blog, we will be implementing programs for various sorting algorithms in Python. So let us start with Bubble sorting.

Bubble Sort

Given an array, ‘array’ of n elements with values or records x1, x2, x3,…, xn bubble sort is applied to sort the array ‘array’

  1. Start with the first element (index 0) Compare the first two elements x1 and x2 in the list.
  2. if x1 > x2, swap those elements
  3. If x1 < x2, move and continue with next 2 elements.
  4. Repeat step 1 until the whole array is sorted and no more swaps are possible.
  5. Return the final sorted list.

Program :

def bubbleSort(array):
    #the outer loop will traverse through all the element starting from the 0th index to n-1
    for i in range(0, len(array)-1):
        #the inner loop will traverse through all elements except the last element as it is sorted and is in a fixed position
        for j in range(0, len(array) - 1 - i):
            #if the current element is found greater than the next element
            if array[j] > array[j+1]:
                #then swap the position of the two elements
                array[j],array[j+1] = array[j+1], array[j]
                

#taking input from user separated by delimiter                
inp = input('Enter a list of numbers separated by commas: ').split(',')
#typecasting each value of the list into integer
array = [int(num) for num in inp]
bubbleSort(array)
print('The Sorted list is :',array)

Output:

Worst Case Time Complexity: O(n2). The worst-case occurs when the array is reverse sorted.

Best Case Time Complexity: O(n). The best-case occurs when the array is already sorted.

Selection Sort

Consider an Array ‘arr’  with n elements x1, x2, x3,…, xn, selection sort is applied to sort the array ‘arr’

  1. Start with the first element (index 0) & set it to min_elem = 0 and search for the minimum element in the list.
  2. If the minimum value is found swap the first element with the minimum element in the list 
  3. Increment the position of min_elem so that it points to the next element 
  4. Repeat the steps with new sublists until the list gets sorted.

Program

def selectionSort(arr):
    #the outer loop will traverse through all the element starting from the 0th index to n-1
    for i in range(0, len(arr)-1):
        #minimum value is initialized to i that everytime checks for the minimum value in the unsorted list of 'i'
        min_elem = i
        #the inner loop starts from i+1 as it iterates through the unsorted part of the list 
        for j in range(i+1, len(arr)):
            #we do comparison to find the minimum element in the remaining unsorted list
            if arr[j] < arr[min_elem]:
                #after finding the minimum value we assign it to the variable min_elem
                min_elem = j
        #swapping the minimum found element with the first element
        temp = arr[i]
        arr[i] = arr[min_elem]
        arr[min_elem] = temp
        
#taking input from user separated by delimiter                
inp = input('Enter a list of numbers separated by commas: ').split(',')
#typecasting each value of the list into integer
arr = [int(num) for num in inp]
selectionSort(arr)
print('The Sorted list is :',arr)

Output:

Worst-Case and Best-Case Time Complexity: O(n2) as there are two nested loops.

Insertion Sort

Given an array with n elements with values or records x0, x1, x2, x3, …, xn.

  1. Initially, x0 is the only element in the sorted sublist and the leftmost element in the array
  2. We start from the element x1 & assign it as the key. Compare x1 with the elements in the sorted sub-list(initially x0 and x1), and place it in the correct position(shift all the elements in the sorted sub-list that is greater than the
    value to be sorted)
  3. Then we make the third element as key and compare it with all the elements at the left and insert it to the right position
  4. Repeat steps 2 and 3 until the array is sorted.

Program

def insertionSort(ar):
    #the outer loop starts from 1st index as it will have at least 1 element to compare itself with
    for i in range(1, len(ar)):
        
        #making elements as key while iterating each element of i
        key = ar[i]
        #j is the element left to i
        j = i - 1
        #checking condition
        while j>=0 and key<ar[j]:
            ar[j+1] = ar[j]
            j = j - 1
        ar[j+1] = key
        
#taking input from user separated by delimiter                
inp = input('Enter a list of numbers separated by commas: ').split(',')
#typecasting each value of the list into integer
ar = [int(num) for num in inp]
insertionSort(ar)
print('The Sorted list is :',ar)

Output:

Worst Case Time Complexity: O(n2). 

Best Case Time Complexity: Ω(n). 

Merge Sort

Given an unsorted array with n elements with values x1, x2, x3, …, xn and is divided into n sub-arrays. We implement 2 main functions divide & merge.

  1. Dividing the given array into multiple small arrays until we get a single atomic value.
  2. Merge the smaller into a new list in sorted order.

Program:

def mergeSort(alist):

   print("Splitting ",alist)

   if len(alist)>1:
       mid = len(alist)//2
       lefthalf = alist[:mid]
       righthalf = alist[mid:]

       #recursion
       mergeSort(lefthalf)
       mergeSort(righthalf)

       i=0
       j=0
       k=0

       while i < len(lefthalf) and j < len(righthalf):
           if lefthalf[i] < righthalf[j]:
               alist[k]=lefthalf[i]
               i=i+1
           else:
               alist[k]=righthalf[j]
               j=j+1
           k=k+1

       while i < len(lefthalf):
           alist[k]=lefthalf[i]
           i=i+1
           k=k+1

       while j < len(righthalf):
           alist[k]=righthalf[j]
           j=j+1
           k=k+1

   print("Merging ",alist)

alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
mergeSort(alist)
print('Sorted list: ', end='')
print(alist)

Output:

Worst-Case and Best-Case Time Complexity: O(n log(n)) as merge sort always divides the array into two halves and take linear time to merge two halves.

Quick Sort

Given an array with n elements with values x1, x2, x3, …, xn

  1. Make the rightmost element of the array as the pivot. 
  2. Partitioning: Rearranging the array in such a way such that all the elements with a value less than the pivot come before the pivot and all the elements with value more than the pivot comes after it.

After this, the pivot comes to its correct final position.

  1. The elements at the left and right of the pivot are not sorted, hence we take these subarrays and repeat steps 1 and 2 until we get the sorted array.
  2. The approach used here is recursion at each split to get to the single-element array.

Program:

#function to implement partitioning where 'low' and 'high' are the starting and the end element of 'array' respectively
def partition(array, low, high):
    i = low - 1
    #pivot is the last element in the array
    pivot = array[high]
     
    for j in range(low, high):
        #comparing each element in the array with the pivot
        if array[j] <= pivot:
            #if condition is true increment the value of i by 1
            #And swap the element at current index of j to current index of i
            i = i+1
            array[i], array[j] = array[j], array[i]
    #after all the traversing has been done, replace the pivot value with the element present at current index of (i+1)
    array[i+1], array[high] = array[high], array[i+1]
    #returning pivot value
    return i+1

#function to do quick sort
def quickSort(array, low, high):
    #comparing if the value of low is smaller than high
    if low < high:
        #p is partitioning index, we'll perform partitioning until the array is sorted
        p = partition(array, low, high)
        #Separately sort elements before partition and after partition
        quickSort(array, low, p-1)
        quickSort(array, p+1, high)
        
#taking input from user separated by delimiter                
inp = input('Enter a list of numbers separated by commas: ').split(',')
n = len(inp)
#typecasting each value of the list into integer
array = [int(num) for num in inp]
quickSort(array, 0, n-1)
print('The Sorted list is :',array)

Output

Worst Case Time Complexity: O(n2). 

Best Case Time Complexity: O(n log(n)). 

Linear Search

For a given array[] with n elements, and x is the key element that has to be searched, we do the linear search

  1. Start from the first element of the array, and one by one compare the key with each element of the array
  2. If the key matches with any of the element, it returns the index of the corresponding element
  3. If no such element is found, it returns -1.

Program

def linearSearch(array, x):
    for i in range(0, len(array)):
        if array[i] == x:
            return i
    return -1

array = input('Enter the list of element').split(',')
arr=[int(num) for num in array]
x = int(input('Enter the element that needs to be searched'))
result = linearSearch(arr, x)
if result == -1:
    print('Element was not present in the list')
else:
    print('Element was found at the position',result)

Output:

Worst-Case Time Complexity: O(n). 

Best-Case Time Complexity: O(1)

Binary Search

For a given array[] with n elements, and x is the key element that has to be searched, we do the binary search:

  1. Start by dividing the given array into two halves and then compare the middle element with x
  2. If x matches with the mid element, it returns the index of that middle element
  3. Else if x is smaller than the middle element, it means it is present in the left subarray, we recur the function into the left half
  4. Else, it means x is present in the right subarray, we recur the function into the right half.

Program:

# Returns index of x in arr if present, else -1, array is the list of elements and x is the element to be searched
def binarySearch(array, f, l, x):
    #checking the base case
    if f <= l:
        #getting the middle element
        mid = (f + (l-f)//2)
        
        #checking if x is present in the middle index
        if array[mid] == x:
            return mid
        #checking if element is smaller than mid, then it is present in the left subarray
        if array[mid]>x:
            return binarySearch(array, f, mid-1, x)
        #if element is larger than mid, then it is present in the right subarray
        else:
            return binarySearch(array, mid+1, l, x)
    #if the element not at all present in the list
    return -1

arr = input('Enter the list of element ').split(',')
array=[int(num) for num in arr]
x = int(input('Enter the element that needs to be searched '))
result = binarySearch(array, 0, len(array)-1, x)
if result == -1:
    print('Element was not present in the list')
else:
   print('Element was found at the position',result)

Output:

Worst-Case Time Complexity: O(log n).

Best-Case Time Complexity: O(1)

This brings us to the end. For any query or suggestions drop us a comment below.

Keep visiting our website for more blogs on Data Science and Data Analytics.

Mitali Singh

Python|| Machine Learning|| Statistics|| Data Science

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Related Articles

Close
Close