DEV Community

blessing-michael
blessing-michael

Posted on • Originally published at Medium

Comparing Bubble Sort with Selection Sort

sorting gif
gif by giphy

Sorting means grouping or arranging a lot of objects into an appropriate order. You know that moment when you are looking for matching pair of socks to wear? That's sorting.
In this article, we will discuss the differences between bubble sort and selection sort.

Prerequisite

  • Big O Notation
  • Javascript for loop

Bubble Sort

The basic principle behind bubble sort is that it compares two elements, if the first element is bigger than the second element, we swap those two elements, or else we leave them and move to the next iteration. Take a look at this helpful visual representation of what happens while the algorithm is running.

bubble sort gif
image by Wikimedia Foundations

I will explain Bubble Sort in detail with the image below.

bubble sort des

The array in the image above is unsorted. It consists of 8 integers, i.e. 6,5,3,1,8,7,2,4.

The steps needed to sort the array are as follows:

PASS 1

Step 1: First we compare a[0] with a[1] element. The a[0] is greater than a[1], i.e. 6>5, so we swap the elements.

bubble sort img-1

our new array after swapping the element looks like this 👇

bubble sort img-1

Step 2:In this step, a[1] would be compared with a[2]. Notice that a[1] is greater than a[2], i.e. 6>3, and we swap the elements again.

bubble sort img-2

Step 3: The a[2] would be compared with a[3]. Notice that 6>1, i.e. a[2] is greater than a[3], so we swap the elements.

bubble sort img-3

Step 4: In this step, a[3] would be compared with a[4]. Notice that a[3] is less than a[4], so we leave them and move to the next iteration since they are in the correct order.

bubble sort img-4

Step 5: In this step, a[4] would be compared with a[5]. Notice that a[4] is greater than a[5], i.e. 8>7, so we swap the elements.

bubble sort img-5

Step 6: Let’s compare the a[5] with a[6]. Notice that a[5] is greater than a[6], i.e. 8>2, so we swap the elements.

bubble sort img-6

Step 7: In this step, a[6] would be compared with a[7]. Notice that a[6] is greater than a[7], so we swap the elements.

bubble sort img-7

At the end of pass 1, we got the array below.

bubble sort img-7

Pass 2: We have to start comparing the elements from the first position,i.e a[0] would be compared with a[1]. We repeat the process until the array is sorted.


Implementing Bubble Sort Algorithm

function bubbleSort(arr){
    for(let i=0; i< arr.length-1; i++){
        for(let j=0; j<arr.length-1; j++){
            if(arr[j]>arr[j+1]){
                arr[j],arr[j+1]=arr[j+1], arr[j]
            }
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Selection Sort

Selection sort continuously selects the next-smallest element and swaps it into position. Assuming we have an unsorted array, To sort this array in increasing order, during each iteration we have to select the smallest item from the unsorted partition and move it to the sorted partition. We will keep track of the current item and current minimum with red and green arrows.

Step 1

selection sort-1

The red arrow keeps track of the current minimum number, The green arrow represents our current item, as we iterate over the array, we find 1, we set this as our current minimum, and we swap 1 and 2. Our new array looks like the diagram below 👇

selection sort-2

Step 2

selection sort-3

In this step, we set 5 as our current minimum and current item using the green and red arrows. we scan the array again using the green arrow to check for a smaller number, Now we found 2, and we swap 5 and 2.

Our new array looks like the diagram below.

selection sort-4

Step 3

selection sort-5

In this step, we set our current minimum to 3 and current item to 3, as we scan through the array, Notice that there is no number smaller than 3 in the right part of the array. So No swapping occurs here.

Step 4

selection sort-6

In this Iteration, our current minimum is set to 4 and the current item to 4, as we scan through the array, Notice that there is no number smaller than 4 in the right part of the array. No swapping occurs here.

Step 5

selection sort-7

In this step, we set our current minimum to 5 and the current item to 5, There is no other element present in the right part of the array. So we return 5.

Implementing Selection Sort Algorithm

for(let i=0; i<arr.length; i++){
    let min=i;
    for(let i+1; j<arr.length; j++){
        if(arr[j]<arr[min]){
            min=j
        }
    }
   [ arr[i],arr[min]]=arr[min, arr[i]]
}

Enter fullscreen mode Exit fullscreen mode

Differences between Bubble sort and Selection sort

Bubble Sort Selection Sort
The time complexity is O(n) and O(n2) respectively. The time complexity in both best and worst cases is O(n 2).
It is not an efficient sorting technique when compare with selection sort. Selection sort is a better sorting technique when compared to bubble sort .
bubble sort functions by repeatedly exchanging the adjacent components if they are in the wrong order. selection sort sorts an array by continuously picking the minimum element from the unsorted part and inserting that at the beginning of the array.

Conclusion

In summary, the main difference between bubble sort and selection sort is that bubble sort compares two elements, and continually swaps the adjacent elements, if they are in the wrong order. In contrast, selection sort sorts an array by repeatedly finding the minimum element from the unsorted part and inserting that at the beginning of the array.

References

Top comments (0)