Selection sort algorithm in data structures

Sunday, March 25, 2018

Selection sort

Selection sort is an in-place sorting algorithm with the worst case time complexity of O(n²). 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