Small Steps III — Thinking with Programs

Put Values in Order

Put Values in Order

Explore one topic in small steps. Try the examples one at a time and take a break whenever you need. Choose how many extra exercises you want to try.

Ordering from smallest to largest

What you will learn

Sorting changes an order according to a rule. This method finds the smallest remaining value and fills positions from the front.

Try it

Example · example1.cpp
void small_main()
{
    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;
    }

    for (int i = 0; i < numbers.length(); i = i + 1)
        print(numbers[i]);
}

The outer loop selects the position i to fill; the inner loop finds the minimum's index in the remaining part.

Use temp to hold one value temporarily when swapping. Overwriting it immediately would lose the original. Check that the output is 2, 4, 5, 7, 9.

Ordering from largest to smallest

What you will learn

Changing the comparison rule changes the order without changing the procedure. Listing larger values first is descending order.

Try it

Example · sorting_2_example2.cpp
void small_main()
{
    Array<int> numbers = {7, 2, 9, 4, 5};

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

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

        int temp = numbers[i];
        numbers[i] = numbers[largest];
        numbers[largest] = temp;
    }

    for (int i = 0; i < numbers.length(); i = i + 1)
        print(numbers[i]);
}

Now find the largest remaining value. The comparison changes from < to >, and the output becomes 9, 7, 5, 4, 2.

You do not need to rebuild the whole loop to change sorting direction. Change which value is selected first.

Showing numbers as bars

What you will learn

Visualization represents data as pictures. Draw taller bars for larger values to see an array.

Try it

Example · visualizing_1_example1.cpp
void small_main()
{
    Window window;
    window.open(450, 450);

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

    window.clear(White);

    for (int i = 0; i < numbers.length(); i = i + 1)
    {
        double height = numbers[i] * 30;
        window.fill_rectangle(40 + i * 70, 420 - height, 50, height, Blue);
    }

    window.show();

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

Multiply each value by 30 for its height. Since y increases downwards, calculate the bar's top as 420 - height.

Change one array value and check that its bar's height changes.

Watching a sort happen

What you will learn

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

Try it

Example · visualizing_2_example2.cpp
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

Use Selection Sort to arrange {10, 3, 8, 1, 6} from smallest to largest.

Exercise starter · exercise1_starter.cpp
void small_main()
{
    Array<int> numbers = {10, 3, 8, 1, 6};

    // Selection Sort here.

    for (int i = 0; i < numbers.length(); i = i + 1)
        print(numbers[i]);
}

Hint

Apply the lesson's smallest-index pattern.

show solution
void small_main()
{
    Array<int> numbers = {10, 3, 8, 1, 6};

    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;
    }

    for (int i = 0; i < numbers.length(); i = i + 1)
        print(numbers[i]);
}
Try More (Optional)

Exercise

Modify Selection Sort to arrange values from largest to smallest.

Exercise starter · sorting_2_exercise2_starter.cpp
void small_main()
{
    Array<int> numbers = {10, 3, 8, 1, 6};

    // Sort from largest to smallest.

    for (int i = 0; i < numbers.length(); i = i + 1)
        print(numbers[i]);
}

Hint

Find largest instead of smallest, and change the comparison to >.

show solution
void small_main()
{
    Array<int> numbers = {10, 3, 8, 1, 6};

    for (int i = 0; i < numbers.length(); i = i + 1)
    {
        int largest = i;
        for (int j = i + 1; j < numbers.length(); j = j + 1)
            if (numbers[j] > numbers[largest])
                largest = j;

        int temp = numbers[i];
        numbers[i] = numbers[largest];
        numbers[largest] = temp;
    }

    for (int i = 0; i < numbers.length(); i = i + 1)
        print(numbers[i]);
}

Exercise

First practice the position marker for a sorting animation separately. Draw the bar at current in Red and all others in Blue. This exercise is a static picture and does not sort. Change current from 0 through 4 and check that the red bar moves to that position.

Exercise starter · visualizing_1_exercise1_starter.cpp
void small_main()
{
    Window window;
    window.open(450, 450);

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

    window.clear(White);

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

        // Make current red.

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

    window.show();

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

Hint

In the drawing loop, choose Color by testing i == current. In the sorting animation, use the position fixed in that step instead of current.

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

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

    window.clear(White);

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

        if (i == current)
            color = Red;

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

    window.show();

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

Exercise

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

Exercise starter · visualizing_2_exercise2_starter.cpp
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.

show solution
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);
}
← Previous lessonNext lesson →