Advanced Database Management System - Tutorials and Notes: Selection sort algorithm in data structures

## Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

## Selection sort

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

**********