Selection Sort Algorithm in Array

Selection Sort Algorithm in Array is a part of Learning Data Structure Series. In the last article of Insertion Sort Algorithm in Array we learnt to sort the element in increasing order in which smallest element is placed to its correct location first.

In Selection sort algorithm we will be sorting an array with the same concept of placing the smallest element at the beginning. But it differs from Insertion Sort in the way it is implemented. It selects the smallest element and places it to its correct location first. In next phase, it selects and inserts second smallest element to its correct location and so on.

Selection Sort Algorithm in Array

Let us consider an array DATA having n elements, DATA[1],DATA[2], …., DATA[N]. To sort the array we make the use of a special variable MIN. MIN holds the current smallest value while scanning the subarray . We compare MIN with each element of array. If we found smaller element than MIN then we replace MIN by that smaller value.

Lets now see how it works.

Pass 1. Find the location LOC of smallest element in the array of N elements. Interchange DATA[LOC] and DATA[1].

Pass 2.  Find the location LOC of smallest element in the subarray of N-1 elements. ( from DATA[2] to DATA[N] ). Interchange DATA[LOC] and DATA[2].

. . .

. . .

Pass N-1. Find the location LOC of smallest element in between DATA[N-1] and DATA[N]. Interchange DATA[LOC] and DATA[N-1].

So now DATA[1],DATA[2],…. DATA[N-1] is sorted. Since DATA[N] is the last element, it got its correct position automatically.Thus DATA[N] is sorted in N-1 passes.

The Selection Sort Algorithm is as follows.


1. Repeat steps 2 to 4 for I = 1,2,...,N-1
2.     Set MIN := DATA[I] and LOC := I
3.     Repeat for J = I+1, I+2,.....,N
           If MIN > DATA[J] then:
                Set MIN := DATA[J]
                LOC := J
           [End If]
       [End of Loop]
4.    Set TEMP := DATA[I]
       DATA[I] := DATA[LOC]
       DATA[LOC] := TEMP
   [End of Loop]
5. Exit.

In above algorithm DATA is an unsorted array with N elements. MIN holds the value of smallest element and LOC holds its location. TEMP is a variable which is used for interchanging DATA[I]and DATA[LOC] .

Lets now understand this algorithm with example.

Selection Sort Algorithm in Array

Selection Sort Algorithm in Array

In above array DATA we have 8 unsorted elements. The selection sort algorithm will work as follows.

Pass 1:

I = 1 so

DATA[I] = 70   and MIN = 70

As 70 > 30   So Now MIN =30 then

30 < 40   So  MIN =30

10 < 30   So MIN =10

10 < 80   So MIN =10

10 < 20   So MIN =10

10 < 60   So MIN =10

10 < 50   So MIN =10

In this way we got the smallest value in the array as 10 and its location LOC =4

So we interchange the value of DATA[I] and DATA[LOC]. Now the smallest value got places at it correct location.

Selection Sort Algorithm - Pass 1

Pass 1

Same Procedure will be applied in all passes.

Pass 2:

Selection Sort Algorithm - Pass 2

Pass 2

The smallest value in the subarray DATA[2] to DATA[8] is 20 and its location LOC =6. So we interchange the value of DATA[2] and DATA[6]. Now the 20 got places at it correct location.

Pass 3:

Selection Sort Algorithm - Pass 3

Pass 3

The smallest value in the subarray DATA[3] to DATA[8] is 30 and its location LOC =6. So we interchange the value of DATA[3] and DATA[6]. Now the 30 got places at it correct location.

Pass 4:

Selection Sort Algorithm - Pass 4

Pass 4

The smallest value in the subarray DATA[4] to DATA[8] is 40 and its location LOC =6. So we interchange the value of DATA[4] and DATA[6]. Now the 40 got places at it correct location.

Pass 5:

Selection Sort Algorithm - Pass 5

Pass 5

The smallest value in the subarray DATA[5] to DATA[8] is 50 and its location LOC =8. So we interchange the value of DATA[5] and DATA[8]. Now the 50 got places at it correct location.

Pass 6:

Selection Sort Algorithm - Pass 6

Pass 6

The smallest value in the subarray DATA[6] to DATA[8] is 60 and its location LOC =7. So we interchange the value of DATA[6] and DATA[7]. Now the 60 got places at it correct location.

Pass 7:

Selection Sort Algorithm - Pass 7

Pass 7

The smallest value in the subarray DATA[7] to DATA[8] is 70 and its location LOC =7. Its already at its correct location. At the same time, observe that DATA[8] is also at its correct location.

So the array is sorted in N-1 comparisons.

Complexity of Selection Sort Algorithm

The term complexity refers to the number of comparisons in the algorithm. In selection sort the number of comparisons independent of original order of elements. So the worst case complexity and average case complexity is same for selection sort

Worst case:  n(n-1)/2

Average case:  n(n-1)/2

Next article of Learning Data Structure Series continues with sorting operation where we will learn Merge sort Algorithm which merges two sorted array in such way that resulting array will be sorted.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *