Selection Sort

 

Selection sort will not require no more than n-1 interchanges. Suppose x is an array of

size n stored in memory. The selection sort algorithm first selects the smallest element

in the array x and place it at array position 0; then it selects the next smallest element

in the array x and places it at array position 1. It simply continues this procedure until it

places the biggest element in the last position of the array.

ALGORITHM:

Step 1 set main to location 0

Step 2 search the minimum element in the list

Step 3 swap the value at the location min

Step 4 increment main to point to the next element

Step 5 repeat until the list is sorted

PSEUDOCODE:

For I = 0 to N-1 do:

Smallsub = I

For J = I + 1 to N-1 do:

If A(J) < A(Smallsub)

Smallsub = J

End-If

End-For

Temp = A(I)

A(I) = A(Smallsub)

A(Smallsub) = Temp

End-For

PROTOTYPE CODE:

for ( i = 0 ; i < n-1 ; i++ ) {

k = i

for ( j = i+1 ; j < n ; j++ )

if ( a[j] < a[k] )

k = j

swap a[i] and a[k]

}

FUNCTIONING DIAGRAM:

TIME COMPLEXITY ANALYSIS:

In general, we prefer selection sort in the case where the insertion sort or the bubble sort

requires exclusive swapping. In spite of the superiority of the selection sort over bubble

sort and the insertion sort (there is a significant decrease in run time), its efficiency is

also O(n2) for n data items.

STABILITY:

This is not stable, because there is nothing to stop an item being swapped past another item that has an identical key. For example, the array [21; 22; 13] would be sorted to [13; 22; 21] which has items 22 and 21 in the wrong order.

EXAMPLE:

Consider the following elements are to be sorted in ascending order using selection sort-

6, 2, 11, 7, 5

Selection sort works as-

• It finds the first smallest element (2).
• It swaps it with the first element of the unordered list.
• It finds the second smallest element (5).
• It swaps it with the second element of the unordered list.
• Similarly, it continues to sort the given elements.

 

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11