position: fixed; top: auto !important; margin-left: 112px;

Selection Sort

Selection Sort is the most intuitive sorting algorithm and is known for its simplicity. The main idea of Selection sort is to divide the input list of elements into two sub-lists:

  • All the elements in the first sub-list are already sorted and it is built from left to right.

  • The second sub-list contains the remaining unsorted elements.

Initially, the first sub-list is empty and the second sub-list is the entire input list. In each iteration, the algorithm builds the first sub-list by finding the smallest element in the second (unsorted) sub-list and exchanging it with the leftmost unsorted element present at the end of the first sub-list and then moving the boundary of the first sub-list by one element to the right.

Selection Sort Basics

Let's see this step by step. Suppose you want to sort a list of elements in the ascending order using Selection Sort. The steps that you need to follow are enumerated below:

  1. Scan through the entire list of inputs (from left to right) and find the smallest element present in the list.

  2. Exchange (swap) it with the element present at the first position in the list.

  3. Again scan through the entire list of inputs (from left to right, except the first position as it already has the smallest element) and find the smallest element present in the sub-list.

  4. Exchange (swap) it with the element present at the second position in the list. As you would have guessed, the smallest and the second smallest elements are present at the first and second position respectively.

  5. Continue the above steps until all the elements in the list are in ascending order.

Now let's see a working example of selection sorting by sorting an array {4,3,2,1} in the ascending order using selection sort.

The color encoding that is being followed below is that the smallest element in the list is shown in red, the number with which the smallest element will be exchanged (swapped) is shown in green and the sorted elements are shown in blue.

Iteration 1:

The smallest element in the list is 1. Swap it with the element present at the first position.



After swapping the elements, the array will look like this:



Iteration 2:

The second smallest element in the list is 2. Swap it with the element present at the second position.



After swapping the elements, the array will look like this:



Iteration 3:

The third smallest element in the list is 3.



Since 3 is already present at its place there is no need to swap and hence the array remains unchanged. So at the end of the third iteration, our array will be:



Now 4 is the only unprocessed element left in the list but as there are no elements to swap, the algorithm will terminate. The final sorted array will look like this:



Observations:

After seeing the working example of how Selection Sort works, let's make some observations from it:

  • The total number of iterations required to sort this array of size 4 is 3. In general, N − 1 iterations are required to sort the array of size N using Selection Sort.

  • In each iteration, we did swapping only once. In general, the total number of swaps required is equal to the total number of iterations. Swapping is done in constant time so the total running time of swap operation is Θ(N).

  • So we can say that to perform Selection Sort on an array of size N, asymptotically Θ(N) iterations are required and Θ(N) swaps are required with constant running time for each swap.

  • In each iteration, we find the smallest element by scanning through the entire sub-list of the unsorted array. In the first iteration, we scanned through 4 elements to find the smallest element. Similarly, in the second and third iteration, we scanned 3 and 2 elements respectively. In general, in the first iteration, we find the smallest element by scanning the array of N elements, in the second iteration, by scanning the array of N − 1 elements and so on. So the total running time of finding the smallest element will be N + (N − 1) + (N − 2) + ··· + 2 which is asymptotically equal to Θ(n2).

  • Adding up the running times of swap operation and the time complexity of finding the smallest element, the asymptotic time complexity of Selection Sort is Θ(n2).

Solve the Quiz of Article

1) In the above tutorial on Selection Sort, observe that the input to the algorithm was already sorted but in descending order. Keeping everything same, what do you think the time complexity of the algorithm will be Θ(n2) when input to the algorithm is the array which is already sorted in the ascending order?
Yes
No

2) Suppose we modify the algorithm such that it will stop iterating through the array if it finds no swap operation is performed in the current pass? What do you think the time complexity of this modified algorithm will be Θ(n2) when the input to the algorithm is the array which is already sorted in the ascending order?
Yes
No


Previous Next Article







codzify.com


Largest collection of up-to-date tutorials to learn programming languages. We are focused on easy learning. Massive collection of interview questions one may need for preparation.

Social Profile


Linkedin
Twitter
Facebook

Copyright 2018. All rights reserved.