정렬 알고리즘 비교

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

Sorting(정렬)은 데이터를 일정한 기준으로 배치하는 작업이다. 숫자 오름차순뿐 아니라 체력, 이름, 생성 시간처럼 여러 기준을 사용할 수 있다.

선택 정렬

남은 구간에서 가장 작은 값을 찾아 앞쪽과 바꾼다.

for (int i = 0; i < Count - 1; ++i)
{
    int MinIndex = i;

    for (int j = i + 1; j < Count; ++j)
    {
        if (Values[j] < Values[MinIndex])
        {
            MinIndex = j;
        }
    }

    std::swap(Values[i], Values[MinIndex]);
}

구현은 쉽지만 비교 횟수가 O(N²)이라 큰 데이터에는 어울리지 않는다.

병합 정렬

배열을 절반씩 나누고 각각 정렬한 뒤 합친다. 시간 복잡도는 O(N log N)이고 안정 정렬로 구현할 수 있지만 합치는 임시 메모리가 필요하다.

퀵 정렬

Pivot을 기준으로 작은 값과 큰 값을 나누고 각 구간을 다시 정렬한다. 평균은 O(N log N)이지만 Pivot 선택이 계속 나쁘면 O(N²)까지 내려갈 수 있다.

실제 C++ 코드에서는 직접 정렬을 다시 만들기보다 std::sort와 std::stable_sort를 먼저 사용한다.

std::sort(Units.begin(), Units.end(),
    [](const Unit& A, const Unit& B)
    {
        return A.Speed > B.Speed;
    });

알고리즘 공부로 직접 구현하는 것과 제품 코드에서 검증된 표준 라이브러리를 사용하는 것은 목적이 다르다.