Algorithm : Sorting(1)

Nekoder

 

이번에 다루는 내용은 정렬입니다. 그리고 교재의 정렬 챕터에서는 배열 정렬을 다룹니다. 이 쳅터에서는 모든 데이터를 메인 메모리에서 처리할 수 있는 상황인 내부 정렬에 초점을 맞추고 시작합니다.

 

다루는 알고리즘은 N square, Shellsort, N log N 알고리즘 등에 대해서 다룹니다.

그리고,  여기서 다루는 정렬 알고리즘을 비교와 교환을 통해서 설명할 예정이고, vector를 기반으로 코드를 구현할 예정입니다.

추가 메모리를 크게 요구하지 않는 방향으로 다룰 것이라고 말하고 있습니다.

 

---

Insertion Sort

---

1. 삽입 정렬 알고리즘.

삽입 정렬은 가장 단순한 정렬 알고리즘입니다. 최종 정렬된 배열을 하나씩 만들어 가기 때문에 퀵 소트나 힙 소트, 머지 소트 같은 고급 정렬에 비해 큰 리스트대해서는 비효율 적입니다.

 

template <typename Comparable>
void insertionSort(vector<Comparable> & a){
    for (int p = 1; p < a.size(); ++p){
    	Comparable tmp = a[p];
        int j;
        for(j = p; j > 0 && tmp < a[j-1]; --j){
        	a[j] = a[j-1];
        }
    a[j] = tmp;
    }
}

 

먼저 이 코드에 대해서 설명하자면, Comparable 이라는 탬플릿 타입을 받습니다.

그 후에 a라는 벡터를 레퍼런스로 받아서 Insertion Sorting을 수행합니다.

p는 삽입을 시작하려는 위치를 가리키고, 현재 삽입할 요소 a[p]를 tmp에 임시 저장합니다.

왼쪽으로 이동하면서 비교할 인덱스 j 선언하고, p 에서 출발해서 왼쪽으로 이동하면서 tmp보다 큰 애들을 전부 오른쪽으로 밀어냅니다. 그 후 밀기 작업이 모두 끝나면, 빈칸에 tmp를 삽입하는 방식입니다.

 

그러면 배열이 [3, 1, 4, 2] 인 배열을 위 코드로 정렬했을 때, p = 2 인 상황에서는 배열이 어떤 상황일까요? 한 번 생각해보세요.

 

2. STL Implementation of Insertion Sort

표준 템플릿 라이브러리(STL)는 고급 정렬 알고리즘을 사용하는 sort 함수를 제공합니다. 하지만, 우리가 직접 이터레이터를 사용해서 정렬 루틴을 작성하고 싶다면, 삽입 정렬을 사용 할 수 있습니다.

template<typename Iterator, typename Comparator>
void InsertionSort(const Iterator& begin, const Iterator& end, Comparator lessThan){
	if(begin == end) return;
    Iterator j;
    
    for(Iterator p = begin + 1; p != end; ++p){
    	auto tmp = std::move(*p);
        for(j = p; j != begin &&lessThan(tmp, *(j-1)); --j) {
        	*j = std::move(*(j-1));
        }
        *j = std::move(tmp);
    }
}

파라미터가 두 개인 insertionSort도 있지만, 그 함수는 사실 Wrapper 함수 입니다. 실제로는 내부에서 파라미터가 세 개인 함수를 호출합니다.

여기 위에 있는 세 개의 인자를 받는 함수가 실제 삽입 정렬을 수행합니다. 여기서  lessThan은 < 대신 사용할 비교 함수입니다.

기본적으로 < 처럼 비교하지만, 필요 시 수정해서 다른 정렬 기준을 줘서 사용할 수 있습니다.

여기서는 Iterator 버전이라서, vector , list 같은 다양한 컨테이너에 사용이 가능합니다. 또 std::move를 사용해서 불필요한 복사를 줄였습니다. 하지만 j-1과 비교하면서 왼쪽으로 한 칸씩 이동하는 방식은 기본 삽입 정렬 로직과 동일합니다.

 

3. Insertion sort 분석

삽입 정렬은 최악의 경우 수행 시간이 N square이고, 평균 수행 시간도 N square입니다. 하지만, 이미 입력이 정렬되어 있는 경우, best case로 O(N)이 됩니다.

 

---

A Lower Bound for Simple

---

It is easy to show that any algorithm that sorts by exchanging adjacent elements requires Ω(N²)  time on average.

인접한 요소들만 교환해서 정렬하는 알고리즘은 평균적으로 Ω(N²) 시간 복잡도가 필요하다는 것을 쉽게 증명할 수 있다.

 

To see this, we define an inversion in a sequence as a pair of elements that are out of order.

이를 이해하기 위해, 우리는 역순을 순서가 어긋난 원소 쌍으로 정의한다.

 

여기서 역순은 뭘 의미하냐면,  배열 [3, 1, 4, 2] 가 있다고 하면 (3, 1), (3, 2), (4, 2) 이렇게 총 세 개의 inversion이 있다는 것을 의미합니다. 그러면 배열이 정렬될 수록 inversion은 적어지겠죠. 하지만 인접한 요소(adjacent elements)를 하나 교환할 때마다, 단 하나의 inversion만 없앨 수 있기 때문에 배열에 inversion이 많고, 한 번에 하나밖에 제거할 수 없다면, 정렬하는 데 Ω(N²) 시간이 필연적으로 필요하다는 결론에 도달합니다.

---

Shellsort

---

Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of elements that are far apart.

쉘 정렬은 삽입 정렬을 확장한 것으로, 멀리 떨어진 요소들끼리 교환을 허용함으로써 속도를 높이는 방법이다.

 

앞서 본 삽입 정렬은 인접한 요소만 교환했지만, 쉘 정렬은 멀리 떨어진 요소 끼리도 비교/교환합니다. 이렇게 하면, 전체 inversion을 더 빨리 없앨 수 있기에 정렬이 더욱 빨라집니다.

 

template<typename Comparable>
void shellsort(vector<comparable> & a){
	for(int gap = a.size() / 2; gap > 0; gap /=2){
    	for(int i = gap; i < a.size(); ++i){
       	    Comparable tmp = std::move(a[i]);
            int j = i;
            
            for(; j >=gap && tmp < a[j - gap]; j-=gap){
            	a[j] = std::move(a[j-gap]);
            }
            a[j] = std::move(tmp);
        }
    }
}

외부 for문 부터 살펴보면,초기 gap 은 배열 크기의 절반이고 매 반복마다 gap을 반으로 줄입니다. 이 반복을 gap이 0보다 크다면 계속 합니다.

인덱스 i를 gap부터 시작해서 배열을 끝까지 돕니다. 돌면서 현재 요소를 tmp에 임시 저장하고, j를 i로 초기화 합니다. 마치 tmp를 들고 다니면서 알맞은 위치를 찾아다니는 것 처럼 돕니다. 그리고 gap 간격으로 이동하면서 삽입 위치를 찾습니다.

j >= gap이면서, tmp < a[j - gap]이라면 a[j]에 a[j-gap]을 받게하고, j -= gap을 해서 왼쪽으로 이동합니다.그 후에 빈칸에 tmp를 대입하는 방식으로 동작합니다.

간단하게 말하면,

1. gap 간격으로 뛰면서
2. gap 간격 삽입 정렬을 하고
3. gap을 점점 줄이면서 더 촘촘한 정렬을 합니다.
4. gap = 1 일 때, 최종적으로 삽입 정렬을 하고 마무리하는 방식입니다.

Worst-Case Analysis of Shellsort

쉘 정렬의 최악 경우 수행 시간은 증분 수열(increament sequence)에 크게 의존합니다. (증분 수열 = gap)

위 코드에서 다룬 매번 gap을 절반으로 나누는 방식은 최악의 경우 Θ(N²) 시간 복잡도를 가집니다. gap을 절반으로 나누면서 간격을 줄이는 방식은 생각만큼 빠르지 않습니다. 후에 더 나은 증분 수열을 다룰 예정입니다.