C++ 07.04 - 선택 정렬을 사용해서 배열 정렬하기 (Sorting an array using selection sort)

07.04 - 선택 정렬을 사용해서 배열 정렬하기 (Sorting an array using selection sort)

정렬의 경우 (A case for sorting)

배열 정렬이란 배열의 모든 요소를 특정 순서로 정렬하는 프로세스다. 배열을 정렬해 두면 배열 검색의 효율성이 더 높아진다. 예를 들어, 이름 목록에서 이름이 있는지 검색할 경우를 생각해보자. 이름 목록인 배열에서 모든 요소를 검사하여 이름이 있는지 확인해야 한다. 많은 요소를 가진 배열의 경우, 모든 요소를 검색하는 것은 비용이 많이 든다.

그러나 배열에서 이름이 사전 순으로 정렬되어 있다고 가정해보자. 이 경우 찾고자 하는 알파벳보다 큰 이름을 만날 때까지만 검색하면 된다. 그 시점에서 이름을 찾지 못했다면 배열의 나머지 부분에 존재하지 않는다는 것을 알 수 있다. 검색하지 않은 요소들은 모두 알파벳 순으로 더 크다.

정렬된 배열을 검색하는 효율적인 알고리즘이 많다. 간단한 알고리즘을 사용해서 20개의 비교만으로 1,000,000개의 요소를 가진 배열을 검색할 수 있다. 물론 단점도 있다. 배열을 정렬하는 것이 상대적으로 비용이 많이 든다. 그러므로 여러 번 검색하지 않는 한 검색을 빠르게 수행하기 위해 배열을 정렬할 필요가 없을 수도 있다.

경우에 따라 배열을 정렬하면 검색이 필요하지 않을 수 있다. 이전 배열 포스트 예제에서 제일 높은 점수를 찾는 프로그램을 생각해보자. 배열이 정렬되지 않은 경우 가장 높은 점수를 찾으려면 배열의 모든 요소를 조사해야 한다. 그러나 배열이 정렬된 경우 가장 높은 점수는 첫 번째 또는 마지막 위치에 있다(오름차순 또는 내림차순 정렬 여부에 따라 다름). 따라서 검색할 필요가 전혀 없다!

---

정렬 방법 (How sorting works)

일반적으로 정렬은 배열 요소 쌍을 반복적으로 비교하고, 사전 정의된 기준을 충족하는 경우 이를 서로 바꿈으로써 수행된다. 이러한 요소가 비교되는 순서는 사용하는 정렬 알고리즘에 따라 다르다. 정렬 기준은 비교하는 방법에 따라 다르다. (오름차순 또는 내림차순)

두 요소를 교환하기 위한 알고리즘(: swap)을 위해 C++ 표준 라이브러리인 <algorithm> 헤더의 std::swap()함수를 사용할 수 있다. C++ 11에서는 효율성을 위해 std::swap()을 <utility> 헤더로 이동시켰다.

#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>

int main()
{
    int x = 2;
    int y = 4;
    std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
    std::swap(x, y); // swap the values of x and y
    std::cout << "After swap:  x = " << x << ", y = " << y << '\n';
}

This program prints:

Before swap: x = 2, y = 4
After swap:  x = 4, y = 2

스왑(swap) 후 변수 x와 y의 값이 교환되었다.

---

선택 정렬 (Selection sort)

배열을 정렬하는 방법은 여러 가지가 있다. 그중에 선택 정렬(selection sort)은 가장 이해하기 쉽다.

선택 정렬은 다음 단계를 수행해서 배열을 오름차순으로 정렬한다.

1. 배열 인덱스 0에서 시작하여 배열 전체를 검색해서 가장 작은 값을 찾는다.
2. 배열에서 찾은 가장 작은 값을 인덱스 0의 값과 스왑한다.
3. 다음 인덱스에서 1단계와 2단계를 반복한다.

즉, 배열에서 찾은 가장 작은 요소를 찾아 첫 번째 위치로 바꾼다. 그다음으로 가장 작은 요소를 찾아 두 번째 위치로 바꾼다. 이 과정을 요소의 끝에 도달할 때까지 반복한다.

다음은 위 알고리즘을 어떻게 동작하는지 설명하는 예다. 먼저 배열을 살펴보자.

• { 30, 50, 20, 10, 40 }

먼저, 인덱스 0부터 시작하여 가장 작은 요소를 찾는다.

• { 30, 50, 20, 10, 40 }

그런 다음 이 값을 인덱스 0의 요소와 스왑한다.

• { 10, 50, 20, 30, 40 }

이제 첫 번째 요소가 정렬되었으므로 무시할 수 있다. 이제 인덱스 1부터 시작해서 가장 작은 요소를 찾는다.

• { 10, 50, 20, 30, 40 }

그리고 인덱스 1의 요소와 스왑한다.

• { 10, 20, 50, 30, 40 }

이제 처음 두 요소를 무시할 수 있다. 인덱스 2부터 시작해서 가장 작은 요소를 찾는다.

• { 10, 20, 50, 30, 40 }

그리고 인덱스 2의 요소와 스왑한다.

• { 10, 20, 30, 50, 40 }

인덱스 3부터 시작해서 가장 작은 요소를 찾는다.

• { 10, 20, 30, 50, 40 }

그리고 이것을 인덱스 3의 요소와 스왑한다.

• { 10, 20, 30, 40, 50 }

마지막으로 인덱스 4에서 시작하는 가장 작은 요소를 찾는다.

• { 10, 20, 30, 40, 50 }

인덱스 4에 있는 요소와 스왑한다. (아무것도 작동하지 않는다.)

• { 10, 20, 30, 40, 50 }

정렬이 끝났다!

• { 10, 20, 30, 40, 50 }

마지막 비교는 항상 그 자체이기 때문에 생략할 수 있다.

---

C++에서의 선택 정렬 (Selection sort in C++)

C++에서 선택 정렬 알고리즘을 구현하는 방법은 다음과 같다:

#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>

int main()
{
    const int length = 5;
    int array[length] = { 30, 50, 20, 10, 40 };

    // 배열의 각 요소를 단계별로 처리한다.
    // 마지막 하나는 항상 그 자체이기 때문에 생략한다.
    for (int startIndex = 0; startIndex < length - 1; ++startIndex)
    {
        // smallestIndex는 반복에서 만난 값이 가장 작은 요소의 인덱스
        // 값이 가장 작은 요소는 반복의 첫 번째 요소라고 가정하고 시작한다.
        int smallestIndex = startIndex;

        // 그런 다음 배열의 나머지 부분에서 더 작은 요소를 찾는다.
        for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex)
        {
            // 이전에 발견된 것보다 더 작은 요소가 발견되면
            if (array[currentIndex] < array[smallestIndex])
                // 이것을 저장한다.
                smallestIndex = currentIndex;
        }

        // smallestIndex는 이제 배열에서 값이 가장 작은 요소의 인덱스다.
        // 시작 요소와 가장 값이 작은 요소를 스왑한다.
        std::swap(array[startIndex], array[smallestIndex]);
    }

    // 배열을 출력한다.
    for (int index = 0; index < length; ++index)
        std::cout << array[index] << ' ';

    return 0;
}

이 알고리즘의 가장 혼란스러운 부분은 중첩 루프다. 외부 루프(:startIndex)는 각 요소를 하나씩 반복한다. 각 외부 루프 반복에서 내부 루프(:currentIndex)를 사용하여 나머지 배열(:startIndex+1에서 시작)에서 값이 가장 작은 요소를 찾는다. smallestIndex는 내부 루프에 의해 발견된 가장 작은 요소의 인덱스를 저장한다. 그러면 smallestIndex가 startIndex와 스왑 된다. 이와 같은 프로세스가 반복된다.

---

std::sort

배열을 정렬하는 것은 매우 흔한 일이므로 C++ 표준 라이브러리인 <algorithm> 헤더에 std::sort라는 정렬 함수가 포함되어 있다.

#include <algorithm> // for std::sort
#include <iostream>

int main()
{
    const int length = 5;
    int array[length] = { 30, 50, 20, 10, 40 };

    std::sort(array, array+length);

    for (int i=0; i < length; ++i)
        std::cout << array[i] << ' ';

    return 0;
}

std::sort는 나중에 자세히 다룰 예정이다.

---

 번역: 이 포스트의 원문은 http://www.learncpp.com/cpp-tutorial/64-sorting-an-array-using-selection-sort/ 입니다.