## 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…

There are no comments yet, add one below.