Small Steps III — Thinking with Programs

Watching a sort happen

Watch a sorting process.

What you will learn

Drawing intermediate states, rather than only the final answer, lets you see an algorithm work.

Try it

void small_main()
{
    Window window;
    window.open(450, 450);

    Array<int> numbers = {7, 2, 9, 4, 5};

    for (int i = 0; i < numbers.length(); i = i + 1)
    {
        int smallest = i;

        for (int j = i + 1; j < numbers.length(); j = j + 1)
            if (numbers[j] < numbers[smallest])
                smallest = j;

        int temp = numbers[i];
        numbers[i] = numbers[smallest];
        numbers[smallest] = temp;

        window.clear(White);

        for (int j = 0; j < numbers.length(); j = j + 1)
        {
            double height = numbers[j] * 30;
            Color color = Blue;
            if (j == i)
                color = Red;

            window.fill_rectangle(40 + j * 70, 420 - height, 50, height, color);
        }

        window.show();
        sleep(0.5);
    }

    while (window.is_open())
        window.show();
}

After fixing one position, redraw all bars and wait 0.5 seconds. The position just fixed is red.

Look at the changed array and describe how far sorting has progressed. Read the drawing and sorting sections separately.

Exercise

Count and print the number of actual swaps in Selection Sort. You may skip swapping a position with itself.

void small_main()
{
    Array<int> numbers = {7, 2, 9, 4, 5};
    int swaps = 0;

    // Sort and count real swaps.

    print("Swaps: ", swaps);
}

Hint

Start swaps at 0. Swap and increase it only when smallest != i.

void small_main()
{
    Array<int> numbers = {7, 2, 9, 4, 5};
    int swaps = 0;

    for (int i = 0; i < numbers.length(); i = i + 1)
    {
        int smallest = i;

        for (int j = i + 1; j < numbers.length(); j = j + 1)
            if (numbers[j] < numbers[smallest])
                smallest = j;

        if (smallest != i)
        {
            int temp = numbers[i];
            numbers[i] = numbers[smallest];
            numbers[smallest] = temp;
            swaps = swaps + 1;
        }
    }

    print("Swaps: ", swaps);
}