# 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

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

Close