퀵 정렬(Quick Sort)
삽입 정렬은 아주 좋은 평균 정렬 성능을 가지는 정렬 알로리즘이다.
퀵 정렬은 피벗을 정하고 왼쪽과 오른쪽에서 각각 시작하여 왼쪽부터는 피벗이 크거나 같으면, 오른쪽에서는 피벗보다 작거나 같으면 두 값을 스왑 해주고, 오른쪽 값과 왼쪽값이 서로 교차할때 새로운 피벗을 설정하여 이 작업을 재귀적으로 실행하는 방법이다.
pivot 26이라고 가정하면 26보다 37 크니 멈추고 19가 피벗보다 작으니 멈추면 둘이 교환한다.
그리고 61 과 15 가 되면 스왑하고 둘이 교차하여 피벗과 right를 스왑해준다. 이 과정을 반복한다.
void quickSort(element a[], int left, int right)
{
int pivot, i, j;
element temp;
if (left < right) {
i = left; j = right + 1;
pivot = a[left].key; //피벗 설정
do {
do i++; while (a[i].key < pivot); //왼쪽 키값과 오른쪽 키값을 찾을때 까지 증가
do j--; while (a[j].key > pivot); // 감소 한뒤
if (i < j) SWAP(a[i], a[j], temp); // 두 값을 스왑하여 정렬
} while (i < j); //i와j가 교차할 때까지
SWAP(a[left], a[j], temp); //left와 j를 스왑해준다.
quickSort(a, left, j - 1); //재귀적으로 수행
quickSort(a, j + 1, right);
}
}시간 복잡도
평균 복잡도는 O(nlogn)
최악의 경우 O(n^2) --> 이미 정렬된 상태일 때
실습 예제
주어진 데이터를 읽어 Quick Sort를 수행하라.
1) 입력 데이터는 다음과 같은 형식을 가지는 파일(input.txt)로부터 입력받는다.
N R 1,1 R 1,2
R 2,1 R 2,2
…
R N,1 R N,2
N: Record의 갯수이며, N≤1000라 가정한다.. Ri, j 는 정수이며, i번째 Record의 j번 field를 나타낸다.
2) Quick Sort를 이용하여 두개의 Key(K 1 , K 2 )에 대해 각각 오름 차순으로 정렬한다.
입력값
input.txt
8
-1 5
31 4
95 -9
82 3
1984 124
-78 -42
0 -154
525 195
코드
/*
Description : Qucik Sort 구현
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct array
{
int key1;
int key2;
}array;
void open();
void Swap(array[], int, int);
void QuickSort_key1(array[], int, int);
void QuickSort_key2(array[], int, int);
void Printarr(array[], array[]);
void Init(array[], array[]);
array *matric;
int N;
int main(void)
{
open();
array *temp1, *temp2;
temp1 = (array*)malloc(sizeof(array) * N);
temp2 = (array*)malloc(sizeof(array) * N);
Init(temp1, temp2); //초기화
printf("Quick Sort\n");
QuickSort_key1(temp1, 0, N - 1);
QuickSort_key2(temp2, 0, N - 1);
Printarr(temp1, temp2);
return 0;
}
void open()
{
FILE *fp = fopen("input.txt", "r");
fscanf(fp, "%d", &N);
matric = (array*)malloc(sizeof(array) * N);
int i = 0, j = 0;
while (fscanf(fp, "%d %d", &matric[i].key1, &matric[i].key2) != EOF)
i++;
fclose(fp);
}
void Init(array *temp1, array *temp2)
{
for (int i = 0; i < N; i++)
{
temp1[i] = matric[i];
temp2[i] = matric[i];
}
}
void Swap(array arr[], int a, int b)
{
array temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void QuickSort_key1(array arr[], int left, int right)
{
int pivot, low, high;
if (left < right)
{
pivot = arr[left].key1; // 피벗의 위치는 왼쪽으로 지정
low = left + 1; high = right;
while (low <= high) // 교차되기 전까지 반복
{
while (pivot >= arr[low].key1 && low <= right) // 피벗보다 큰값을 찾음
low++; // low를 오른쪽으로 이동
while (pivot <= arr[high].key1 && high >= (left + 1)) //피벗보다 작은값을 찾음
high--; // high을 왼쪽으로 이동
if (low <= high) // 교차되지 않은 상태이면
Swap(arr, low, high);
}
Swap(arr, left, high); //피벗과 high의 교환
QuickSort_key1(arr, left, high - 1);
QuickSort_key1(arr, high + 1, right);
}
}
void QuickSort_key2(array arr[], int left, int right)
{
int pivot, low, high;
if (left < right)
{
pivot = arr[left].key2; // 피벗의 위치는 왼쪽으로 지정
low = left + 1; high = right;
while (low <= high) // 교차되기 전까지 반복
{
while (pivot >= arr[low].key2 && low <= right) // 피벗보다 큰값을 찾음
low++; // low를 오른쪽으로 이동
while (pivot <= arr[high].key2 && high >= (left + 1)) //피벗보다 작은값을 찾음
high--; // high을 왼쪽으로 이동
if (low <= high) // 교차되지 않은 상태이면
Swap(arr, low, high);
}
Swap(arr, left, high); //피벗과 high의 교환
QuickSort_key2(arr, left, high - 1);
QuickSort_key2(arr, high + 1, right);
}
}
void Printarr(array arr[], array arr2[])
{
printf("Key : K1\n");
for (int i = 0; i < N; i++)
printf("%d %d\n", arr[i].key1, arr[i].key2);
printf("\nKey : K2\n");
for (int i = 0; i < N; i++)
printf("%d %d\n", arr2[i].key1, arr2[i].key2);
}출력 값
정렬 관련 알고리즘