정렬
- 삽입 정렬 응용
삽입 정렬의 알고리즘에 대해 간단히 요약해보면
자료 배열의 모든 요소를 앞에서부터 차례로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입하는 것이다.
삽입 정렬 알고리즘의 구체적 아이디어
삽입 알고리즘은 리스트 내에서 정렬된 부분과 아직 정렬되지 않은 부분으로 나뉜다.
그래서 반복문을 두번 사용하는 것이 보편적인데
일단 전체 자료를 탐색하기 위한 포문을 하나 만들고
그 내부에 현재 비교할 자료를 정렬된 부분에 끼워주기 위한 반복문을 만들어준다.
2. 소스코드
while
int* Insertion_sort(int* random_data, int n) {
for (int i = 1; i < n; i++) {
int key = random_data[i];
int index = i - 1;
while ((index >= 0) && (random_data[index] > key)) {
random_data[index + 1] = random_data[index];
index = index - 1;
}
random_data[index + 1] = key;
}
return random_data;
}for
int* Insertion_sort(int* random_data, int n) {
int i, j;
for (i = 1; i < n; i++) {
int key = random_data[i];
for (j = i - 1; j >= 0 && random_data[j] > key; j--) {
random_data[j + 1] = random_data[j];
}
random_data[j + 1] = key;
}
}- 삽입정렬의 수행시간
best case
각 부분에 대해 한번씩만 탐색해보면 되므로 n 만큼의 시간이 걸린다.
worst case
입력이 내림차순으로 주어질 경우
외부 반복문:
n-1 번
내부 반복문 :
1 + 2 + .... + (n-2) + (n-1) 번
=> n(n - 1) / 2 = O(n^2) 번 이루어 진다.
- 장 단점
구현이 쉬운 편에 속하는 정렬 법이며 정렬을 위한 비교횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 교환이 일어나야 하는 자료의 상태에서 효율적으로 사용할 수 있다. 만약 자료가 정렬된 값이라면 교환이 일어나지 않고 N-1 만큼의 비교만 일어난다.
하지만 시간 복잡도가 O(N^2) 이므로 시간이 오래걸리는 정렬 방식이다.
퀵 정렬
퀵 정렬에 핵심 개념은 분할, 정복, 피봇, L, R 이다.
분할 : 정렬할 자료들을 기준 값을 중심으로 좌, 우 2개의 부분집합으로 나누는 것이다.
정복 : 부분 집합의 원소들 중에서 기준 값보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽 부분 집합으로 정렬하는 과정이다.
부분 집합의 크기가 더이상 나눌 수 없을 때 까지 분할, 정복의 과정이 반복된다.
퀵정렬을 구성하는 방법은 두가지가 있는데
리스트의 중간을 pivot 을 두는 방법 리스트의 첫번째 요소를 pivot 으로 두는 방법이 있다.
1.리스트의 첫번째 요소를 pivot 으로 두는 방법
퀵 정렬의 구체적 아이디어에 대해 간단히 요약해 보면
- pivot 보다 작은 요소들은 모두 pivot의 왼쪽으로 옮겨지고 pivot 보다 큰 요소들은 모두 .pivot의 오른쪽으로 옮겨진다.
- 결과적으로 pivot 을 중심으로 왼쪽은 pivot 보다 작고, 오른쪽은 pivot 보다 큰 요소들로 구성이 된다.
그렇다면 어떻게 왼쪽 부분 리스트와 오른쪽 부분 리스트를 정렬할까?
- 순환 호출을 이용하여 정렬을 반복한다.
- 부분 리스트에서도 다시 pivot 을 정하여 부분 부분의 과정을 반복한다.
2. 소스코드
int partition(int ary[], int left, int right) {
int pivot, low, high;
pivot = left;
low = left + 1;
high = right;
while (1) {
while ((ary[low] <= ary[pivot]) && (low <= high)) {
low++;
}
while ((ary[high] > ary[pivot]) && (low <= high)) {
high--;
}
if (low > high) {
break;
}
swap(&ary[low], &ary[high]);
}
swap(&ary[left], &ary[high]);
return high;
}
void quick_sort(int ary [], int left, int right) {
if (left < right) {
int q = partition(ary, left, right);
quick_sort(ary, left, q - 1);
quick_sort(ary, q+1, right);
}
}수행시간
n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n) 이라고 할 때
퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀호출이 이루어지는데
부분인 S(n) 을 다 합하였을 때 log n 이 나오고 T(n) = n log n 이 된다.
분할 되는 횟수를 k 라 가정하였을 때
k = log 2 n 계속 분할 하므로
최종적으로 요소들의 개수만큼 진행하게 되므로 nlog2 n 이 된다.
최악의 시작 복잡도인 O(n^2) 이 나오는 상황은 데이터가 정렬되어있거나 역순으로 정렬되어 있을 때 이다.
장단점
속도가 빠르다 또한 추가적인 메모리 공간을 필요로 하지 않는다.
하지만 만약 리스트가 계속 불균형 하게 나뉘는 경우 (특히, 이미 정렬된 리스트에 대하여 퀵 정렬이 일어나는 경우)에는 최악의 시간 복잡도를 보여주게 된다.
이럴 때에는 자료의 중앙값을 찾아 중앙에 정렬해주는 방법이 사용될 수 있다.
약간의 코드만 추가하여 성능을 높일 수 있다.