Small Steps III — Thinking with Programs

Ordering from smallest to largest

Order values 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

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.

Exercise

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

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.

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