알고리즘 공부 - sort

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 정렬(sort)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

개요

정렬은 프로그래밍에서 기본적이고 중요한 개념입니다.

저는 강의에서 공감을 했던 부분이 데이터를 탐색함에 있어서 정렬된 데이터를 유지하느냐 그렇지 않느냐에 따라 시간복잡도가 다를 수 있다는 것을 깨닫게 되었기 때문입니다.

조금 더 구체적으로 얘기해보면 무작위 순서를 가진 데이터에서도 순차적으로 데이터를 탐색하며 원하는 결과를 얻을 수도 있지만, 데이터가 정렬되어 있다면 탐색을 효율적으로 할 수 있기 때문입니다.

한 예시로
정렬되지 않은 배열 [5, 8, ..., 1]에서 7이 위치한 인덱스를 찾고 싶으면 첫 번째 원소부터 탐색을 해야하지만
정렬된 배열 [1, 2, ..., 10] 에서 7이 위치한 인덱스를 찾고 싶을 때는 값의 상대적 위치를 활용하여 예상 위치를 추정하며 탐색의 범위를 좁힐 수 있습니다.

정렬 알고리즘의 종류

기본적인 정렬 알고리즘에는 다음의 것들이 있습니다.

• 선택정렬
• 버블정렬
• 삽입정렬
• 합병정렬
• 빠른정렬
• 힙정렬
• 계수정렬
• 기수정렬

이 중 선택정렬, 버블정렬, 삽입정렬은 간단하게 구현할 수 있지만 정렬 속도는 O(n^2)으로 느리다는 특성이 있고, 합병정렬, 빠른정렬, 힙정렬은 O(nlogn)으로 속도가 빠르다는 장점이 있습니다.

그 외에 계수정렬, 기수정렬은 제한된 조건 내에서 O(n) 의 속도를 가집니다.

선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 큰 수를 찾은 후 해당 수를 가장 마지막으로 보내는 것을 아이디어로 합니다.

예제

버블 정렬 (Bubble Sort)

버블 정렬도 선택 정렬과 마찬가지로 배열에서 가장 큰 수를 배열의 가장 마지막으로 보내는 것을 아이디어로 합니다.

하지만 선택 정렬과의 차이점은 명확히 최대 수를 찾는 방식이 아니고, 배열의 전/후 수를 비교하여 큰 수를 뒤로 미는 방식입니다.

예제

삽입 정렬 (Insertion Sort)

삽입 정렬은 배열이 정렬되어있다는 전체에 새로운 값을 정렬 순서에 맞게 추가하는 것을 아이디어로 합니다.

따라서 삽입 정렬은 최악의 경우에는 선택 정렬, 버블 정렬과 같이 O(n^2)의 속도를 가지지만, 최선의 경우에는 O(n)의 속도를 가집니다. 평균적으로 선택 정렬, 버블 정렬의 절반인 O(n^2/2)의 속도를 가진다고 볼 수 있습니다.

예제

합병 정렬 (Merge Sort)

합병 정렬은 분할정복법 (Divide and Conquer)을 사용하는 정렬 알고리즘 입니다. 분할 방식은 주어진 배열을 반으로 나눠 각각을 정렬하고 합치는 방식을 취합니다.

합병 정렬의 속도는 O(nlogn)입니다.

단점으로는 합병하는 과정에서 추가적인 배열을 사용해야한다는 점입니다.

예제

빠른 정렬 (Quick Sort)

빠른 정렬도 합병 정렬과 같이 분할정복법을 사용하는 정렬 알고리즘 입니다.합병 정렬과의 차이점은Pivot`이라는 개념을 이용하여 기준 데이터를 기준으로 큰 집합과 작은 집합을 나눈 후 각각을 정렬하는 방식을 취합니다.

합병 정렬에서 단점으로 언급됐던 추가적인 배열을 사용하지 않는 다는 단점이 있고, 최악의 경우에는 선택정렬, 버블정렬, 삽입정렬과 같이 O(n^2)의 속도를 가지지만 평균적으로 합병 정렬과 같이 O(nlogn)의 속도를 가집니다.

빠른 정렬은 Pivot을 어떻게 선택하느냐에 따라 정렬 속도가 달라질 수 있기 때문에 Pivot을 선택하는 방식에도 존재합니다.

첫번째 값이나 마지막 값을 pivot으로 선택하면 이미 정렬된 데이터를 정렬할 경우 최악의 성능을 가집니다. 대체로 현실에서 사용하는 데이터는 정렬되어 있는 경우가 많기 때문에 첫번째 값이나 마지막 값을 pivot으로 선택하는 경우는 좋지 않습니다.

첫번째, 마지막, 가운데 값 중에서 중간값을 pivot으로 선택하는 방법도 있는데요. 이 경우 최악의 경우에도 시간 복잡도는 O(nlogn)을 유지할 수 있습니다. 또한 pivot을 랜덤하게 선택하는 경우에도 O(nlogn)의 성능을 유지할 수 있습니다.

예제

힙 정렬 (Heap Sort)

힙 정렬은 주어진 배열을 complete heap의 자료구조로 가정하여 정렬하는 방식입니다.

힙(heap)이란 완전 이진 트리(complete binary tree)이면서 heap property를 만족하는 자료구조 입니다. 'heap property란, 부모가 자식보다 크거나 같은max heap property이거나 부모가 자식보다 작거나 같은min heap property를 만족하는 것을 말합니다.complete binary tree는n-1레벨까지는full biary tree이면서 n레벨의leaf node`가 좌측으로 정렬되어있는 트리를 말합니다.

힙 정렬의 시간 복잡도는 O(nlogn)입니다.

예제

Comparison sort의 최대 속도

정렬 알고리즘의 유형에는 comparison sort와 non-comparison sort가 있습니다. 데이터들간 상대적인 크기관계만으로 정렬할 것이냐 사전 지식을 활용할 것이냐에 따라 구분할 수 있는데요.

comparison sort의 경우 앞에서 언급한 모든 알고리즘을 포함합니다.

comparison sort는 입력 데이터를 한번씩 보기 위해서는 O(n)의 시간복잡도가 무조건 필요합니다. 그리고 그 어떤 알고리즘도 O(nlogn)의 시간복잡도보다 나을 수 없습니다.

왜냐하면, decision tree를 활용하여 비교에 대한 경우의 수를 나열해보면 결국 트리의 높이가 가장 낮은 경우가 비교의 경우가 작은 경우인데 트리의 높이가 가장 낮은 경우가 complete binary tree 일 경우이고 이때 logn!의 높이를 가지기 때문입니다.

결국 logn!은 수학적으로 O(nlogn)의 시간복잡도를 가지기 때문에 comparison sort는 O(nlogn)의 시간복잡도보다 나을 수 없습니다.

Counting Sort

해당 정렬 방식은 사전 지식을 활용한 non-comparison sort이고, 사전 지식은 0 ~ k 사이의 정수입니다.

아이디어는 정렬을 위한 키를 배열 인덱스로 가정하여 데이터를 수를 센 후 식별된 수대로 배열을 재구성하는 방식입니다.

해당 방식은 데이터간 값비교를 하지 않기 때문에 O(n) 의 속도를 가지지만 사전 전제인 k의 값이 정렬할 데이터의 수보다 클 경우에는 실용적이지 않다고 합니다. 그리고 동일한 값일 경우 입력값의 순서가 출력값에도 유지되는 특성이 있습니다. (stable sort)

예제

Radix Sort

Radix sort 또한 counting sort 와 같이 non-comparison sort 입니다. 사전 지식은 0 ~ 9 사이의 수 k 로 구성된 d 자리 정수입니다.

시간 복잡도는 변수 k와 d가 고려되어 O(d(n+k)를 가집니다.

아이디어는 낮은 자릿수부터 stable sort로 정렬을 하면 최종적으로 d 자리 정수가 정렬이 된다는 것입니다.

예제

관련 강의

• [알고리즘] 제3강 기본적인 정렬 알고리즘
• [알고리즘] 제4강 합병정렬(merge sort)
• [알고리즘] 제5강 빠른정렬(quicksort)
• [알고리즘] 제6-1강 힙 정렬(heap sort)
• [알고리즘] 제6-2강 힙 정렬(heap sort) (계속)
• [알고리즘] 제6-3강 힙 정렬(heap sort) (계속)
• [알고리즘] 제7강 정렬의 lower bound
• [알고리즘] 제8-1강 sorting in linear time
• [알고리즘] 제8-2강 sorting in linear time: Radix Sort

관련 글

• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유