자료구조와 함께 배우는 알고리즘 입문 C언어편- 6장
6장_정렬(sorting)
6장에서는 데이터 집합을 일정한 줄지어 늘어서도록 바꾸는 정렬에 대해 다루고 있다.
정렬 알고리즘은 내부정렬(internal sprtomg)과 외부 정렬(external sorting)로 나눌 수 있다.
내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
외부 정렬 : 데이터가 너무 많아 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
이 책에서 다룬 정렬 알고리즘은 8개(버블, 단순 선택, 단순 삽입, 셀, 퀵, 병합, 힙, 도수)이며 모두 내부 정렬이다.
*버블 정렬
버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬이다.
#define swap (type, x, y) do { type t= x; x = y; y = t; } while(0)
/* 비교한 두 요소를 교환하는 함수 */
<그림 2> 처럼 코딩을 할 경우 불필요한 스캔을 하게 되어 효율이 떨어진다. 효율을 높이기 위해 각각의 패스에서 비교, 교환을 하다가 어떤 시점에서 이후에 교환이 수행되지 않는다면 그것 보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 해도 된다. 따라서 <그림 4>에서 첫 요소를 제외한 5개의 요소가 아닌 3개의 요소에서만 비교, 교환을 하면된다. <그림 6>은 개선한 함수이다.
시간 복잡도는 O(n²)이다.
*단순 선택 정렬
단순 선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨 순서를 맞추는 정렬이다.
- 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택
- a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환
시간 복잡도는 O(n²)이다.
*단순 삽입 정렬
다순 삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 ‘삽입’하는 정렬이다. 단순 선택 정렬과 비슷해 보이지만 단순 선택 정렬은 값이 가장 작은 요소를 선택해 위치를 옮긴다는 점에서 다르다.
a[i]을 원하는 값에 삽입 하려면 a[i]보다 작은 요소를 만날 때까지 이웃한 왼쪽의 요소(a[i - 1])를 a[i]에 대입하는 작업을 반복한다.(원래의 a[i] 요소 값은 tmp에 저장) 작은 값을 만나 멈추면 그위에 원래의 a[i]를 대입한다.
- 정렬된 열의 왼쪽 끝에 도달
- tmp보다 작거나 같은 key를 갖는 항목 a[j -1]발견 (j = i )
위의 두 조건 중 하나를 만족할 때까지 j를 1씩 감소시키면서 반복한다. 위의 법칙에 드모르간 법칙을 이용하면 아래의 두 조건을 모두 성립해야 한다.
- j가 0보다 큼
- a[j -1]값이 tmp보다 큼
시간 복잡도는 O(n²)이다.
*셸 정렬
셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬로 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행하고 합치는 정렬이다.
<그림 11>은 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나우어 정렬한 ‘4-정렬’이다. 아직 정렬을 마친 상태는 아니지만 정렬을 마친 상태에 가까워졌다.
정렬되지 않은 상태의 배열에서 ‘4-정렬’, ‘2-정렬’로 정렬이 된 상태에 가까운 배열로 만든 다음 단순 삽입 정렬을 수행하여 정렬을 마친다.
증분값(h값)을 선택할 때는 주의해야 할 게 있다. 증분값을 잘못 설정해야 할 경우 그룹을 나누더라도 정렬 알고리즘이 작동하지 않는다.
- 1부터 시작하여 3배한 값에 1를 더한 값(1, 4, 13, 40…)
- h 초깃값이 요소 개수 n을 9로 나눈 값을 넘지 않아야 한다.
*퀵 정렬
퀵 정렬은 배열 중에서 그룹을 나누는 기준(피벗)을 정하고 다른 요소를 기준에 따라 그룹을 나누는 작업을 반복하여 정렬하는 것이다.
<그림 14>는 퀵 정렬 중 처음 그룹을 나누는 과정이다. 피벗 이하의 요소들과 피버 이상의 요소들을 각각 이 작업을 반복하면 정렬을 할 수 있다.
<그림 15>는 재귀 알고리즘을 써서 퀵 정렬을 구현했다. 퀵 정렬을 비재귀적으로 구현하기 위해서는 스택을 이용하면 된다.
lstack와 rstack스택에 푸시한 처음 푸시한 값은 각각 ‘첫 요소’와 ‘끝 요소’의 인덱스이다. 배열을나누는 작업이 끝나면 왼쪽 그룹 인덱스를 lstack에 오른쪽 그룹 인덱스를 rstack에 푸시한다. 스택이 비면 정렬이 끝난다.
인덱스를 푸시할 때 어떤 것을 먼저 푸시하는지에 따라 스택의 용량이 달라진다.
- 요소의 개수가 많은 그룹을 먼저 푸시하는 경우
- 요소의 개수가 적은 그룹을 먼저 푸시하는 경우
<그림 17>, <그림 18>을 비교해보면 스택에 넣고 꺼내는 횟수는 같지만 스택에 쌓여 있는 데이터의 최대 개수가 다르다. 퀵 정렬의 시간 복잡도는 O(n log n)이고 최악의 시간 복잡도는 O(n²)이다.
qsort 함수를 사용한 정렬
qsort함수의 인자로 전달하는 값은 총 4개이다. base는 정렬할 배열, nmemb는 요소의 개수, size는 요소의 크기, 마지막 compar는 비교함수이다.
<그림 20>을 이용하면 오름차순으로 배열을 정렬할 수 있다.
*병합 정렬
병합 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하는 정렬이다.
<그림 21>은 정렬을 마친 배열 a,b 를 비교하여 작은 값을 꺼내 c에 넣은 것이다.
<그림 22>는 앞부분과 뒤부분을 나누어 가가 정렬한 후 병합하는 과정이다.
병합 정렬 알고리즘의 순서는 배열의 요소 개수가 2개 이상인 경우 배열의 앞 부분과 뒤부분을 각각 정렬한 후 배열의 앞부분과 뒤 부분을 병합하는 것이다.
병합 정렬의 시간 복잡도는 O(n log n)이다.
*힙 정렬
힙 정렬은 힙(heap)의 특성을 이용한 정렬이다. 힙은 ‘부모의 값이 자식의 값보다 항상 크다(항상 작다)’라는 조건을 만족하는 완전이진트리를 말한다.
부모와 자식의 인덱스 사이에는 다음과 같은 관계가 성립한다.
- 부모는 a[(i-1) / 2]
- 왼쪽 자식은 a[i*2 + 1]
- 오른쪽 자식은 a[i*2 + 2]
힙에서 가장 큰 값을 트리라고 한다.(<그림 24>에서는 10)
배열로 힙 정렬을 하려면 아래의 과정을 반복하면 된다.
- 루트를 정렬되지 않은 부분의 마지막 요소와 교환한 후 정렬된 부분으로 정리한다.
- 정렬되지 않은 부분을 힙 상태로 바꾼다.
부모가 자식보다 작아 힙이 아닌 상태에서는 부모를 두 자식 중에 큰 값과 바꾸어 힙 상태로 만들면 됩니다.
힙 정렬의 시간 복잡도는 O(n log n)이다.
*도수 정렬
도수 정렬은 요소의 대소 관계를 비교하지 않고 정렬할 수 있는 알고리즘이다. 도수 정렬은 도수분포표와 누적도수분포표르 이용하여 정렬을 한다. 도수 정렬은 4단계로 구분 지을 수 있다.
- 도수분포표 마들기
- 누적도수분포표 만들기
- 목적 배열 만들기
- 배열 복사하기
1단계 도수분포표 만들기
먼저 ‘각 점수에 해당하는 학생이 몇 명인지’를 나타내는 도수분포료를 작성해야한다. 배열 a는 각 학생의 점수, 배열 f는 도수분포표를 나타내기위한 것이다. 배열 f의 모든 요소를 0으로 초기화 시킵니다.
2단계 누적도수분포표 만들기
이제 ‘0점부터 점수 n까지 몇 명의 학생이 있는지’ 누적된 값을 나타내는 누적도수분포표를 만든다. f[i] += f[i-1]를 이용하면 된다.
이 과정을 마치면 배열 f는 도수분포표가 아닌 누적도수분포표롤 바뀐다.
3단계 목적 배열 만들기
배열의 각 요솟값과 누적도수분포표 f를 대조하여 정렬을 마친 배열로 만드는 작업이 3단계이다. 이 작업은 작업용 배열 b가 필요하다. 이 작업은 배열 a의 마지막 요소부터 처음 요소로 해야 안정적으로 정렬을 완성할 수 있다.
마지막 요소(a[8])의 값은 3이다. 누적도수를 나타내는 배열(f[3])의 값이 5이므로 0~3점 사이에 5명이 있음을 알 수 있다. 목적 배열인 b[4]에 3을 저장한다. 이와 같은 과정을 반복하면 목적 배열을 만들 수 있다.
4단계 배열 복사하기
배열 a는 정렬되기 전인 상태이고 배열 b는 배열 a가 정렬된 상태이다. 그러므로 배열 b의 값을 배열 a로 복사해야 한다.
