So in our previous article, Understanding The Sorting Algorithms we read about different sorting algorithms and how differently they can be categorized. Now let's dive into one of those to understand it's working. 

In this article, we would be looking at how Selection Sort algorithm works. Selection Sort works by taking one position at hand and then comparing with the rest of the positions , swapping the values until we have a sorted dataset.

Now let's say we have 4 elements.

It will start with the 1st position or the 1st index.

It will compare the element at 1st position with the rest of the elements i.e.

Element at 1st position with the element at 2nd position

Element at 1st position with the element at 3rd position

Element at 1st position with the element at 4th position

Now, as per the sort we want (ascending or descending), it will place the minimum or maximum element from our list in the 2nd position.

So since we have the 1st position sorted, it will move towards 2nd position or 2nd index and repeat the same process until we have the data sorted.

Let's take some proper valid example and see how the sorting process will take place

Input dataset : [10, 4, 1, 2] for sort in ascending order

Process : 

1st pass for [10, 4, 1, 2] - Take index 0/1st position as our reference or selection point

Now compare 10[element at 1st position] with 4[element at 2nd position] , since 10 is greater than 4, swap both so now the dataset would be [4, 10, 1, 2]

Now compare 4[element at 1st position]  with 1[element at 3rd position] , since 4 is greater than 1, swap both so now the dataset would look like [1, 4, 10, 2]

Now compare 1[element at 1st position]  with 2[element at 4th position]. since 1 is less than 2 we would not swap it and the dataset would look like [1, 4, 10, 2]

So after 1st pass we have our dataset as [1, 4, 10, 2]

2nd pass for [1, 4, 10, 2] - Take index 1/2nd position as our reference or selection point

Now compare 4[element at 2nd position] with 10[element at 3rd position] , since 4 is less than 10,no swap happens so now the dataset would be [4, 10, 1, 2]

Now compare 4[element at 2nd position]  with 2[element at 4th position] , since 4 is greater than 2, swap both so now the dataset would look like [1, 2, 10, 4]

3rd pass for [1, 2, 10, 4] - Take index 2/3rd position as our reference or selection point

Now compare 10[element at 3rd position] with 4[element at 4th position] , since 10 is greater than 4, swap happens so now the dataset would be  [1, 2, 4, 10]

And we have the array sorted.

Algorithm :

1. Set the 0th index element as the minimum
2. Look for smallest element in the dataset
3. Swap the values such that the 0th index would have the minimum
4. Now consider 1st index as the minimum
5. Repeat the process until we have the dataset sorted.

Now let's see how the code for the same would look like

//input arr

int[] dataset = [10, 4, 2, 1]

//loop through the dataset

for(int index:0; index<dataset.length; index++){

  // int minIndex = index;

  for(int cIndex = index+1; cIndex<dataset.length; cIndex++){

     if(dataset[minIndex] > dataset[cIndex]) {

       minIndex = cIndex;

     }

  }

 //Swap if the min index and the current index are not same

 if(minIndex!=index){

  // Perform the swap

 }

}

To check different ways to swap data. Have a look at below article.

Swapping The Swap

Now if we see, the most iterations that would happen will be square of the dataset size. So if n is the dataset size then the most times an iteration would happen would be equal to n² . So from this example, we can say the worst case complexity for this sorting algorithm would be O(n²). 

Same would be the best case complexity as the array would have to be traversed irrespective of whether the initial array was sorted or not.
Right??

So, the best case complexity would be also O(n²). The average case would thus be O(n²).

And since we are talking about time complexity, let's talk about space complexity which will be O(1) since we are working directly on the input dataset itself. 

The advantage selection sort algorithm has is,

It's easier to understand and implement.

It's useful where we work with smaller datasets and also in places where we want the space complexity to be O(1).

The disadvantage

With complexity of O(n²), it takes a lot of processing that would have to be done for larger datasets.

It is not a stable algorithm which means the elements relative order does change. Proper example of this would be dataset [2, 2, 1].

Well that's some information about the selection sort algorithm. Until next time when we explore more such algorithms to work on! Keep the conversations with the code ongoing!!

Powered by Froala Editor