[Lecture 18] Sorting Algorithm / 정렬 알고리즘

#정렬 알고리즘

컴퓨터 분야에서 중요시되는 알고리즘 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 알고리즘이다. 실제 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생하는데 이걸 얼마나 효과적으로 해결할 수 있느냐가 정렬 알고리즘의 핵심이다.

 

정렬 알고리즘이란 데이터 요소의 집합을 일정한 순서로 배열하는 알고리즘이다. 쉽게 말해 정렬(sort)이란 데이터를 일정한 규칙에 따라 재배열하는 것을 의미한다. 각 요소 내의 1개 또는 복수의 1개 또는 복수의 키값을 바탕으로 하여 배열하는 경우도 있다. 정렬 알고리즘으로는 버블 정렬, 분산 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있다.

[네이버 지식백과 / 나무위키] 정렬 알고리즘

 

보통  데이터의 일부 필드 값(sort key)을 기준으로 오름차순 또는 내림차순으로 데이터 목록을 정렬해야 하는 일이 많다

리스트은 연속적이고 무작위로 액세스할 수 있거나(예: 배열) 분산되어 순차적으로만 액세스할 수 있다(예: 연결 리스트). 구현 세부사항은 다르지만 두 경우 모두 동일한 논리가 적용된다.

다양한 정렬 알고리즘의 성능을 분석할 때 일반적으로 두 가지 요소를 고려한다:
- 필요한 정렬 키 비교 수
- 목록에서 레코드를 이동해야 하는 횟수

최악의 경우와 평균적인 경우 모두 성능이 중요하다

#Internal VS External sort

내부 정렬에서 레코드 목록은 정렬 기간 동안 물리적 메모리에 완전히 유지될 수 있을 정도로 작다.
외부 정렬에서는 레코드 목록이 한 번에 물리적 메모리에 완전히 들어가지 않는다. 이 경우 레코드는 디스크 파일에 보관되고 선택된 레코드만 지정된 시간에 물리적 메모리에 상주한다.

 

즉 데이터를 키의 값에 따라 올림순 또는 내림순으로 일정하게 배열하고 데이터의 개수가 비교적 적어 컴퓨터의 주기억만으로 실행되는 경우를 내부 정렬, 외부 기억을 이용하여 실행하는 경우를 외부 정렬이라고 한다. [네이버 지식 백과]

이번 포스트에서는 내부 정렬에 대해 알아보자.

#Stable VS Unstable sorting

Stable (안정) 정렬이란 동일한 키 값을 레코드들의 처음 순서가 정렬된 다음에도 그대로 유지되는 정렬을 말한다. 즉, 정렬 알고리즘은 키가 같은 레코드의 상대적 순서를 유지할 경우 안정적이라고 한다.

#Insertion Sort

이제 정렬 알고리즘 하나인 삽입 정렬에 대해 알아보자. 삽입 정렬 알고리즘이란 한 번에 한 개씩 적당한 위치를 찾아 삽입·배치하는 알고리즘이다. 배열 내 데이터를 순회하며 정렬이 필요한 원소를 적당한 위치에 삽입하는 알고리즘이다. 즉 새로운 데이터를 이미 정렬된 데이터들 사이의 적절한 자리에 집어넣는 정렬방식이다.

삽입 정렬 자바 코드:

public void insertionSort(T[] A) {

 int j;
 for (int p = 1; p < A.length; p++) {
 T temp = A[p];
 for (j = p; j > 0 && temp.compareTo(A[j-1]) < 0; j--)
 A[j] = A[j-1];
 A[j] = temp;
 }
}

#삽입 정렬 개선

삽입 정렬은 각 목록 요소의 초기 위치가 최종 위치에 상당히 가까울 때 가장 효율적이다. 다음 배열을 한번 보자:

단계 크기(여기서 5)를 선택하고 논리적으로 배열을 부분으로 나눈다. 각 파트의 요소를 정렬한다. 삽입 정렬은 짧은 목록에서 효율적이기 때문에 이 경우 효율적이다.

이 경우 우리는 다음과 같은 배열을 얻는다

이제 더 작은 increment(여기서 3)을 선택하고 이 과정을 반복해보자.

 

리스트 분할:

분할된 부분들 정렬:

그렇다면 다음과 같은 배열을 얻는다

마지막으로 크기 1로 프로세스를 반복시 다음과 같은 배열을 얻는다

이 방법은 일반적인 삽입 정렬보다 더 복잡해 보인다. 그렇다면 이 정렬 방법이 왜 더 빠른 걸까?

 

• 마지막 패스까지 정렬되는 하위 목록은 전체 목록보다 훨씬 짧다. 길이 1000의 두 리스트를 정렬하는 것이 길이가 2000인 한 리스트를 정렬하는 것보다 빠르다.
• 일찍 패스를 하면 각 요소를 완전히 정렬된 목록의 최종 위치에 더 가깝게 이동 시킨다.
• 마지막 패스에서 대부분의 요소는 최종 위치에서 그리 멀지 않으며, 이는 삽입 정렬이 상당히 효율적인 상황 중 하나이다.

#Shell Sort

우리가 방금 알아본 정렬 방법이 셸 정렬이다. 셸 정렬은 삽입 정렬을 개선한 것으로, 일정한 간격으로 부분 배열을 나누고, 각 부분 배열을 삽입하여 정렬하는 알고리즘이다. 삽입 정렬(Insert Sort)은 원소들을 한 칸씩 이동하며 비교하여 가장 거리가 먼 원소와 비교를 할 경우 이동이 많은 오버헤드가 발생한다. 이를 개선한 것이 쉘 정렬로, 기준 값에서 일정한 간격의 부분 배열로 나누고, 각 부분 배열을 삽입하여 정렬하는 알고리즘이다.

[네이버 지식백과 / 쉘 정렬] 

 

즉 간단하게 단계적으로 셸 정렬 알고리즘을 보면

• 요소가 단계 크기, h, 간격인 불연속 하위 목록으로 목록을 분할한다.
• 삽입 정렬을 적용하여 각 하위 목록 정렬
• h의 값을 줄이고 첫 두 단계를 반복하여 h가 1인 패스 후에 멈춘다.

최종 패스(h는 1)는 단순히 전체 목록에 대한 삽입 정렬을 적용한 것이기 때문에 최종 결과는 정렬된 리스트가 된다.

 

셸 정렬 자바:

public void shellSort(T[] A) {
 int increment = A.length / 2;
 while (increment > 0) {

 for (int i = 0; i < A.length; i++) {
 int j = i;
 T temp = A[i];
 while ((j >= increment) &&
 (A[j-increment].compareTo(temp) > 0)) {
 A[j] = A[j - increment];
 j = j - increment;
 }
 A[j] = temp;
 }
 if (increment == 2)
 increment = 1;
 else
 increment = increment * 5 / 11;
 }
}

#Divide and Conquer / 분할 정복

분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다. 그 외에 오토마타에서도 top-down parser등의 개념을 위하여 이용된다. 어원은 제국주의 시절 유럽 식민제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분할통치에서 시작되었다.

 

분할 정복의 포괄적인 의미는 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식을 말한다. 더 자세히 말해 분할 정복이란 문제를 해결하기 쉽도록 먼저 작게 나누고(Divide), 각각의 작은 문제들의 답을 구한 뒤(Conquer), 도출한 답들을 통합(Combine)하여 전체 문제의 해를 찾는 알고리즘이다. 즉 분할과 정복을 통해 문제를 해결하는 알고리즘이다. 주어진 문제를 해결하기 위해 나눌 수 있는 가장 작은 단위의 문제로 나누고, 이 문제들을 풀어 답을 구한 뒤, 답들을 통합하여 전체 문제의 해를 찾는 방법이다. 복잡한 문제의 경우 작게 나누어 생각함으로써 문제의 해결을 용이하게 하고, 업무적으로는 병렬처리가 가능해 퍼포먼스를 높일 수 있다.
[네이버 지식백과 / 나무위키] 분할 정복

 

우리가 방금 알아본 셸 정렬이 바로 "분할 정복" 방법을 사용한 정렬 알고리즘이다. 즉, 큰 문제를 더 작은 부분(아마도 더 관리하기 쉬운 부분)으로 나누고 각 부분을 처리한 다음 어떻게든 개별 결과를 재조합하여 최종 해를 구한다. Shell Sort에서는 단계 크기를 1로 줄이고 하위 목록을 원래 목록 구조 내에 물리적으로 유지함으로써 재조합이 이루어진다. 셸 정렬은 연결된 목록보다 연속된 리스트에 더 적합하다. 그렇기 때문에 이 바로 다음에 나올 정렬법은 분할 정복 방법을 유지하지만 연결 리스트에 더 적합한 알고리즘인 Merge sort / 합병 정렬을 알아보자

#Merge Sort / 병합 정렬

Merge란 ‘조합한다’는 뜻이며 일정한 순서로 되어 있는 데이터를 조합해서 하나로 하는 일을 말한다. 예를 들면, 각 지점의 정보를 1개의 파일로 순서를 붙이는 것 등이다. 또 소트란 분류의 뜻이며, 정보항목을 미리 정해진 일정한 순서가 되도록 정리하는 일을 말한다. 그러므로 머지소트란 컴퓨터를 사용하여 파일의 조합에 의해 분류하는 방법을 말한다.예를 들면 하루 동안의 거래 전표를 고객별로 정해진 순서로 늘어놓아 카드나 테이프에 의해 분류하는 일 등을 말한다. 

 

그렇기에 Merge Sort / 합병 정렬 이란 주어진 데이터들을 몇 부분으로 분할한 다음 각각을 재귀적으로 정렬하고, 두 부분을 합쳐서 하나로 만드는 방법이다. 즉, 하나의 리스트를 정렬하기 위해서 해당 리스트를 n개의 서브리스트로 분할하여 각각을 정렬한 수, 정렬된 n개의 서브리스트로 합병시켜서 정렬시키는 방법을 말한다. 복잡도는 O(n log n)으로 비교적 좋은 편이나 내부 정렬로는 별로 사용하지 않고, 수행시간이 오래 걸려 주로 외부 정렬에 활용된다.

 

퀵 정렬(Quick Sort)와 같이 분할과 정복을 통해 두 개의 정렬된 배열을 합치며(merge) 더 커진 배열로 만들어 간다.두 개의 그룹으로 나누어 정렬 후 병합한다는 점에서 퀵 정렬과 유사하지만 퀵 정렬은 좌우 두 배열의 크기가 다를 수 있어 이것이 최악의 성능 O(n^2)이 될 수 있으나, 병합 정렬은 좌우 두 배열의 크기가 항상 동일하게 분할되어 최악의 경우에도 O(nlogn)의 시간복잡도를 가진다는 점에서 차이가 있다. 또한 병합 정렬은 두 개의 배열을 합쳐 새로운 배열로 만들기 위한 별도의 임시 기억 장소가 필요하다.

[네이버 지식백과] 

 

위에서 언급했듯이 합병 정렬에서 우리는 리스트를 가능한 한 거의 동일한 크기의 두 개 이상의 하위 목록으로 잘라내고, 각 하위 리스트를 개별적으로 정렬한 다음, 정렬된 하위 리스트를 병합하여 원래 리스트의 정렬된 최종 결과를 얻는다. 

두 개의 정렬된 목록을 하나의 정렬된 목록으로 병합하는 것은 비교적 간단한 작업이다.

합병 정렬은 stable 정렬 알고리즘이다

#Heap Sort / 힙 정렬

힙이란 최댓값과 최솟값을 쉽게 추출할 수 있는 완전 이진트리의 자료구조이다.

 

힙 정렬은 내부 정렬 알고리즘의 하나로, 주어진 데이터들을 힙 자료구조, 즉, 최대 힙 트리(Maximum Heap Tree)나 최소 힙 트리(Minimum Heap Tree)를 이용하여 정렬하는 알고리즘이다. 내림차순으로 정렬 시 최대 힙 트리로 구성하고, 오름차순으로 정렬 시 최소 힙 트리로 구성하여 자료를 추출할 수 있다. 더 자세히 말하면 주어진 데이터들을 집산의 조건을 만족하는 완전 이진 트리로 구성한 다음 그 루트 노드를 꺼내면 그것이 데이터 중 가장 큰 값을 가지는 것이 된다. 그 다음 나머지 데이터들에 대해 다시 집산을 구성하고 루트를 꺼내는 작업을 되풀이하면 결국 모든 데이터들이 크기 순서대로 정렬된다. 이는 평균적으로 O(n log n)의 시간 복잡도를 가진다.

 

간단히 힙 정렬 알고리즘이 어떻게 수행되는지 알아보자.

 

힙 정렬 수행 절차(내림차순)
· 완전이진 트리로 정렬할 원소들을 최대 힙 트리로 구성한다.
· 원소 하나씩 추출(삭제)하여 배열의 뒤부터 저장한다.
· 최댓값부터 삭제되며, 삭제되는 순서로 정렬된다.

최대 힙 트리 삽입 절차
· 새로운 원소의 삽입 시 힙의 마지막 노드(node)에 새로운 노드를 삽입한다.
· 새로운 노드를 기존 노드와 비교하여 더 크면 위치를 교환한다.
· 부모 노드부터 노드들이 내림차순으로 최대 힙 트리로 구성되면 교환 작업을 종료한다.

최대 힙 트리 삭제 절차
· 부모노드를 삭제한다.
· 삭제된 부모 노드에 힙의 마지막 노드를 이동시킨다.
· 노드들과 비교하여 최대 힙 트리를 재구성한다.

힙 정렬 성능
완전 이진트리의 최대 힙 재구성 시 트리 깊이만큼 수행하므로 O(logn)만큼의 수행시간이 소요되며, 최악 시간복잡도와 최선 시간복잡도 및 평균 시간복잡도가 모두 동일하다.

[네이버 지식백과] 힙 정렬

 

목록을 먼저 힙에 빌드한 다음 힙이 비워질 때까지 힙에서 루트 노드를 반복적으로 삭제하여 정렬할 수 있다. 삭제된 루트가 배열의 역순으로 저장되면 (최대 힙이 사용되는 경우) 오름차순으로 정렬된다.

public static void heapSort(Integer[] List, int Sz) {
 BinaryHeap<Integer> toSort = new BinaryHeap<Integer>(List, Sz);
 int Idx = Sz - 1;
 while ( !toSort.isEmpty() ) {
 List[Idx] = toSort.deleteMax();
 Idx--;
 }
}

#QuickSort / 퀵 정렬

퀵 정렬(quick sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. [네이버 지식백과] 퀵 정렬

 

퀵 소트는 분할 정복 방식을 사용한다는 점에서 merge sort와 개념적으로 유사하다. 차이점은 파티셔닝이 수행되는 방식과 하위 리스트가 적절한 상대적 순서로 유지되므로 병합이 필요하지 않다는 것이다.

 

• QuickSort는 자연적으로 재귀적인 알고리즘이며, 각 단계는 다음을 포함한다:
  • 현재 하위 리스트에 대한 pivot(기준 키) 값 선택
  • 하위 목록을 두 개의 하위 리스트로 분할한다. 왼쪽은 pivot 값보다 작은 값만 포함하고 오른쪽은 pivot 값보다 크거나 같은 값만 포함한다
  • 결과의 각 하위 리스트를 재귀적으로 처리한다

#Pivot 값의 중요성

Pivot 값의 선택은 QuickSort의 성능에 매우 중요한 영향을 미친다. 분할 단계는 두 개의 동일한 하위 리스트를 생성하는 것이 이상적이다. 최악의 경우 파티셔닝 단계는 하나의 빈 하위 리스트를 생성 할 수 있다.

 

이론적으로 이상적인 pivot 값은 하위 리스트에 있는 값의 중앙값이다. 불행히도 중간 값을 찾는 것은 너무 비싸서 실용적이지 않다.

#Pivot 값 고르기

• 중간 값을 찾는 데 일반적으로 사용되는 대안은 다음과 같다
  • 일정한 위치(첫 번째, 가장 중간, 마지막 등)에서 값을 구한다
  • 첫 번째 값, 마지막 값과 가장 중앙 값 사이의 중앙값을 취한다
  • 세 개의 다른 값을 찾아 그 값의 중앙 값을 구한다

세 번째 방법은 좋은 성능을 보장하는 것이 아니라 두 개의 비어 있지 않은 하위 리스트를 보장하는 유일한 전략이기 때문에 나열된 전략 중 가장 좋다. (물론 세 개의 고유한 값을 찾을 수 없는 경우에는 이 방법이 작동하진 않지만, 현재 하위 리스트에서 고급 정렬을 필요로 하지 않으므로 빠른 스왑을 사용해 효율적으로 완료된다). pivot 값을 찾기 위해 위에서 주어진 각각의 전략은 Θ(1)의 비교 비용을 가진다.

#하위 리스트 분할

QuickSort를 반복할 때마다 하위 목록을 분할해야 하므로 파티셔닝, 즉 분할은 효율적으로 수행되어야 한다. 다행히도, 비교와 할당에서 비용이 Θ(N)인 N개의 요소의 하위 리스트를 분할하기 위한 간단한 알고리즘이 있다.

template <typename T>
unsigned int Partition(T List[], unsigned int Lo, unsigned int Hi ) {
     T Pivot;
     unsigned int Idx,
     LastPreceder;
     Swap(List[Lo], List[(Lo + Hi)/2]); // take middle-most element as Pivot
     Pivot = List[Lo]; // move it to the front of the list
     LastPreceder = Lo;
     for (Idx = Lo + 1; Idx <= Hi; Idx++) {
     if (List[Idx] < Pivot) {
     LastPreceder++;
     Swap(List[LastPreceder], List[Idx]);
 		}
 	}
     Swap(List[Lo], List[LastPreceder]);
     return LastPreceder;
}

#퀵 정렬 구현

방금 설명한 pivot 과 파티션 / 분할 함수가 주어졌다고 가정하면, 주요 QuickSort 기능은 꽤나 간단하다.

template <typename T>
void QuickSort(T List[], unsigned int Lo, unsigned int Hi) {
 QuickSortHelper(List, Lo, Hi);
}
template <typename T>
void QuickSortHelper(T List[], unsigned int Lo, unsigned int Hi) {
 unsigned int PivotIndex;
 if (Lo < Hi) {
     PivotIndex = Partition(List, Lo, Hi);
     QuickSortHelper(List, Lo, PivotIndex - 1); // recurse on lower part,
     QuickSortHelper(List, PivotIndex + 1, Hi); // then on higher part
 }
}

#퀵 정렬 개선

• 퀵 정렬을 다음과 같은 변화를 주어 개선될 수 있다:
  • 비교적 짧은 하위 리스트에서 비재귀적 (반복적) 정렬 알고리즘으로 전환한다. 일반적으로 하위 리스트에 10개 미만의 요소가 포함된 경우 삽입 정렬로 전환하는 것이다.
  • 재귀를 완전히 제거하는 것. 그러나 결과 구현은 재귀 버전보다 이해하기 훨씬 더 어렵다 (따라서 검증하기도 까다롭다).
  • 주어진 구현에서 수행된 것보다 더 신중하게 피벗 값을 선택하기.
  • 파티션 / 분할 알고리즘을 개선하여 스왑 수를 줄인다. 분할 중 스왑 수를 주어진 구현에서 사용되는 스왑의 약 1/3로 줄일 수 있다.

#Bin Sort / Bucket sort / 버킷 정렬

버킷 정렬은 컴퓨터가 개발되기 전에 일련의 자료를 정렬하는 방법이었다. 일련의 자료를 조건에 따라 여러 "버킷"에 넣고 키 값에 따라 다시 정렬하는 것을 의미한다.

 

다음과 같은 0-99 범위의 정수 리스트를 정렬해야 한다고 가정해보자

34 16 83 76 40 72 38 80 89 87

저장을 위한 100(빈)의 정수 배열이 주어지면, 정수 리스트를 통과하고 각각의 값과 일치하는 빈에 배치한다

Bin[Souce[k]] = Source[k]

이 작업은 단 한번만의 패스가 필요하고 비교 하지 않아도 되기 때문에 비용이 N log(N)보다 훨씬 빠른 Θ(N)이다. 아마 정렬 알고리즘중에 Θ(N) 비용으로 실행 할 수 있는 알고리즘은 버킷 정렬 계열의 알고리즘들이 유일 할 것이다. 

function bucketSort(array, k) is
    buckets ← new array of k empty lists
    M ← 1 + the maximum key value in the array
    for i = 0 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 0 to k do 
        nextSort(buckets[i])
    return the concatenation of buckets[0], ...., buckets[k]

• 버킷 정렬의 단점:
  • 빈의 수는 값의 범위에 따라 결정된다
  • 정수 유사 값에만 사용가능하다

#Radix Sort / 기수 정렬

컴퓨터를 개발하기 전에 나타난 카드 분류기(card sorting machine)의 작동 원리를 이용한 정렬 방식. 즉, 수치자료의 정렬을 위한 방법으로, 숫자의 각 자릿수를 기준으로 정렬하는 알고리즘이다. 정렬할 원소를 여러 버킷에 분산하고 정렬하는 버킷 정렬의 일종이다. 기수에 따라서 원소를 버킷에 넣으므로 비교가 불필요하고 수치 자료의 각 자릿수만큼 반복한다.

 

내부 기억 장치를 사용하는 경우, 숫자를 정렬하기 위해서는 10개, 영문자이면 26개의 기억 영역(카드 분류기의 경우에는 포켓이라고 함)을 두고 여기에 정렬이 끝난 항목을 수용한다. 전체 항목이 각 부분 집합에 배분되면 부분 집합의 순으로 모으고, 다음 자리의 정렬에 착수한다. 이 조작을 차례로 반복하면 정렬이 끝나게 된다. 예를 들어 1번부터 99번까지 학생의 시험지를 순서 없이 거두어서 번호대로 정리한다면, 십 단위로 정렬하고 다시 1단위 순서로 각각 정렬하게 된다. 기수 정렬을 버킷 정렬(bucket sort) 이라고도 한다. 기수 정렬은 가장 상위 자릿수부터 정렬하는 MSD(most significant digit) 우선 정렬 또는 왼쪽 우선 정렬(left first sort)이라 하고, 가장 하위 자릿수부터 정렬하는 경우를 LSD(least significant digit) 우선 정렬 또는 오른쪽 우선 정렬(right first sort)이라고 한다.

 

기수 정렬 수행 절차
· 첫 번째 숫자를 키(key)로 해서 정렬 후, 해당 버킷에 분배한다.
· 버킷에 분배된 숫자를 차례대로 추출하여 두 번째 키를 적용하여 정렬 후 해당 버킷에 분배한다.
· 위의 과정을 키의 개수만큼 반복하며 정렬한다.

[네이버 지식백과] 기수 정렬]

 

0-99 범위의 정수 목록을 정렬해야 한다고 가정하자

34 16 83 76 40 72 38 80 89 87

저장할 10개의 연결 리스트(빈) 배열이 주어지면 정수 리스트를 통과한 다음 각각을 1의 자리 숫자와 일치하는 빈에 넣는다.

Bin
 0: 40 80
 1:
 2: 72
 3: 83
 4: 34
 5:
 6: 16 76
 7: 87
 8: 38
 9: 89

그런 다음, 각 빈을 순서대로 가져가서 두 번째 패스를 하고, 각 정수를 10의 자리 숫자와 일치하는 빈에 추가한다.

Bin
 0:
 1: 16
 2:
 3: 34 38
 4: 40
 5:
 6:
 7: 72 76
 8: 80 83 87 89
 9: