작은 걸음 III — 프로그램으로 생각하기

순서 정하기

순서 정하기

한 주제 안에서 차근차근 배워 봅니다. 예제를 하나씩 실행하고, 중간에 쉬었다가 이어서 해도 좋습니다. 마지막의 추가 연습은 원하는 만큼 해 보세요.

작은 수부터 순서 정하기

이번에 배울 것

정렬은 정한 기준에 맞게 순서를 바꾸는 일입니다. 이번 방법은 남은 값 중 최솟값을 찾아 앞자리부터 채웁니다.

실행해 보기

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

바깥 반복은 채울 자리 i, 안쪽 반복은 남은 부분의 최솟값 위치를 찾습니다.

두 값을 바꿀 때 temp에 한 값을 잠시 보관합니다. 곧바로 덮어쓰면 원래 값을 잃기 때문입니다. 출력이 2, 4, 5, 7, 9 순서인지 보세요.

큰 수부터 순서 정하기

이번에 배울 것

같은 절차에서 비교 기준을 바꾸면 순서도 바뀝니다. 큰 수부터 나열하는 것을 내림차순이라고 합니다.

실행해 보기

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

이번에는 남은 값 중 최댓값을 찾습니다. 비교가 <에서 >로 바뀌고 출력은 9, 7, 5, 4, 2가 됩니다.

정렬 방향을 바꾸려고 반복문 전체를 다시 만들 필요는 없습니다. 어떤 값을 먼저 고르는지 바꾸면 됩니다.

숫자를 막대로 보여 주기

이번에 배울 것

시각화는 데이터를 그림으로 표현하는 것입니다. 값이 클수록 높은 막대를 그려 배열을 눈으로 봅니다.

실행해 보기

예제 · 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();
}

값에 30을 곱해 높이를 정합니다. 화면은 아래로 갈수록 y가 커지므로 막대 위쪽을 420 - height로 계산합니다.

배열의 값 하나를 바꾸고 해당 막대의 높이가 달라지는지 확인하세요.

정렬 과정을 눈으로 보기

이번에 배울 것

완성된 답뿐 아니라 중간 상태를 그리면 알고리즘의 동작도 볼 수 있습니다.

실행해 보기

예제 · 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();
}

자리 하나를 정한 뒤 전체 막대를 다시 그리고 0.5초 기다립니다. 이번에 정한 자리는 빨강입니다.

바뀐 배열을 보고 정렬이 어디까지 진행됐는지 말해 보세요. 그림을 그리는 부분과 정렬하는 부분을 구분해 읽습니다.

Exercise — 오름차순 정렬

{10, 3, 8, 1, 6}을 Selection Sort로 작은 순서로 정렬하세요.

연습 문제 코드 · 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

Lesson의 smallest index 패턴을 그대로 적용하세요.

풀이 보기
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]);
}
더 해 보기 (선택)

Exercise — 큰 순서로 바꾸기

Selection Sort를 수정해 큰 값부터 작은 값 순서로 정렬하세요.

연습 문제 코드 · 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

smallest 대신 largest를 찾고 비교 방향을 >로 바꾸세요.

풀이 보기
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 — 현재 위치 표시

먼저 정렬 애니메이션에 사용할 위치 표시를 따로 연습합니다. 시작 코드의 current번째 막대를 Red로, 나머지를 Blue로 그리세요. 이 연습 자체는 정렬하지 않는 정적인 그림입니다. current를 0부터 4까지 바꾸어 빨간 막대가 해당 위치로 바뀌는지 확인하세요.

연습 문제 코드 · 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

막대를 그리는 loop 안에서 i == current인지 검사해 Color를 선택하세요. 앞의 정렬 애니메이션으로 옮길 때에는 current 대신 그 단계에서 확정한 위치를 사용하면 됩니다.

풀이 보기
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 — swap 횟수 세기

Selection Sort에서 실제로 swap을 수행한 횟수를 세고 마지막에 출력하세요. 같은 위치끼리는 swap하지 않도록 해도 좋습니다.

연습 문제 코드 · 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

swaps를 0으로 시작하고 smallest != i일 때만 swap하고 증가시키세요.

풀이 보기
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);
}
← 이전 레슨다음 레슨 →