Selection Sort

 

Suppose we have an array with different numbers. For sorting it in an ascending order, selection sorting will be applied on it in the following manner. We find the smallest number in the array and bring it to the position 1. We do the same process with the remaining part of the array and bring the smallest number among the remaining array to the next position. This process continues till the time all the positions of the array are filled with the elements. Thus the main idea of selection sort is that

• find the smallest element

• put it in the first position

• find the next smallest element in the remaining elements

• put it in the second position

• …

• And so on, until we get to the end of the array

Let’s understand this algorithm by considering an example with the help of figures.

Consider an array that has four numbers i.e. 19, 5, 7 and 12 respectively. Now we want to sort this array in ascending order. To sort the array, selection algorithm will be applied on it.

The above pictorial representation explains the selection sort. It describes that at the start, we begin the search for the smallest number from the first position of the array i.e. from the index zero. We find that 5 is the smallest number and bring it to the first position i.e. index 0. Later, number 19 is put at the position that was occupied by number 5. Thus in a sense, we swap these numbers. Now 5, the smallest number in the array, has come at its final position i.e. index 0.

As index 0 has the proper number, so we start our search from position 2 i.e. index 1. Now we look at the remaining elements 19, 7, 12 and find the smallest number among them. Here 7 is the smallest so we change its position with 19 to bring 7 at its position. Thus 5 and 7 have come at their final positions. Now there are two elements are left behind i.e. 12 and 19. We search the smallest among these and find that 12 is the smallest. So we swap it with 19 to bring it at index 2 i.e. its final position. Now there is last element remaining and obviously it is at its position as there is no element to compare with it. The array is now in the sorted form with ascending numbers.

The point to remember in the selection search is that at the beginning, we start search for the smallest number from index 0 (i.e. first position). After it we start search from the index 1 (i.e. position 2). After each search one number gets its final position so we start the next search from the next position to it. Thus we do the multiple passes of the array to sort it. First, we pass through the n elements of the array and search the n-1 elements and then n-2. Thus at last, we come to the single and last element of the array.

Now let’s see the code of this algorithm in C++.

void selectionSort(int *arr, int N) { int posmin, count, tmp ; for (count=0;count<N;count++) { posmin = findIndexMin(arr, count, N) ; tmp=arr[posmin] ; arr[posmin]=arr[count] ; arr[count]=tmp ; } } int findIndexMin (int *arr, int start, int N) { int posmin=start ; int index ; for(index=start; index < N; index++) if (arr[index]<arr[posmin]) posmin=index ; return posmin ; }

In the above code, we write the function selectionSort. This function takes an array of integers as *arr and the size of array as N. There are local variables declared in function as posmin, count and tmp. Then there is a ‘for loop’ that starts from zero and goes to N-1. This is due to the fact that the index of array of N elements is from zero to N-1. The condition count < N indicates that loop will execute as long as count is less than N and will exit when count gets N. Now in the loop, we calculate the posmin with a function i.e. findIndexMin. This findIndexMin method is written below in the code. This routine or method works in the way that we pass to it the whole array i.e. arr, the value of count (what it is in that execution of loop) and size of the array i.e. N. This routine starts the search from the index equal to value of count and goes to Nth position, returning the position of the minimum (smallest) element. Now in the first routine, we get this position value in the variable posmin. Thus the code line:

posmin = findIndexMin(arr, count, N) ;

gets the position of the smallest number returned by the method findIndexMin in the variable posmin. After finding this position, we do the swapping of this posmin with the count position. Thus we put the value of position posmin in the count position.

The findIndexMin routine is such that it takes arr, start and N as arguments. It starts searching from the start position in the for loop, finds the position of the minimum value and returns that position.

This sorting algorithm is also known as the in-place sorting algorithm as there is no need of additional storage to carry out this sorting. The pictorial representation of the swap action of this algorithm will be as under:

We want to sort the following array that has five elements. We start the search from the first element and find that the smallest element is 5. As we have started our search from index 0 (that is the count in our above code) so we swap 5 with the value at index 0 i.e. 20. After this swap, 5comes at the position of 20 while 20 goes to the position of 5. Afterwards, we start the search from index 1. We find that 7 is the smallest number among the remaining elements. It swaps its position with 8. After this, in the remaining three elements, 8 is the smallest. This number 8 swaps its position with 20. At the end, 10 is the smallest number among 10 and 20. So there is no need of swapping as 10 has already got its position.

Selection Sort Analysis

We have seen in the code for the algorithm that there are two loops. The loop in the selectionSort method passes the array to search the smallest element and the second loop that is in the findIndexMin method finds the position (index) of the smallest value. To find the first smallest element, we have to go through the N elements of the array. For the purpose of finding the second smallest element, we have to search the N-1 elements. During this search process, we have to find two elements for the second last smallest element. And obviously in the end, there is one element that is at its proper position, necessitating no search. We have to do all these searches. These are N, N-1, N-2 ……2, 1 for the first, second, third ……second last and last element respectively. Now if we want to find the total searches, the addition of all these searches together will help us get a sum total as given in the following equation.

Total searches = 1 + 2 + 3 + …….+ (N-2) + (N-1) + N

= N (N+1) / 2

= (N² + N) / 2

Suppose if N is 10, then according to this formula, the total searches will be (100 + 10) / 2 i.e. 55. If N is 100, the total searches will be (10000 + 100) / 2 i.e. 5050. Similarly if N is 1 million, N² is going to be very large as compared to N. Thus there we can ignore N and can say that the time (total searches) is proportional to N². This means that larger the N, greater will be the performance of selection with respect to N^2.

Technorati Tags: data structure and algorithm,ds and algo,ds tutotrial,selection sort,selection sort algorithm