Comparing Bubble Sort with Selection Sort

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.

image by Wikimedia Foundations

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

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.

our new array after swapping the element looks like this 👇

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.

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.

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.

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.

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.

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.

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

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]
            }
        }
    }
}

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

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 👇

Step 2

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.

Step 3

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

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

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]]
}

Differences between Bubble sort and Selection sort

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

• java T point
• Khan Academy