Sorting Algorithms

7 min readJan 1, 2021

Bubble Sort

It is a sorting technique which requires swapping. As the name suggests as the bubble keep rising up in the water similarly the elements which are smaller keep moving leftwards.

**Comparison between bubbles in sea and numbers in array**

After each iteration/ pass you will get an element which is largest at the end from the unsorted part of the array. So basically we are getting a sorted array from back side of the array.

**Intermediate state during bubble sort**

ALGORITHM

You will start from the first element in the array i.e. index = 0
You will keep on swapping until that element is smaller than its next element.
After iterating through all the elements (from index = 0 to index = n — 1)of array once, in this pass you will end up getting the largest element from the unsorted part of the array.
Now the next pass will start from index = 0 and will go up to index = n — 2)as we have already have the element on the n — 1th index at its correct position so no need to disturb that.
Repeat these passes by reducing the size of the array by taking in account only elements from index = 0 to index = n — i — 1 where i goes from 0 to n — 1
At the end you will get a sorted array.

Let’s take one example

4 5 2 1 3

I PASS (array to be considered -> 4 5 2 1 3)

4 5 2 1 3

4 2 5 1 3

4 2 1 5 3

4 2 1 3 5

II PASS (array to be considered -> 4 2 1 3)

2 4 1 3 5

2 1 4 3 5

2 1 3 4 5

II PASS (array to be considered -> 2 1 3)

1 2 3 4 5

1 2 3 4 5

III PASS (array to be considered -> 1 2)

1 2 3 4 5

IV PASS (array to be considered -> 1)

1 2 3 4 5

As you can see in the above example even though we got the sorted array in the II pass itself but still we are moving forward and iterating over the next passes, which is just wastage of time.

Even when we get a sorted array we try all passes although those passes will not change the order as the array was already sorted so to optimize our algorithm what we can do is that we can have a flag for stopping the algorithm when there are no changes even after a particular pass then it directly means that we have got our desired output and now we can stop.

Time complexity

Time complexity of bubble sort is O(n²).

As because for each element in the array we are traversing n — i — 1 times where i denotes the index.

For element at index 0 we will traverse n — 1 times

For element at index 1 we will traverse n — 2 times

For element at index 2 we will traverse n — 3 times

For element at index 3 we will traverse n — 4 times and so on…

Thus summation of n — 1 + n — 2 + n — 3 ……..1 = O(n²)

Is bubble sort stable?

A sorting algorithm is said to be stable when ordering of the elements having same value but present at different indexes remains same after sorting.

Yes bubble sort is stable.

We will understand this with the help of one example.

As you can see the ordering(of element 2) remains same even after the sorting by bubble sort.

Is Bubble sort in place algorithm?

In place algorithm are those which doesn’t take any extra space other than required by the input.

Yes Bubble sort is in place algorithm.

Bubble sort doesn’t require any extra space as we are doing swapping in the input array itself so algorithm doesn’t uses any extra space.

Selection sort

As the name suggests we are selecting the most appropriate element for the from the unsorted part of the array and putting it in the sorted part of the array. My the word “most appropriate” I mean to say that if we are sorting in ascending order then the smallest element in our consideration part of the array(unsorted part of the array) and if we are sorting in descending order then that is the largest element from the unsorted part of the array.

After each pass we get one new element in the sorted part of the array.

**Intermediate state during selection sort**

ALGORITHM

First compare the element at index = 0 with the remaining array(unsorted part of the array) starting from index + 1 to n — 1
We keep traversing the loop from j = index + 1 to n — 1 and keep updating our min index found so far.
Then we swap the element at index and at min index found after the traversal in the unsorted part.
Now our unsorted array is from 1 to n — 1 because after each pass we are adding one element to our sorted array that is forming from the left side of the array.
Then we repeat this process and get a sorted array

Time complexity

Time complexity of selection sort is O(n²).

As for each element we are traversing the array n — i — 1 times where i = index of the element which ranges from 0 to n — 2

n — 1 + n — 2 + n - 3 ……………….0 = O(n²)

Is selection sort stable?

A sorting algorithm is said to be stable when ordering of the elements having same value but present at different indexes remains same after sorting.

Yes selection sort is not stable.

We will understand this with the help of one example.

As you can see ordering of the element 3 has been changed.

Is selection sort in place algorithm?

In place algorithm are those which doesn’t take any extra space other than required by the input.

Selection sort is in place algorithm

Selection sort doesn’t require any extra space as we are doing swapping in the input array itself so algorithm doesn’t uses any extra space.

Insertion sort

Selection sort was not in place algorithm so as to make it in place we make some changes to selection sort algorithm and the changed selection sort which is in place is called as Insertion sort.

So basically in insertion sort we pick the element from the unsorted part insert the element in this correct position in the sorted part of the array.

**Intermediate state during insertion sort**

It is very similar to the way you sort the playing cards in your hand.

ALGORITHM

We traverse the array from start to end.
We compare the key(current element) from the elements which are on the left side of that element.
Loop until you reach the start or the element is no longer greater than the key, you keep moving the elements one position ahead(on the right side) so as to make place for the key to be placed at its correct position. By this step we are able to place the key to its correct position.