정렬 - 기본기

기본 다지기 - 정렬

정렬이야말로 기본기 중 가장 밑단이면서도, 모든 알고리즘의 대표격이라고 생각한다.

여러 정렬의 종류를 알아보고, 새로운 정렬 방식이 있는지, 그것의 복잡도는 어떻게 계산되는지 생각해 보자.

 

정렬이란

비교 가능한 요소를 가지고 있는 데이터셋의 연속 (배열이나 리스트 등) 에서, 특정한 조건을 기준으로 요소들의 순서를 재배치 하는 방법론이다.

일반적으로 특정 값을 오름차순, 내림차순으로 순서를 매기는 것이 대표적이다.

하지만 특정 값에 가장 가까운 순서라던지, 특정 계산식을 거쳤을 때 원하는 값에 가깝게 나오는 순서라던지 등등 확장은 마음껏 가능할것 같다.

물론 이들도 결국 계산식을 거친 후 그 값에 의한 오름 내림차순이기는 하겠지만.

 

들어가기 앞서

swap

두 요소 간 배열 등 연속된 자료형에서의 순서를 바꿔주는, 즉 둘의 메모리에서의 위치를 변경해주는 swap 함수이다.

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
    return;
}

이를 라이브러리나 내장함수를 통해 쉽게 처리할 수 있는 방법이 있을까?

C에서는 템플릿이 존재하지 않기 때문에, 구현한다면 인자 형식이 void* 이 될 텐데, 이는 type-safe 하지 않다.
출처

그렇다면 C++ 템플릿을 적용해 이쁘게 짜보자.

template <typename T> 
void swap(T *a, T *b) {
    T temp = *a;
    *a = *b;
    *b = temp;
    return;
}

이제 이걸 C++ swap 함수와 비교해 보자.

template <class T>
void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}

확실히, C++만의 특징이 몇 개 보인다.

첫째로, 참조자를 통해서 전달받게 바뀌었다. 물론 포인터를 사용한 것과 참조자를 사용한 것 모두 결과는 같고, 구문 형태상의 차이만 있지만, 훨씬 이쁘긴 하다.

둘째로, temp 역할을 하는 변수 선언 시 초기화를 곧바로 T c(a) 를 통해서 했다. 이는 T가 기본 자료형이 아니라, 커스텀 자료형이나, 생성자를 통해 특정 작업이 이루어지는 자료형에 대응하기 위함으로 보이며, 그렇게 생각하니 T temp = *a; 와 동일한 결과일 수 있겠지만, 더욱 안전하고 발전된 형태인 것 같다.

 

printArray

배열을 순서에 맞추어 출력해주는 printArray 함수이다.

void printArray(int *array, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return;
}

이 친구도 C++ template, 참조자를 통해서 더욱 이쁘게 바꿔줄 수 있을 것이다.

template <typename T>
void printArray(T &array, int size) {
    for (int i = 0; i < size; i++) {
        cout << array[i];
    }
    cout << endl;
    return;
}

C++ 에서는 iterator라던지 STL을 이용해서 배열이나 리스트를 다루는 함수가 수도 없이 많다.

 

generateRandomArray

이제 정렬 프로그램을 짜는 걸 도와줄, 랜덤으로 size 개의 int 배열을 만들어주는 generateRandomArray 메서드만 정의하고 넘어가자.

int* generateRandomArray(int size) {
    int *myArray = (int*) calloc(size, sizeof(int));
    srand((unsigned)time(NULL));
    for (int i = 0; i < size; i ++) {
        myArray[i] = rand() % 100;
    }
    return myArray;
}