Algorithms are commonly taught in Computer Science, Software Engineering subjects at your Bachelors or Masters. Some find it difficult to understand due to memorizing them without practically going through those algorithms. There are many sorting algorithms present today. I’ll be going through some of the commonly taught algorithms in Computer Science / Software Engineering.
It’s a simple algorithm starting from the L.H.S (Left-hand Side) and repeatedly compares the adjacent values and keep swapping (bubbling) the larger ones to the R.H.S(Right Hand Side). Which can be represented in the following repetitions.
|First Step||[ 4 0 3 1 7 ] –> [ 0 4 3 1 7 ], In here Bubble sort compares the first two values and swaps 5 with 1.(The largest one to the left).|
|Second Step||It continues the cycle with the second value by comparing the third [ 0 4 3 1 7 ] –> [ 0 3 4 1 7 ], and Swap since 4 is greater than 3.|
|Third Step||Again it compares the third with fourth elements [ 0 3 4 1 7 ] –> [ 0 3 1 4 7 ], Swap 4 with 1, since 4 is greater than 1.|
|Fourth Step||It compares the fourth with fifth [ 0 3 1 4 7 ] –> [ 0 3 1 4 7 ] and the value 4 is less than 7, therefore the value will not get swapped.|
It continues the steps to the same steps to swap the values as shown in cycle one.
|First Step||[ 0 3 1 4 7 ] –> [ 0 3 1 4 7 ]|
|Second Step||[ 0 3 1 4 7 ] –> [ 0 1 3 4 7 ], It will Swap 3 with 1 due to 3 is greater than 1.|
|Third Step||[ 0 1 3 4 7 ] –> [ 0 1 3 4 7 ]|
|Fourth Step||[ 0 1 3 4 7 ] –> [ 0 1 3 4 7 ]|
In the third cycle, it checks whether there is a necessity to swap any elements. If there is no swapping needed the algorithm will stop in this phase.
|First Step||[ 0 1 3 47 ] –> [ 0 1 3 47 ]|
|Second Step||[ 0 1 3 4 7 ] –> [ 0 1 3 4 7 ]|
|Third Step||[ 0 1 3 4 7 ] –> [ 0 1 3 4 7 ]|
|Fourth Step||[ 0 1 3 4 7 ] –> [ 0 1 3 4 7 ]|
It can be represented in a Python programming language as below.
# Python program to implement bubbleSort# BH# Array input to swaparr = [4 , 0 , 3 , 1 , 7]def bubbleSort(arr):n = len(arr)# Going through all array elementsfor x in range(n):# Last x elements are already in placefor y in range(0, n-x-1):# going through the array from 0 to n-x-1# Swap if the element found is greater than the next elementif arr[y] > arr[y+1] : arr[y], arr[y+1] = arr[y+1], arr[y]bubbleSort(arr)print ("Sorted elements are :")for x in range(len(arr)): print ("%d" %arr[x]),
Sorted elements are :01347
It’ll go through all the elements and find the smallest one then It’ll Swap the element into that position as the first item. It’ll continue to repeat the selection sort on the remaining items (N – 1).
Finding the smallest value from the Array and place it at the beginning
|First Step||[ 2 4 1 7 9 ] -> [ 1 4 2 9 7 3 ]|
|Second Step||[ 1 [ 4 2 7 9 ] ] -> [ 1 2 4 7 9 ]|
|Third Step||[ 1 2 [ 4 7 9 ] ] -> [ 1 2 4 7 9 ]|
|Fourth Step||[ 1 2 4 [ 7 9 ] ] -> [ 1 2 4 7 9 ]|
# Implementing Selection Sort in Python# BHimport sysSort_Array = [ 2, 4, 1, 7, 9]# Going through all array elementsfor x in range(len(Sort_Array)):# Find the minimum element in remaining unsorted arraymin_idx = xfor z in range(x+1, len(Sort_Array)):if Sort_Array[min_idx] > Sort_Array[z]:min_idx = z# Swap minimum element with the first elementSort_Array[x], Sort_Array[min_idx] = Sort_Array[min_idx], Sort_Array[x]# Driver code to test aboveprint ("Sorted array : ")for x in range(len(Sort_Array)):print("%d" %Sort_Array[x]),
Sorted array :12479
Insertion sort is based on the concept where in each iteration one element is taken to find it’s relevant position to where it beleongs in a sorted array.
It is less efficient in terms of larger array elements comparing to other sorting algorithms like heapsort, mergesort or quicksort.
By each iteration, it grows the sorted array and it compares the element with the largest element in the sorted array. If the current element is greater in value then it leaves the current element and moves to the next iteration and then it checks the element, If it’s less than the sorted array then it moves to the relevant position. This is done by shifting the larger elements than the current element in the sorted array. This process is repeated until all elements are sorted.
# Implementing Insertion Sort in Python# BHnumber_array = [5,7,3,10,2,8]def insertionSort(number_array):# Going through 1 to length of arrayfor x in range(1, len(number_array)):key = number_array[x]# Move elements of Array that are greater than key to one position ahead of their current positionno = x-1while no >= 0 and key < number_array[no] :number_array[no + 1] = number_array[no]no -= 1number_array[no + 1] = key# Printing the sorted arrayprint ("Sorted array : ")insertionSort(number_array)for y in range(len(number_array)):print ("% d" % number_array[y])
Sorted array :2357810
Quicksort picks an element as Pivot and divides the given values (array) around the picked pivot. Quick Sort is similar to Merge Sort and it’s a Divide and Conquer algorithm.
QuickSort helps to lessen the space complexity and removes the use of additional array which is used in Merge Sort. In Most cases selecting a pivot in an array improve the time complexity. There are many ways to pick a Pivot element.
How to Implement Quick sort?
These are the steps to implement a quicksort algorithm.
- Step 1: I have selected the pivot as the last index of the array after selecting the pivot, We have to divide the array using Partitioning.
- Step 2: Quick Sort uses Partitioning to divide the array into two subarrays, but when it comes to partitioning, the elements which are smaller than the pivot will be on the left-hand side of the pivot and the elements which are greater than the pivot will be on the right-hand side of it And the pivot element will be at its final sorted position.
- Step 3: The array elements which are at the left-hand side and right-hand side may not be sorted.
- Step 4: Then the sub-arrays with the elements on the left-hand side of pivot and elements on the right-hand side of pivot will be portioned by choosing a pivot in the subarrays.
It can be represented in a Python program as below.
# Implementing Quick Sort in Python# BHquicksort_array = [40,33,3,11,50,48]def partition(quicksort_array,starting_index,ending_index):i = ( starting_index-1 ) # index of smaller elementpivot = quicksort_array[ending_index] # pivotfor j in range(starting_index , ending_index):# If current element is smaller than the pivotif quicksort_array[j] < pivot:# incrementing the smaller elementi = i+1quicksort_array[i],quicksort_array[j] = quicksort_array[j],quicksort_array[i]quicksort_array[i+1],quicksort_array[ending_index] = quicksort_array[ending_index],quicksort_array[i+1]return ( i+1 )# Quick sort Functiondef quickSort(quicksort_array,starting_index,ending_index):if starting_index < ending_index:# partitioning index variable is pipi = partition(quicksort_array,starting_index,ending_index)# Separately sort elements before partition and after partitionquickSort(quicksort_array, starting_index, pi-1)quickSort(quicksort_array, pi+1, ending_index)quickSort(quicksort_array,0,len(quicksort_array) -1)# Printing the sorted arrayprint ("Sorted array :")for i in range(len(quicksort_array) ):print ("%d" %quicksort_array[i])
Sorted array :31133404850
Merge Sort is like Quick Sort where It uses Divide and Conquer algorithm strategy. It breaks the input array into two halves and then runs the algorithm for the two halves then merges the sorted two halves.
While comparing two halves for merging, the first element of both lists is taken into consideration. While sorting in the correct order, The lower value element becomes a new element of the sorted list. This method is repeated until both the smaller halves are empty and the new combined subarrays comprise all the elements of both the subarrays.
# Python program to implement MergeSort# BHmergeArray = [56,21,7,54,40,20]def mergeSort(mergeArray):if len(mergeArray) > 1:mid = len(mergeArray) // 2before_left = mergeArray[:mid]before_right = mergeArray[mid:]# Recursive call on each halfmergeSort(before_left)mergeSort(before_right)# Two iterators for going through the two halvesi = 0j = 0# Iterator for the main listk = 0while i < len(before_left) and j < len(before_right):if before_left[i] < before_right[j]:# The value from the half has been usedmergeArray[k] = before_left[i]# Move the iterator forwardi += 1else:mergeArray[k] = before_right[j]j += 1# Move to the next slotk += 1# For all the remaining valueswhile i < len(before_left):mergeArray[k] = before_left[i]i += 1k += 1while j < len(before_right):mergeArray[k]=before_right[j]j += 1k += 1print ("Array Before Sorting : ", *mergeArray)mergeSort(mergeArray)print ("Array After Sorting : ", *mergeArray)
Array Before Sorting : 56 21 7 54 40 20Array After Sorting : 7 20 21 40 54 56
- How to install WordPress with Nginx on Ubuntu 18.04
- How to create a new user & configure a firewall on Ubuntu 18.04
- Installing Nginx, PHP, MySQL and PHPMyAdmin on Ubuntu 18.04
- Predicting per capita income of the US using linear regression in Python