Bubble Sort and Selection Sort

Sorting is fundamental algorithm in computer programming. In every day problem, we need to sort things. It might be name sorting, number sorting, result sorting etc. So, to solve this problem we have multiple algorithms available. Here I am explaining two most commonly sorting algorithms. Which is 1.) Bubble sort and 2.) Selection Sort.

Let’s talk first about bubble sort. Which is comparatively “simpler” than selection sort.

In bubble sort, we compare adjacent elements and arrange the elements in certain order. So let’s say if we have to arrange an array of integer in ascending order. We’ll compare first two elements of array and write the smallest one at first position i.e; 0th index of array.

In best case, it’s complexity is 0(n) because it’s already sorted but anyway we have to traverse the list once. And in worst case it’s complexity is 0(n²) because array is completely in reverse order so we have to sort each element comparing with next element.

Now coming to Selection Sort, in section sort we pick the correct element in one scan and place that element at right position. So taking the same example as in bubble sort if we have to sort an array in ascending order we’ll compare the first element with remaining element of array and if any other element is smaller than first element we’ll swap both.

It’s complexity is 0(n²) in both case because even if the array is sorted we are comparing all elements with rest of the elements in array so it doesn’t matter whether that array is sorted or not. It’s complexity will always be the 0(n²).