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

정렬 과정을 눈으로 보기

정렬 과정을 눈으로 보기

이번에 배울 것

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

실행해 보기

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

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

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