특정한 값을 기준으로 큰 숫자와 작은 숫자를 반으로 나눈다
항상 피봇 값은 집합의 첫번째 원소(가장 왼쪽에 위치해있음)인 노란색으로 설정한다. 피봇 값을 기준으로 왼쪽에서 오른쪽으로 움직이면서 피봇보다 큰 자료를 찾는 left와 오른쪽 끝에서 왼쪽으로 움직이며 피봇보다 작은 자료를 찾는 right를 사용한다. 단, left는 right까지 이동할 수 없고, right는 left보다 더 왼쪽으로 이동할 수 없다. 피봇보다 큰 값과 작은 값을 찾았으면 두 값을 교환해준다. left나 right이 더 이상 움직일 수 없을 때 해당 위치의 값과 피봇값을 교환해준다. 피봇값을 기준으로 왼쪽 부분은 피봇보다 작은 수들의 모임이고 오른쪽 부분은 피봇보다 큰 수들의 모임이다. 해당 시행을 왼쪽, 오른쪽 부분에 대해 다시 실행시켜준다.
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
void printArray(int value[], int count) {
int i = 0;
for (i = 0; i < count; i++) {
printf("%d ", value[i]);
}
printf("\n");
}
void quickSort(int value[], int start, int end) {
int pivot = 0;
if (start < end) {// 시작 위치와 끝 위치를 비교하여 퀵 정렬을 수행할지 결정한다. 시작위치가 끝 위치와 크거나 같다면 더 이상 퀵 정렬을 수행하지 않는다.
pivot = partitionQuickSort(value, start, end);
quickSort(value, start, pivot - 1);
quickSort(value, pivot + 1, end);
}
//분할 정복을 위해 리턴된 피봇 위치를 이용하여 왼쪽 부분 집합과 오른쪽 부분 집합에 대해 각각 함수 quickSort를 재귀적으로 호출한다.
}
int partitionQuickSort(int value[], int start, int end) {
int pivot = 0;
int temp = 0, left = 0, right = 0;
left = start;
right = end;
pivot = end;
//left와 right, pivot의 위치를 초기화 시킨다. 여기서는 pivot의 위치가 right와 동일하다.
while (left < right) {
//left가 right의 왼쪽에 있을 때 루프 실행
while (value[left] < value[pivot] && left < right) {
left++;
}
//left는 pivot값보다 큰 값을 찾기 위해 오른쪽으로 이동한다. 단, right보다 더 오른쪽으로 이동할 수 없다.
while(value[right] >= value[pivot] && left < right) {
right--;
}
//right는 pivot값보다 작은 값을 찾기 위해 왼쪽으로 이동한다. 단, left보다 더 왼쪽으로 이동할 수 없다.
if (left < right) {
temp = value[left];
value[left] = value[right];
value[right] = temp;
printf("start-[%d], end-[%d], pivot-[%d], in-loop", start, end, value[pivot]);
printArray(value, end - start + 1);
}
//left와 right의 위치가 적합하다면 두 자료의 위치를 교환한다.
}
//left와 right의 위치가 겹치면 pivot의 값과 right의 값을 교환한다.
temp = value[pivot];
value[pivot] = value[right];
value[right] = temp;
printf("start-[%d], end-[%d], pivot-[%d], out-loop", start, end, value[right]);
printArray(value, end - start + 1);
return right;//최종 위치 right을 반환한다.
}
int main() {
int values[] = { 80,50,70,10,60,20,40,30 };
printf("Before Sort\n");
printArray(values, 8);
quickSort(values, 0, 7);
printf("After Sort\n");
printArray(values, 8);
}
#include <stdio.h>
#pragma warning(disable:4996)
int number = 10;
int data[10] = { 1,10,5,8,7,6,4,3,2,9 };
void quickSort(int* data, int start, int end) {
if (start >= end) {//원소가 1개인 경우
return;
}
int key = start;//키는 첫번째 원소
int i = start + 1;//왼쪽 출발지점
int j = end;//오른쪽 출발지점
int temp;
while (i <= j) {//엇갈릴 때까지 반복
while (data[i] <= data[key]) {//키 값보다 큰 값을 만날 때까지
i++;
}
while (data[j] >= data[key]&&j>start) {//키 값보다 작은 값을 만날 때까지 + 오른쪽으로 넘어가지 않도록 범위 설정(기준값이랑 오른쪽 값을 바꿈)
j--;
}
if (i > j) {//현재 엇갈린 상태면 키 값과 교체
temp = data[j];
data[j] = data[key];
data[key] = temp;
}
else {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
int i, j;
quickSort(data, 0, number - 1);
for (i = 0; i < number; i++) {
printf("%d ", data[i]);
}
}
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_SIZE 10
#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
int list[MAX_SIZE];
int n;
int partition(int list[], int left, int right) {
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left];
do {
do {
low++;//low는 left+1에서 출발, do-while루프에서 먼저 증가를 시킴
} while (list[low] < pivot);
do {
high--;//high는 right에서 출발, do-while 루프에서 먼저 감소를 시킴
} while (list[high] > pivot);
if (low < high)
SWAP(list[low], list[high], temp);
} while (low < high);
SWAP(list[left], list[high], temp);
return high;
}
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");
}
void qsort(void* base, size_t num, size_t width, int(*compare)(const void*, const void*));
일반적인 구조체 배열을 정렬하기 위하여 제작됨
void* base: 배열의 시작주소
size_t num: 배열 요소의 개수
size_t width: 배열 요소 하나의 크기(바이트 단위)
int (compare) (const void, const void*): 포인터를 통하여 두 개의 요소를 비교하여 비교 결과를 정수로 반환하는 함수