## Selection Sort

One of the easiest ways to sort a table is by selection.

• A search is performed to locate the element which has the smallest key starting from the first record.
• When this element is found, it is interchanged with the first record in the table.
• This will place the record with the smallest key in the first position of the table.
• A search for the second smallest key is then carried out from the second element onwards.
• The element which has the second smallest key is interchanged with the element located in the second position of the table.
• The process continues until all records are sorted in ascending order.

Procedure SELECTION_SORT(K, N). Given a vector K of N elements, this procedure rearranges the vector in ascending order; that is, its elements will be in the order K[1] K[2] …. K[N].

• The variable PASS denotes the pass index and the position of the first element in the vector which is to be examined during a particular pass.

• The variable MIN_INDEX denotes the position of the smallest element encountered thus far in a particular pass. The variable I is used to index elements K[PASS] to K[N] in a given pass. All variables are of type integer.

K – Array to be sorted

N – Size of the array

PASS – Pass index

MIN_INDEX – Position of the smallest element encountered till time

I – Loop variable

1)    [Loop on pass index]

Repeat thru step 4 for PASS = 1, 2, ……..N-1

2)    [Initialize minimum index]

MIN_INDEX ß PASS

3)    [Make a pass and obtain element with smallest value]

Repeat for I = PASS +1, PASS + 2,……., N

If K[I] < K[MIN_INDEX]

then    MIN_INDEX ß I

4)    [Exchange elements]

If MIN_INDEX ≠ PASS

then    K[PASS] « K[MIN_INDEX] (SWAP)

5)    [Finish]

Return

Tracing

Here, encircled entry denotes the record with the smallest key selected in a particular pass. The elements above the bar for a given pass are those elements that have been placed in order and need not required to be compared.

Performance analysis:

1.) During the first pass, n-1 records are compared to find the record with the smallest key.

2.) For the ith pass of the sort, n – i comparisons are required.

3.) At the end of the First Pass Smallest element present on First index position,At the end of second smallest element is present at the second index position and so on…