## Selection sort algorithm in data structures

##
__Selection sort__

Selection sort is an in-place sorting algorithm with
the worst case time complexity of O(n

^{2}). It works as follows;
Let us consider an array A of size n stored in memory.

- The selection sort algorithm first selects the smallest element in the array A and place it at array index 0; [the index position 0 is sorted now]

- Then it selects the next smallest element in the array A excluding index 0 (considered sorted) and place it at array index 1. [the index positions 0 and 1 are sorted now]

- Then it selects the next smallest element in the array A excluding indexes 0, 1 (considered sorted) and place it at array index 2. [the index positions 0,1, 2 are sorted now]

- The algorithm continues this procedure until it places the biggest element in the last position of the array.

**Algorithm/Pseudo-code:**
for (i = 1, i ≤
n − 1; i + +)

{

low_index = i; low_key = A[i];

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

if (A[j] < low_key)

{

low_key = A[j];

low_index = j

}

swap (A[i], A[low_index])

}

**Example:**
**********

Go to Sorting algorithms compared page

Go to Sorting algorithms and programs page

Go to Time complexity of sorting algorithms page

Go to Selection sort program (recursive) page

## No comments:

## Post a Comment