Category
>Machine Learning
>Python Programming

Implementing Bubble Sort And Merge Sort Using Python

Tanesh Balodi
Sep 11, 2021

Sorting Algorithms

Sorting algorithms are the techniques or ways by which we can re-arrange or sort a large number of elements, this rearrangement can be done from lowest to highest or from highest to lower.

The efficiency of any sorting algorithm depends upon the time taken by the algorithm for a large number of elements, in short, the time complexity and space complexity of an algorithm is of prime importance.

There are various types of sorting, some of them are mentioned below-:

Comparison Based Sorting: this type of sorting requires you to compare the two elements and place them according to the desired way. Bubble sort, insertion sort, merge sort, quick sort, heap sort are some examples of this type of sorting.

Non-comparison Based Sorting: This type of sorting algorithm doesn’t use comparison but use key values, examples are Radix sort and Bucket Sort

Stable Sorting: Sorting that preserves the order of duplicate elements in the sorted list. Tim sort, insertion sort, and merge sort are few examples

In-place Sorting: This type of sorting algorithm preserves the storage or space requirement in the sorted list as it was in the original list. Example: Bubble sort and Quicksort.

Out-place Sorting: This type of sorting algorithm requires extra space after sorting, usually this space is o(n) more than what we have in the original, Example: Merge Sort.

Internal Sorting: This type of algorithm doesn’t require external storage, all the data is in the RAM, this type of sorting algorithm is used when the size of the input is not large.

External Sorting: This type of sorting algorithm requires external storage, this type of algorithm is specially designed to handle large input, Merge sort is one of the examples of such a sorting algorithm.

(Must read: Machine Learning Algorithms)

Bubble Sort

Bubble sort is one of the most used sorting algorithms and is also known as sorting by the exchange. The idea or intuition behind this algorithm is fairly simple, it compares the adjacent element, if the adjacent element is out of order, then swap both elements, if it’s not out of order, then no changes are needed.

Let’s take an input list as, 50,40,30,20,10 where we want to sort the list in ascending order.

The above input is the worst-case scenario, which means that every element in the list needs to be sorted. This example is best to understand the working of the algorithm.

Let us compare the 1st and 2nd elements, i.e 50 and 40, 50 is greater than 40, therefore it is out of order and we need to swap them. After swapping these two elements, we will get-:

Now, we need to compare the 2nd and 3rd elements, i.e 50 and 30, 50 is greater than 30, therefore we are going to swap them. After swapping, the list will look like-:

Now, if we follow the above steps and compare them to either swap or let there be no change, then the other two iterations will look like:-

We can clearly observe that now 50 is in its right location.

After sorting our first element, the number of elements remaining is one less than the total number of elements, so if the total number of elements is ‘n’, then ‘n-1’ elements are left for sorting after one element is sorted.

Also, for the ‘n’ number of elements, the n-1 comparison is needed for one variable sorting.

(Recommended blog: Machine learning hackathons)

Let us break all the steps and try to understand the working in a way that we can implement it using code.

For the ‘n’ number of elements, we need to do ‘n-1’ comparisons, for the ‘n-1’ number of elements, we need to do the ‘n-2’ number of comparisons. So for the first pass, we have 5 elements, therefore 4 comparisons will happen, for the next pass, we have 4 elements and 3 comparisons will happen, and so on.

So, the first pass will sort the last element, the second pass will sort the second last element, and so on. Here we can conclude that for the second pass, we don’t need to consider the last element, as it is already sorted (This deduction is crucial to understand the code).

Bubble sort Python Implementation

def bSort(list1):

    n = len(list1)

  

    for i in range(n-1):

 

        # Last i elements are already in place

        for j in range(0, n-i-1):  

           

            if list1[j] > list1[j + 1] :

                list1[j], list1[j + 1] = list1[j + 1], list1[j]

 

list1 = input('enter the list of values to be sorted: ').split()

list1 = [int(x) for x in list1] #for every element in list1 we will call bubble sort

bSort(list1)

print(list1)

In the first loop, the range is till ‘n-1’ as we do not need to repeat the loop one more time, because in python, the index starts from ‘0’, therefore the last index will be ‘n-1’. Now, the ‘J' loop denotes that in each pass we are starting from the 0th index and executing the loop till ‘n-i-1’. Within the ‘jth’ loop, we are simply swapping if we find any element greater than their adjacent element.

Now the confusion behind the last value of the jth loop is common, i.e why did the loop executed till ‘n-i-1’, this is because for pass 1, our last value is of the index ‘n-2’, and for pass 2, our last value is of the index ‘n-3’, therefore, we execute the loop till ‘n-i-1’.

(Also read: Feature engineering in ML)

The complexity of Bubble Sort

The complexity of bubble sort depends upon its loop, the loop goes from 1+2+3+.......+ n-1, this will lead us to, n(n-1)/2, ignoring constants and dropping the lower order terms, we get the complexity of 0(n2). This is the best case, average case, and as well as the worst case of the bubble sort algorithm.

Merge Sort

Merge sort is a recursive algorithm that follows the divide and conquers way for sorting, in the recursive algorithm we call the function within the function. The divide and conquer method basically divides the problem into two sub-parts and solves them recursively.

Therefore, broadly there are three steps-:

Divide the problem into two sub-parts
Solve them Recursively
Merge the two sub-part using the merge algorithm

The example of merge sort-:

1 2 3 4 5 6 7 8

In order to apply merge sort to the above-unsorted list, we need to divide it in the sub-part, we can note the index from 1-8, therefore, the problem after dividing will look like-:

And

After solving the above two lists recursively, we will get-:

And

Now our last step is to merge them, while merging we have to compare each element of the left part with the right part, in this way, if any element in the left subpart is greater than the element in the right part, then the smaller element will be listed in the sorted list, otherwise no changes will be made.

For example, if we compare the first element of the left part, which is ‘3’, with the first element of the right part, which is ‘2’, 3 is greater than two, therefore we will put 2 in the sorted list. This way, the merging of two sorted lists will be done and the final list that we will get is-:

(Suggested blog: Underfitting and overfitting in ML)

Pseudo Code For Merge Sort

def Mergesortalgo(f,l):

    if f<l:

        mid = f+l/2

        Mergesortalgo(f,mid)

        Mergesortalgo(mid+1,l)

        Merge(l,mid,f)

The complexity of Merge Sort

Let’s discuss the time complexity of the merge sort algorithm-:

Dividing the array or list into two-part will take constant time, i.e o(1)
Recursively solving two sub-parts, each part will take T(n/2), which makes 2T(n/2) for both sub-parts
Merge algorithm will merge the two parts, i.e, o(n/2+n/2), which is equal to o(n)
We get the recurrence relation as 2T(n/2) + o(n), if we solve the recurrence relation using master’s theorem, we will get the complexity as Ө(nlogn)

Therefore, the complexity of the merge sort algorithm is Ө(nlogn)

Merge Sort Python Implementation

def mergesort(list1):

    if len(list1)>1:

        mid = len(list1)//2

        left = list1[:mid]

        right = list1[mid:]

        mergesort(left)

        mergesort(right)

        i=0

        j=0

        k=0

        while i<len(left) and j<len(right):

            if left[i]<right[j]:

                list1[k] = left[i]

                i=i+1

                k=k+1

            else:

                list1[k] = right[j]

                j = j+1

                k = k+1

        while i<len(left):  #if there is element left out in the left list

            list1[k] = left[i]

            i = i+1

            k = k+1

        while j<len(right): #if there is element left out in the right list

            list1[k] = right[j]

            j = j+1

            k = k+1

           

list1 = input('enter the list of values to be sorted: ').split()

list1 = [int(x) for x in list1] #for every element in list1 we will call merge sort

mergesort(list1)

print(list1)

The above Python code is pretty simple and everything goes step by step, at first, we have created a function name mergesort(), this function takes a list of unsorted elements as an input(as mentioned in the bottom part of the code), after defining a function, we have made an ‘if’ statement to check whether the length of the list is greater than 1 or not, because if a list contains only 1 element, then it is already sorted, we just have to return that element.

Afterward, we have three variables, mid, left, and right where ‘mid’ is used to find out the floor division of the list, basically we are splitting the list into two parts, ‘left’ is used for the left part of the list after the division, and ‘right’ is used for the right part of the list after the division. Two function calls are done after assigning the variables, one for the left part of the list, and another one for the right part.

Three variables i, j, and k are defined to and initialized to zero, the ‘while’ statement simply says that the loop will go on until the left part and right part has a length greater than 0,i.e while they have one or more than one element, the loop will go on.

We have an ‘if’ loop inside the ‘while’ loop that is comparing the element inside the left part and right part, and if the ‘ith’ element present in the left part of the list is less than the ‘jth’ element present on the right, we will simply put that element in the sorted list.

Conclusion

In this informative blog, we got to know about the working as well as the implementation of Bubble Sort and Merge Sort using python programming language, we also got to know about the complexity of merge sort and the complexity of bubble sort, this information will help students to grasp their command over data structure and their implementation using python.