Selection Sort

What is selection sort?

An in-place sorting algorithm that finds minimum element in each cycle and puts it in appropriate position in list.

Time and Space Complexity:

• Best Time Complexity: O(n^2)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)
• Best Space Complexity: O(1)

Steps:

1. Find the minimum item in list and swap it with 1st element.
2. Now find the min. item in list excluding 1st item and swap it with 2nd element.
3. Likewise in each cycle exclude already swapped min. items and keep finding min. item in remaining list.
4. Perform such (number of elements – 2) cycles.
5. When remaining list size is 1 you get sorted list.

Pseudo code for selection sort:

Initialize n = Length of Array

SelectionSort (Array, n)
{
    for i = 0 to n-2
    {
        i_min = i
        for j = i+1 to n-1
        {
            if Array[j] < Array[i_min]
                i_min = j
        }
        Swap(Array[j], Array[i_min])
    }
}

Let’s Code

To code in any language other than C++, 👉 Click here 👈