[자료구조] 정렬(Sort)

동기

• 리스트: 하나 이상의 필드로 된 레코드의 집합
• 키: 레코드를 구분하기 위해 사용되는 필드
• 순차탐색: 레코드를 왼편에서 오른편 또는 오른편에서 왼편으로 레코드를 검사하는 것

template <class E, class K>
int SeqSearch(E *a, const int n, const K& k)
{ // a[1:n]을 왼쪽에서 오른쪽으로 탐색한다. 
// a[i]의 키 값이 k와 같은 가장 작은 i를 반환한다. 
// 그런 i가 없으면, 0을 반환한다.
int i;
for (i = 1; i <= n && a[i] != k; i++);
if (i > n) return 0;
return i;
}

n개의 레코드를 탐색하기 위해 O(n)의 시간이 걸린다.

 

• 이원탐색(Binary Search): 정렬된 n개의 레코드를 탐색하기 위해 O(log n)의 시간이 걸린다.
• 보간법(interpolation): 리스트가 정렬돼 있을 때만 사용 가능, 탐색의 성질은 리스트에 있는 키의 분포에 달려있음

리스트를 반복해서 탐색할 때 리스트를 정렬된 상태로 유지하는 것이 이롭다.

 

정렬(Sort)

2개 이상의 자료를 작은 것부터 큰 것 순서의 오름차순 (ascending)이나 큰 것부터 작은 것 순서의 내림차순 (descending)으로 재배열하는 것을 정렬이라 한다.

 

실행방법에 따른 분류

• 비교식 정렬(comparative sort)

비교하고자 하는 각 키 값들을 한번에 두 개씩 비교 하여 교환하는 방식으로 정렬을 실행하는 방법

• 분산식 정렬(distribute sort)

 키 값을 기준으로 하여 자료를 여러 개의 부분 집합 으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

 

정렬 장소에 따른 분류

• 내부 정렬: 정렬할 자료를 메인 메모리에 올려서 저장하는 방식
• 외부 정렬: 정렬할 지료를 보조기억장치에 저장하는 방식

 

버블정렬

인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.

• 메모리 사용공간

n개의 원소에 대하여 n개의 메모리를 사용한다.

• 평균 시간 복잡도는 O(n^2)
• 비교횟수는 i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번이다.

선택정렬

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다.

• 시간 복잡도는 어떤 경우에서나 같으므로 비교횟수는 O(n^2)이다.

 

삽입정렬

정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다.

연산시간

• 최선의 경우 -  이미 정렬되어 있는 경우에는 바로 앞자리 원소와 한 번만 비교: O(n)
• 최악의 경우 - 모든 원소가 역순으로 되어 있어 비교 횟수가 최대: O(n^2)

 

퀵 정렬

정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.

왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.

• 분할(divide): 정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할
• 정복(conquer): 부분 집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분 집합으로 정렬

연산시간

• 최선의 경우 - 피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
• 최악의 경우 - 피봇에 의해 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우

 

병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법이다.

 

병합 정렬 방법의 종류

• 2-way 병합: 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법
• n-way 병합: n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법

 

메모리 사용 공간

• 각 단계에서 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요하다.
• 원소 n개에 대해서 (2xn)개의 메모리 공간 사용

 

연산 시간

• 전체 병합 정렬의 시간 복잡도: O(nlog2n)

 

힙 정렬

힙에서는 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환한다.

 

기수정렬

원소의 키값을 나타내는 기수를 이용한 정렬 방법이다.