Selection Sort

Selection Sort

Selection sort is an in-place sorting algorithm. Selection sort works well for small files. It is used for sorting the files with very large values and small keys. This is because selection is made based on keys and swaps are made only when required.

Advantages

• Easy to Implement
• In-Place Sort (require no additional storage space)

Disadvantages

• Doesn't scale well: O(n^2)

Algorithm

1. Find the minimum value in the list
2. Swap it with the value in the current position
3. Repeat this process for all the elements until the entire array is sorted

This Algorithm is called Selection sort since it is repeatedly selects the smallest element

Implementation

void SelectionSort(int A[], int n)
{
    int i, j, min, temp;

    for(int i = 0; i < n - 1; i++)
    {
        min = i;

        for(j =  i + 1; j < n; j++)
        {
            if(A[j] < A[min])
            {
                min = j;
            }
        }

        temp = A[min];
        A[min] = A[i];
        A[i] = temp;
    }
}

Performance

• Worst case complexity : O(n^2)
• Best case complexity : O(n^2)
• Average case complexity : O(n^2)
• Worst case space complexity: O(1) auxiliary