Time complexity:

Worst-case: \(O(n^2)\)

Best-case: \(O(n^2)\)

Average-case: \(O(n^2)\)

Find the smallest element and move it to the front. Then, find the second smallest and move it.

void SelectionSort(int *list, int size)
{
    int i, j, minIndex, swapCount = 0, runningCount = 0;
    for(i=0;i<size;i++)
    {
        minIndex = i;
        for(j=i+1;j<size;j++)
        {
            runningCount++;
            if(list[minIndex] > list[j])
                minIndex = j;
        }
        if(minIndex != i)
        {
            swap(&list[i], &list[minIndex]);
            swapCount++;
        }
    }
}

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

For example, to sort an array of size 7.

Case I: Worst-case

int worstList[] = {23,20,18,14,10,6,3};

swapCount = 3 and runningCount = 21

Case II: Best-case

int bestList[] = {3, 6, 10, 14, 18, 20, 23};

swapCount = 0 and runningCount = 21

Case III: Average-case

int averageList[] = {20, 6, 23, 3, 18, 14, 10};

swapCount = 3 and runningCount = 21

Unsorted Array: 20, 6, 23, 3, 18, 14, 10

Step01. 20, 6, 23, (3), 18, 14, 10  ->  3, 6, 23, (20), 18, 14, 10

Step02. 3, (6), 23, 20, 18, 14, 10  ->  without swapping

Step03. 3, 6, 23, 20, 18, 14, (10)  ->  3, 6, 10, 20, 18, 14, (23)

Step04. 3, 6, 10, 20, 18, (14), 23  ->  3, 6, 10, 14, 18, (20), 23

Step05. 3, 6, 10, 14, (18), 20, 23  ->  without swapping

Step06. 3, 6, 10, 14, 18, (20), 23  ->  without swapping

—————————————————————————————––​

Sorted Array: 3, 6, 10, 14, 18, 20, 23