2. 순차 정렬(Sequential Sort)

순차 정렬의 개념

한 자리씩 순차적으로 정렬한다고 해서 순차 정렬이라 부른다.

 

▼ 순차 정렬 알고리즘 도식화

그림에서처럼 현재 위치와 그 뒤의 값들과 비교하면서 가장 작은 값(혹은 큰 값)으로 교환한다.

 

내부 순환문이 한번 다 돌면 그 위치는 최솟값 혹은 최댓값이 확정되기 때문에

다음 위치에서 다시 반복하는 것이 알고리즘의 핵심이다.

순차 정렬의 성능[O(n²)]

정렬할 자료의 수의 제곱에 비례하여 늘어난다.

 

단순 무식한 방법인 만큼 순차 정렬은 거의 모든 경우에서 최악의 성능을 보여준다.

하지만 역시나 정렬이 이미 완료된 경우엔 최선의 성능을 보인다.

 

데이터에 따라 다르긴 하지만 순차 정렬은 실무에서는 거의 쓰이지 않는다고 한다.

C99

▼ 관련 개념

Loop & Pointer & Call By Address

 

▼ 구현 코드

int Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void Swap(int* lhs, int* rhs)
{
    int _temp = *lhs;
    *lhs = *rhs;
    *rhs = _temp;
}

void SequentialSort(int iArr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (Compare(iArr[i], iArr[j]) > 0)
            {
                Swap(&iArr[i], &iArr[j]);
            }
        }
    }
}

비교(Compare) 함수가 흥미롭다.

 

단순히 (lhs > rhs)로 반환해도 되지만 차이값을 반환함으로써 대소 여부는 물론 동일 여부까지 확인할 수 있다.

이 방법은 C언어의 표준 함수 중 하나인 strcmp(String Compare)에서도 사용되는 방법이다.

CPP B.11

▼ 관련 개념

Loop & STD

 

▼ 구현 코드

#include <algorithm>

int Compare(int lhs, int rhs)
{
    return (lhs - rhs);
}

void SequentialSort(int iArr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (Compare(iArr[i], iArr[j]) > 0)
            {
                std::swap(iArr[i], iArr[j]);
            }
        }
    }
}

CPP A.98 <algorithm> 라이브러리를 사용한 방법이다.

CPP A.11

▼ 관련 개념

Loop & Template & STD

 

▼ 구현 코드

#include <utility>

template<typename T>
int Compare(T lhs, T rhs)
{
    return (lhs - rhs);
}

template<typename T, typename L>
void SequentialSort(T tArr[], L length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (Compare(tArr[i], tArr[j]) > 0)
            {
                std::swap(tArr[i], tArr[j]);
            }
        }
    }
}

주조(Template)를 사용하여 어떤 변수형이 오더라도 비교하고 정렬할 수 있는 코드가 되었다.

배열의 길이가 int형이 아닌 long이나 long long으로 오더라도 문제없이 작동한다.

 

CPP A.11에서는 std::swap 함수가 <utility>로 이동했다.