Chapter10 정렬(Sorting)

2018/02/20 - [프로그래밍/자료구조] - Chapter09 우선순위 큐(Priority Queue)와 힙(Heap)

10-1 단순한 정렬 알고리즘

각각의 알고리즘이 갖는 특징에 관심을 두고 공부하는 것이 기억에 오래 남는다.

버블 정렬(Bubble Sort): 이해와 구현

인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식

"정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내기!"

왜 이름이 버블 정렬일까?

비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어진 것이다.

버블 정렬(Bubble Sort): 성능평가

시간 복잡도에 대한 빅-오를 결정하는 기준은 '비교의 횟수'이다. 하지만 '이동의 횟수'까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘간의 세밀한 비교가 가능하다.

버블 정렬의 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n^2)이다.

데이터 이동횟수(교환횟수)에 대한 빅-오는 최악의 기준으로 하여 O(n^2)이다.

선택 정렬(Selection Sort): 이해와 구현

"정렬순서상 가장 앞서는 것을 선택해서 가장 왼족으로 이동시키고, 원래 그 자리에 있던 데이터를 빈 자리에 가져다 놓는다.

선택 정렬(Selection Sort): 성능평가

선택 정렬의 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분없이 O(n^2)이다.

데이터 이동횟수(교환횟수)에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n)이다.

최악의 경우를 놓고 보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있겠지만, 버블 정렬은 최선의 경우에 단 한번의 데이터 이동도 발생하지 않는다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지 않는다는 사실을 감안하면, 이 둘의 우열을 가리는 것은 무의미하다.

삽입 정렬(Insertion Sort): 이해와 구현

"정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다."

"삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다."

삽입정렬(Insertion Sort): 성능평가

비교연산과 이동연산에 대한 빅-오가 O(n^2)이다.

10-2 복잡하지만 효율적인 정렬 알고리즘

정렬대상의 수가 적지 않은 경우에 보다 만족스로운 결과를 보장하는 알고리즘.

힙 정렬(Heap Sort): 이해와 구현

"힙의 루트 노드에 저장된 값이 가장 커야 한다."는 특성을 활용하여 정렬하는 알고리즘이다.

'최대 힙(max heap)'의 특징으로 "힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다"

힙 정렬(Heap Sort): 성능평가

- 힙의 데이터 저장 시간 복잡도    O(log2n)

- 힙의 데이터 삭제 시간 복잡도    O(log2n)

연산에 대한 시간 복잡도 O(log2n)

정렬과정에 대한 시간 복잡도 O(nlog2n)

병합 정렬(Merge Sort): 이해와 구현

'분할 정렬(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다.

- 1단계 분할(Divide)        해결이 용이한 단계까지 문제를 분할해 나간다.

- 2단계 정복(Conquer)    해결이 용이한 수준까지 분할된 문제를 해결한다.

- 3단계 결합(Conbine)    분할해서 해결한 결과를 결합하여 마무리한다.

"8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다."

병합 정렬(Merge Sort): 성능평가

"정렬의 대싱인 데이터의 수가 n개 일 때, 각 병합의 단계마다 최대 n번의 비교연산이 진행된다."

비교연산에 대한 빅-오는 O(nlog2n)이다.

이동연산 횟수는 최악, 평균, 최선의 경우에 상관없이 2nlog2n 이므로 빅-오는 O(nlog2n)이다.

퀵 정렬(Quick Sort): 이해와 구현

"정렬대상에서 세 개의 데이터를 추출한다. 그리고 그 중에서 중간 값에 해당하는 것을 피벗으로 선택한다."

참고로 세 개의 데이터를 추출하는 방법에도 여러 가지가 있다. 단순히 맨 앞에 위치한 세 개의 데이터를 추출하는 방법도 있고, 조금 더 신경을 써서 가장 왼쪽과 가장 오른쪽, 그리고 중간에 위치한 데이터를 추출하는 방법도 있다.

퀵 정렬(Quick Sort): 성능평가

비교연산의 빅-오는 O(nlog2n)이다.

다만 최악의 경우는 아니다. 하지만 퀵 정렬의 경우에는 약간의 예외를 둔다. '중간에 가까운 피벗을 선택하는 방법'을 적용하면, 최선의 경우는 아니지만 최선의 경우에 가까운 성능을 평균적으로 보이기 때문이다. 최악의 경우의 비교연산 횟수에 대한 빅-오는 O(n^2)이다.

시간 복잡도가 O(nlog2n)인 알고리즘이다. 별도의 메모리 공간을 요구하지 않으므로 동일한 빅-오를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.

기수 정렬(Radix Sort): 이해1

"기수 정렬은 정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다."

비교연산은 정렬 알고리즘의 핵심. 정렬 알고리즘의 이론상 성능의 한계는 O(nlog2n)으로 알려져 있는데, 기수 정렬은 이러한 한계를 넘어설 수 있는 유일한 알고리즘이다.

'기수(radix)'란 주어진 데이터를 구성하는 기본 요소를 의미한다.

"데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 방식"

기수 정렬(Radix Sort): LSD 기준 구현

일반적으로 '기수 정렬'이라 하면 LSD 방식을 기준으로 이야기한다.

기수 정렬(Radix Sort): 성능평가

기수 정렬은 비교연산이 핵심이 아니다. 오히려 버킷으로의 데이터 삽입과 추출이 핵심이다. 따라서 이 정렬의 시간 복잡도는 삽입과 추출의 빈도수를 대상으로 결졍해야 한다.

정렬대상의 수가 n이고, 모든 정렬 대상의 길이가 l이라고 할 때, 시간 복잡도에 대한 기수 정렬의 빅-오는 다음과 같다.