12.1 정렬이란?
12.2 선택 정렬
12.3 삽입 정렬
12.4 버블 정렬
12.5 쉘 정렬
12.6 합병 정렬
12.7 퀵 정렬
12.8 히프 정렬
12.9 기수 정렬
12.10 정렬 알고리즘의 비교
12.11 정렬의 응용: 영어 사전을 위한 정렬
12.1 정렬
정렬
- 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것 (자료 탐색에서 필수!)
- 정렬 대상 => 일반적으로 레코드(record) ( 예를 들면 학생들이 레코드면, 학번 이름 등이 필드)
- 레코드는 필드라는 보다 작은 단위로 구성되고 키필드(이름 등)로 레코드와 레코드를 구별
- 모든 경우에 최적인 정렬 알고리즘은 X
- 정렬 알고리즘 평가 기준 => 비교 횟수 빈도, 이동 횟수 빈도 (빅오표기법으로)
분류1
- 단순, 비효율 => 삽입 정렬 , 선택 정렬 , 버블정렬
- 복잡, 효율 => 퀵정렬 , 히프정렬 , 합병정렬 , 기수정렬
분류2
- 내부 정렬 : 모든 데이터가 주기억장치에 저장된 상태에서 정렬 (여기서는 내부정렬만 다룸)
- 외부 정렬 : 외부기억장치에 대부분 데이터, 일부만 주기억장치에 저장된 상태에서 정렬
분류3
- 안정 O (같은 키 값 레코드들이 정렬 후에도 바뀌지 X) => 삽입 정렬 , 선택 정렬 , 합병정렬
- 안정 X => 선택 정렬, 히프 정렬
***in-place sorting 제자리 정렬: 입력 배열 이외에는 다른 추가 메모리를 요구하지 않는 정렬 방법
12.2 선택 정렬
선택정렬
- 정렬된 왼쪽 리스트와 정렬이 안 된 오른쪽 리스트 가정
- 초기에 왼쪽 0리스트 비어 있고, 정렬할 숫자들은 모두 오른쪽 리스트에
- 오른쪽 리스트에서 가장 작은 숫자 선택해서 왼쪽 리스트로 이동하는 작업 반복
선택정렬 알고리즘
| selection_sort(A,n) 1. for i<-0 to n-2 do 2. least <- A[i], A[i+1],..., A[n-1] 중에서 가장 작은 값의 인덱스; 3. A[i]와 A[least]의 교환; 4. i++; |
- i 값은 0~n-2까지만 변화되는 점. 왜냐면 만약 list[0]~list[n-1]까지 정렬 되어있으면 list[n-1]이 이미 가장 커서 n-1까지 정렬할 필요 X
선택정렬 코드
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t) ) //세번의 이동(교환)
int list[MAX_SIZE];
int n;
void selection_sort(int list[], int n)
{
int i,j,least,temp;
for (i=0; i<n-1; i++) //한 round마다 한 개의 record가 최종 정렬된 위치를 찾아 가면서, sorted/unsorted part 길이가 각각 1씩 증가/감소
least = i; //비교 횟수 = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)
for (j=i+1; j<n; j++) //최솟값 탐색
if (list[j] < list[least]) least = j;
SWAP(list[i], list[least], temp); //이동회수 = 3x(n-1)번의 swapping = O(n)
}
}
//main 함수
int main(void)
{
int i;
n = MAX_SIZE;
srand(time(NULL));
for (i=0; i<n; i++) //난수 생성 및 출력
list[i] = rand() % 100; //난수 발생 범위 0-99
selection_sort(list, n); //선택정렬 호출
for (i=0; i<n; i++)
printf("%d", list[i]);
printf("\n");
return 0;
}
결과:
16 24 25 38 48 64 87 90 93 96
**만일 정렬해야할 데이터 셋이 이미 원하는 순서로 정렬되어 있어도 swapping(이동) 발생. 아래 if 문 추가하면 됨
즉. 최소값이 자기 자신이면 자료이동 X
if ( i != least)
SWAP(list[i], list[least], temp);
선택정렬 복잡도 분석
- 비교 횟수(= 내부루프 실행 횟수) : (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)
- 이동 횟수(= 외부루프 실행 횟수) : 3(n-1)
- 전체 시간적 복잡도 : O(n^2) = 비교횟수 + 이동횟수 한 것
- 안정성 만족 X. 같은 레코드가 있는 경우에 상대적인 위치 변경 가능 ( unstable, in-place sort )
- 메모리 사용 최소화 (고정된 양의 추가 메모리만 필요 ) ==> 공간 복잡도 : O(1)
12.3 삽입정렬
삽입정렬 (insertion sort)
- 정렬되어 있는 부분에 새로운 레코드를 정렬이 유지되는 위치에 삽입 반복
삽입정렬 알고리즘
| insertion_sort(A, n) //오름차순 1. for i<-1 to n-1 do //A[0]은 기정렬된 것으로 간주하여 A[1]부터 시작 2. key <- A[i]; 3. j <- i-1; //#3~#6 sorted part에서 A[i]가 순서있게 놓일 위치 찾는 과정 4. while j ≥ 0 and A[j] > key do 5. A[j+1] <- A[j]; //key값이 들어갈 자리를 확보하기 우함 6. j <- j-1; //하나 더 앞에 것과 비교 7. A[j+1] <- key //while문에서 exit 할 때 마지막으로 비교된 element가 A[j] (0<=j<=i-1)이고 비어있는 element는 A[j+1] |
(i=5) round에서
(1) 만일 A[5]=key가 A[4]보다 크다면... j가 4이므로 하나 증가시켜 원래자리 A[5]에 key 값 저장
(2) 만일 A[5]=key가 A[0]보다 작다면... j가 -1이므로 하나 증가시켜 A[0]에 key값 저장
삽입정렬 코드
//삽입정렬
void insertion_sort(int list[], int n)
{
int i, j, key; //추가 공간은 변수(key) 하나. 상수이므로 공간복잡도 O(1)
for (i=1; i < n; i++)
{
key = list[i];
for (j=i-1; j>=0 && list[j] > key; j--)
list[j+1] = list[j]; //레코드의 오른쪽 이동
list[j+1]=key;
}
}
삽입정렬 복잡도 분석
(Inner for문 복잡도는 n 나눈 것 )
- 최선 : O(n) --->> 이미 정렬되어 있는 경우
ㄴ 비교 n-1번 **바로 앞의 것과 1회씩만 비교
ㄴ 이동 2(n-1) (2번의 이동.)
- 최악 : O(n^2) --->> 역순으로 정렬되어 있는 겨우
ㄴ모든 단계에서 앞에 놓인 자료 전부 이동
ㄴ 비교: 1+2+ .... + (n-1) = n(n-1)/2 = O(n^2)
ㄴ이동: n(n-1)/2 + 2(n-1) = O(n^2)
- 평균 : O(n^2) **small datasets에 적합
- 많은 이동 필요 -> 레코드가 크면 불리
- 안정된 정렬방법
- 대부분 정렬되어 있으면 효율적
- **in-place sort 메모리 사용 최적화(고정된 양의 추가 메모리만 필요) ==> 공간복잡도 O(1)
12.4 버블 정렬
버블정렬
- 인접한 2개의 레코드 비교하여 순서대로 되어 있지 않으면
서로 교환
- **In each round, unsorted part에서 가장 큰 record가 최종 위치를 찾아 감 (여기서는 8). 마치 거품 보글보글 같다.
버블정렬 알고리즘
| BubbleSort(A, n) 1. for i<-n-1 to 1 do 2. for j<-0 to i-1 do 3. j와 j+1번째의 요소가 크기 순이 아니면 교환 4. j++; 5. i--; |
버블정렬 코드
#define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t) )
void bubble_sort(int list[], int n) //오름차순
{
int i,j,temp;
for (i=n-1; i>0; i--)
{
for (j=0; j<i; j++) //앞뒤의 레코드를 비교한 후 교체
if (list[j] > list[j+1])
SWAP(list[j], list[j+1], temp); //3회 이동 연산
}
}
버블 정렬 복잡도 분석
- 비교 횟수 (최상, 평균, 최악 모두 일정) :1+2+...+(n-1) = n(n-1)/2 = O(n^2)
- 이동 횟수
ㄴ 최악 - 역순으로 정렬된 경우 이동 횟수 = 3 (swap이 3개 이동이라)* 비교 횟수
ㄴ 최선 - 이미 정렬된 경우(이동 한 번도 발생X) = 이동 횟수 = 0
ㄴ 평균 - O(n^2)
- 레코드의 이동 과다 : 이미 정렬 위치에 있어도 교환되는 일잉 일어남. 이동연산은 비교연산보다 더 많은 시간 소요
===>> 부분적으로 정렬된 데이터셋에서 더 효율적, small datasets에 적합, stable-sort, simplicity
12.5 쉘 정렬
셀 정렬
- 삽입정렬이 어느 정도 정렬된 배열에서 대단히 빠른 것에 착안. (삽입 정렬은 이웃한 위치로만 이동하므로, 많은 이동에 의해서만 제자리 찾아감)
-> 요소들이 멀리 떨어진 위치로 이동 -> 적게 이동하여 제자리 찾을 수 있음
- 전체 리스트를 일정 간격(gap)의 부분 리스트로 나눔
==> 나뉘어진 각각의 부분 리스트를 삽입정렬
그 후 간격을 1/2 줄여서 다시. 마지막은 간격 1
셀 정렬 프로그램
//gap 만큼 떨어진 요소들을 삽입정렬
//정렬의 범위는 first에서 last
inc_insertion_sort (int list[], int first, int last, int gap)
{
int i, j, key;
for (i=first+gap; i<=last; i=i+gap) {
key = list[i];
for (j=i-gap; j>=first && key<list[j]; j=j-gap)
list[j+gap] = list[j];
list[j+gap] = key;
}
}
//
void shell_sort (int list[], int n) //n=size
{
int i, gap;
for (gap=n/2; gap>0; gap=gap/2) {
if ((gap%2)==0)
gap++;
for (i=0; i<gap; i++) //부분 리스트의 개수는 gap
inc_insertion_sort(list, i, n-1, gap);
}
}
셀 정렬 복잡도 분석
- 셀 정렬 장점 ⓛ : 불연속적인 부분 리스트에서 원거리 자료 이동으로 보다 적은 위치교환 가능성 증가 (삽입정렬은 한칸씩만 이동 ㅜ)
- 셀 정렬 장점 ② : 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입정렬 속도 증가
- 시간 복잡도 ***gap(간격)에 많은 영향
ㄴ 최악 : O(n^2)
ㄴ 평균 : O(n^1.5)
-**stable sort, in-place sort -> space complextity = O(1)
12.6 합병 정렬
합병 정렬 ( merge sort )
- 리스트를 두개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬
- 정렬된 두 개의 부분 리스트를 합하여 전체 리스트를 정렬
(divide and conquer 분할 정복 기법에 바탕)
합병정렬 알고리즘
| 1. 분할 (Divide) : 배열을 같은 크기의 2개의 부분 배열로 분할 2. 정복 (Conquer) : 부분 배열을 정렬.(합병 정렬 순환 적용) 부분 배열 크기가 충분히 작지 않으면... 재귀호출로 다시 분할 정복기법 적용 3. 결합 (Combine) : 정렬된 부분배열을 하나의 배열에 통합 ( 이 단계에서 정렬 수행!! ) merge_sort(list, left, right) : 1. if left < right 2. mid = (left + right) / 2; 3. merge_sort(list, left, mid); ==> 분할 4. merge_sort(list, mid+1, right); ==> 분할 5. merge(list, left, mid, right); ==> 합병 |
합병 알고리즘
//합병 알고리즘
merge(list, left, mid, right):
//2개의 인접한 배열 list[left..mid]와 list[mid+1..right]를 합병
i<-left;
j<-mid+1;
k<-left;
sorted 배열 생성;
while i <= mid and j <= right do
if (list[i] < list[j] ) then
sorted[k]<-list[i];
k++;
i++;
else
sorted[k]<-list[j];
k++;
j++;
요소가 남아있는 부분배열을 sorted로 복사;
sorted를 list로 복사;**합병 중간 sorted 배열 C 필요. 배열 C는 임시 저장소이므로 원 배열 list[]에 copy해애 recursive call 이 제대로 수행
==>> 추가 공간 필요, not in-place , 공간 복잡도 O(n)
합병정렬 프로그램
int sorted[MAX_SIZE]; //추가 공간 필요
//i는 정렬된 왼쪽리스트에 대한 인덱스
//j는 정렬된 오른쪽리스트에 대한 인덱스
//k는 정렬될*** 리스트에 대한 인덱스
void merge(int list[], int left, int mid, int right)
{
int i,j,k,l;
i=left; j=mid+1; k=left;
while (i<=mid && j<=right) { //분할 정렬된 list의 합병
if (list[i] <= list[j]) sorted[k++] = list[i++]; //non-decreasing order -> 더 작은 것을 먼저 copy
else sorted[k++] = list[j++];
}
if (i > mid) //왼쪽 배열A는 모두 copy 되었다는 뜻
for (l=j; l<=right; l++)
sorted[k++] = list[l]; //혹시 오른쪽 배열B에 남은 것 있으면 for문 실행
else //남아 있는 레코드의 일괄 복사
for (l=i; l<=mid; l++) //혹시 왼쪽 배열A에 남은 것 있으면 for문 실행
sorted[k++] = list[l];
//배열 sorted[]의 리스트를 배열 list[]로 복사
for (l=left; l<=right; l++) //**sorted[]는 임시 저장소이므로 원 배열 list[]에 copy해야 recursive call이 제대로 수행
list[l] = sorted[l]; // |right-left|만큼의 이동 연산 -> O(n)
void merge_sort(int list[], int left, int right)
{
int mid;
if (left < right)
{
mid = (left+right)/2; //리스트의 균등분할
merge_sort(list, left, mid); //부분리스트 정렬
merge_sort(list, mid+1, right); //부분리스트 정렬
merge(list, left, mid, right); //합병
}
}**만일 record 개수가 33개인 dataset을 merge sort하면 merge() 함수는 총 몇번 호출?
recursive call 횟수는 log(n), n=dataset 크기 ( or 정렬하고자 하는 record 개수)
합병정렬 복잡도 분석
merge 함수에서 비교 연산과 이동연산이 수행되는 것.
- 비교 횟수 :
크기 n 리스트 균등분배이므로(2^3->2^2->2^1->2^0) log(n)개의 레벨 + 각 레벨에서 모든 레코드 n개 비교하므로 n번 비교 연산 ==>> 최대 nlog2(밑)의 n(지수)번 필요
- 이동 횟수 :
레코드의 이동이 각 패스에서 2n번 발생 ==> 전체 레코드 이동은 2n*log(n)번 발생
ㄴ 레코드 크기가 크면 매우 큰 시간적 낭비 / 레코드를 연결리스트로 구성하여 합병 정렬하면 매우 효율적
- 최적, 평균, 최악 모두 차이 없이 O(n*log(n))의 복잡도
- 안정적, 데이터 초기 분산 분포에 영향 ↓ ↓ ↓
- not in-place, 공간 복잡도 O(n)
12.7 퀵 정렬
퀵 정렬 ( quick sort )
- 평균적으로 가장 빠른 정렬 방법
- 분할정복법 사용
- 합병 정렬과 달리 리스트를 2개의 부분리스트로 비균등 분햘 -> 각각 부분리스트 다시 퀵정렬(재귀호출)
- **how to choose pivot? => 가능하면 선택된 pivot에 의해 얻어진 부분리스트의 길이가 비슷하도록. 즉, unsorted list 내 key들 중 중간 값
퀵 정렬 알고리즘
| void quick_sort(int list[], int left, int right) { if (left < right) { int q = partition(list, left, right); quick_sort(list, left, q-1); quick_sort(list, q+1, right); } } |
퀵 정렬 코드
int partition (int list[], int left, int right) //int q = partition(list, left, right);
{
int pivot, temp;
int low, high;
low = left;
high = right+1;
pivot = list[left]; //현 리스트의 가장 왼쪽 record의 key가 pivot
do {
do
low++;
while (low <= right && list[low] < pivot);
do
high--;
while (high >= left && list[high] > pivot);
if (low < high) SWAP(list[low], list[high], temp); //이때 high값이 pivot이 들어갈 자리이며 그 자리가 pivot 값의 최종자리!!
} while (low < high); //if high < low then NO swapping and Done!
SWAP(list[left], list[high], temp; //pivot(list[left])을 정렬된 자리로~!
return high; //pivot이 정렬된 index를 반환
}
void quick_sort(int list[], int left, int right)
{
if (left < right)
{
int q = partition(list, left, right);
quick_sort(list, left, q-1);
quick_sort(list, q+1, right);
}
}
int main(void)
{
int i;
n = MAX_SIZE;
srand(time(NULL));
for (i=0; i<n; i++) //난수 생성 및 출력
list[i] = rand()%100;
quick_sort(list, 0, n-1) //퀵 정렬 호출
for (i=0; i<n; i++)
printf("%d", list[i]);
printf("\n");
return 0;
}실행결과 : 16 24 25 38 49 64 87 90 93 96
퀵 정렬 복잡도 분석
- 최선 (거의 균등한 리스트로 분할한다고 가정)
ㄴ 패스 수 : log(n)
ㄴ 각 레벨에서 비교횟수: n
ㄴ 총 비교횟수 : n*log(n)
ㄴ 총 이동횟수 : 비교횟수에 비해 적으므로 무시 가능
ㄴ **만일 pivot을 잘 정해서 두 sub list가 유사한 크기로 분할되면 quick_sort() 함수의 총 호출횟수는 O(logn)
- 최악 (극도로 불균등한 리스트로 분할)
ㄴ 레벨 수 : n
ㄴ 각 레벨 안 비교횟수: n
ㄴ 총 비교횟수 : n^2
ㄴ 총 이동횟수 : 무시 가능
ㄴ **만일 pivot을 잘못 정해서 항상 두 sub list 중 하나의 크기가 1이면 quick_sort() 함수의 총 호출횟수는 O(n)
- 중간값을 피벗으로 선택하면 불균등 분할 완화 가능
- 한번 선택된 pivot은 최종 자리 찾고 아후, 연산에서 배제
- 불필요한 데이터 이동 줄임 (fast and no extra memory needed)
-**fast, no extra memory needed, in-place sort algorithm
12.9 기수정렬
기수정렬 (Radix Sort)
- 대부분의 정렬 방법들은 레코드들을 비교함으로써 정렬 수행
- but 기수 정렬은 레코드를 비교하지 않고 정렬 수행
(비교 연산 전혀 사용하지 않음~!)
- O(dn)의 시간복잡도 가짐
(d:key값이 숫자인 경우, 자리수)
+ 추가적인 메모리를 필요
기수(radix) : 숫자의 자리수 (단계의 수는 자리수의 개수와 일치)
- 한자리수 기수정렬 : 단순히 자리수에 따라 버켓에 넣었다가 꺼내면 정렬
- 두자리수 기수정렬 : 낮은 자리수로 먼저 분류한 다음 다시 높은 자리수로 분류
***추가 공간 필요. not in-place
기수정렬 알고리즘
| RadixSort(list, n): 1. for d<-LSD의 위치 to MSD의 위치 do { 2. d번째 자리수에 따라 0번부터 9번 버켓에 넣는다 3. 버켓에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다 4. d++; 5. } //LSD (Least Significant Digit) 가장 낮은 자리수 <-> MSD (Most) |
- 버켓은 큐로 구현 (먼저 들어간 숫자들이 먼저 나와야 함)
- 버켓의 개수는 키의 표현 방법과 밀접한 관계 (알파벳문자면 버켓 26개)
- 패스의 개수는 자리 개수(d)에 밀접한 관계
기수정렬 프로그램
//6장의 큐 소스를 여기에...
#define BUCKETS 10 //한 자리가 0~9까지 10가지로 표현되므로 bucket 수는 10
#define DIGITS 4 //key가 4자리 수
void radix_sort(int list[], int n)
{
int i, b, d, factor=1;
QueueType queues[BUCKETS];
for (b=0; b<BUCKETS; b++) //bucket만큼의 큐들의 초기화
init(&queues[b]); //큐들의 초기화
for (d=0; d<DIGITS; d++) { //낮은 자리수부터 정렬!
for (i=0; i<n; i++) //전체(n) 데이터들을 자리수에 따라 큐에 입력
enqueue(&queues[(list[i]/factor) % 10], list[i]); //%10은 끝자리 반환
for (b=i=0; b<BUCKETS; b++) //버켓에서 꺼내어 list로 합침
while (!is_empty(&queues[b]))
list[i++] = dequeue(&queues[b]); //한 패스 정렬됨
factor *= 10; //그 다음 자리수로 간다 d가 +1 => factor는 X10
} //(outer for)d번 반복 X (inner for)n번 반복 => O(dn)
}
//define SIZE 10
int main(void)
{
int list[SIZE];
srand(time(NULL));
for (int i=0; i<SIZE; i++) //난수 생성 및 출력
list[i] = rand()%100;
radix_sort(list, SIZE); //기수정렬 호출
for (int i=0; i<SIZE; i++)
printf("%d", list[i]);
printf("\n");
return 0;
}실행 결과: 22 38 71 76 81 83 89 94 97 98
기수정렬 복잡도 분석
- n개의 레코드, d개의 자릿수로 이루어진 키를 기수 정렬할 경우
ㄴ 메인 루프는 자릿수 d번 반복 / 큐에 n개의 레코드 입력 수행
- O(dn)의 시간적 복잡도 (d는 아주 작아서 O(n)이라고 해도 됨)
ㄴ 키의 자릿수 d는 10이하의 작은 수이므로 빠른 정렬
(실수, 한글, 한자로 이루어진 키는 정렬X 숫자만 가능)
***not in-place
12.10 정렬 알고리즘 비교
'Study > Data Structure' 카테고리의 다른 글
| 자료구조 전체 (0) | 2023.12.08 |
|---|---|
| [자료구조 스터디] chap.13 탐색 (0) | 2023.12.01 |
| [자료구조 스터디] chap.10 그래프 I (0) | 2023.11.20 |
| [자료구조 스터디] chap.11 그래프 II (0) | 2023.11.16 |
