Selection Sort

Notes

Selection sort is one way to sort an array of numbers. Data is divided into sorted and unsorted portions. One by one, the smallest values remaining in the unsorted portion are selected and swapped over to the sorted portion of the array.

First, scan the unsorted portion of the array to find the smallest value.

Swap that value with the first unsorted value -- it is now part of the sorted subarray.

Repeat until there are no more values in the unsorted portion of the array.

Let's use selection sort to sort the elements of this array in ascending order.

Selection sort relies on breaking up the array into sorted and unsorted portions.

Before we start sorting, all values are considered unsorted.

On our first pass through the unsorted subarray (which on our first pass is actually the entire array), we find that 2 is the smallest.

We must now swap 2 with the first unsorted value (3) in order to add it to the sorted subarray.

On our second pass through the unsorted subarray, we find that 3 is the smallest.

We must now swap 3 with the first unsorted value (5) in order to add it to the sorted subarray.

On our third pass through the unsorted subarray, we find that 4 is the smallest.

We must now swap 4 with the first unsorted value (5) in order to add it to the sorted subarray.

On our fourth pass through the unsorted subarray, we find that 5 is the smallest.

We must now swap 5 with the first unsorted value (6) in order to add it to the sorted subarray.

When only one value (the largest value) remains in the unsorted subarray, the array has been completely sorted!

And this is a way to implement selection sort in C. Try it yourself!

In both the best and worst cases, we'd have to compare each element to every other element in the unsorted subarray to ensure that the smallest value is selected on each iteration. As such, the selection sort algorithm takes n2 in the best and worst cases.

Since the best and worst case runtimes of selection sort are equivalent, the expected runtime is Θ(n2).

As you can see, O(n2) is far from efficient. Maybe we can do better with other sorting algorithms?

Here's a comparison of the runtimes of selection sort to the runtimes of other sorting algorithms covered in CS50.

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

(Selection) Sort the Array

Prerequisites:

Use selection sort to sort the array.

jharvard@run.cs50.net (~): ./a.out
4 15 16 50 8 23 42 108
4 8 15 16 23 42 50 108

Try out some pseudocode here!
#include <stdio.h>

#define SIZE 8

void sort(int array[], int size)
{
    // TODO: sort array using selection sort
}

int main(void)
{
    int numbers[SIZE] = { 4, 15, 16, 50, 8, 23, 42, 108 };
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
    sort(numbers, SIZE);
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

Videos

study50 video thumbnail

Wednesday, Week 3

An introduction to sorting algorithms
study50 video thumbnail

Tommy's Selection Sort Short

Tommy gives a general overview