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’
- Start with the first element (index 0) Compare the first two elements x1Â and x2Â in the list.
- if x1Â > x2, swap those elements
- If x1Â < x2, 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 :
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’
- 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
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.
- Initially, x0Â is the only element in the sorted sublist and the leftmost element in the array
- 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) - 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
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.
- 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:
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.
- 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:
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
- 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
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:
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.