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 x_{1}, x_{2}, x_{3},…, xn bubble sort is applied to sort the array ‘array’

- Start with the first element (index 0) Compare the first two elements x
_{1}and x_{2}in the list. - if x
_{1}> x_{2}, swap those elements - If x
_{1}< x_{2}, move and continue with next 2 elements. - Repeat step 1 until the whole array is sorted and no more swaps are possible.
- 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(n^{2}). 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 x_{1}, x_{2}, x_{3},…, x_{n}, selection sort is applied to sort the array ‘arr’

- Start with the first element (index 0) & set it to min_elem = 0 and search for the minimum element in the list.
- If the minimum value is found swap the first element with the minimum element in the list
- Increment the position of min_elem so that it points to the next element
- 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(n^{2}) as there are two nested loops.

**Insertion Sort**

Given an array with n elements with values or records x_{0}, x_{1}, x_{2}, x_{3}, …, x_{n}.

- Initially, x
_{0}is the only element in the sorted sublist and the leftmost element in the array - We start from the element x
_{1}& assign it as the key. Compare x_{1}with the elements in the sorted sub-list(initially x_{0}and x_{1}), 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) - 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
- 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(n^{2}).

Best Case Time Complexity: **Ω**(n).

**Merge Sort**

Given an unsorted array with n elements with values x_{1}, x_{2}, x_{3}, …, x_{n} and is divided into n sub-arrays. We implement 2 main functions divide & merge.

- Dividing the given array into multiple small arrays until we get a single atomic value.
- 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 x_{1}, x_{2}, x_{3}, …, x_{n}.

- Make the rightmost element of the array as the pivot.
- 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.

- 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.
- 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(n^{2}).

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

- Start from the first element of the array, and one by one compare the key with each element of the array
- If the key matches with any of the element, it returns the index of the corresponding element
- 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:

- Start by dividing the given array into two halves and then compare the middle element with x
- If x matches with the mid element, it returns the index of that middle element
- 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
- 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.