クイックソート

/*--- 퀵 정렬 (비재귀 버전) ---*/
/* 분할 범위(인덱스 양끝)를 Push, Pop */
void quick_sort(int a[], int left, int right)
{
	// 그룹의 첫 요소, 끝 요소 인덱스
	IntStack lstack, rstack;

	// 스택 초기화 
	Initialize(&lstack, right - left + 1); 
	Initialize(&rstack, right - left + 1); 
	
	Push(&lstack, left); Print(&lstack); // 맨 앞 인덱스
	Push(&rstack, right);  Print(&rstack); // 맨 뒤 인덱스

	while (!IsEmpty(&lstack)) { // 두 그룹으로 분할 마치면 종료(함수 호출 완료하면 Pop 되므로)
		// Pop하면 분할 시작
		int pl = (Pop(&lstack, &left), left); // Pop후 왼쪽 스택에 left 대입
		int pr = (Pop(&rstack, &right), right); // Pop후 오른쪽 스택에 rigjht 대입
		int x = a[(left + right) / 2]; // 중앙값

		/* 분할(partition) */
		do { 
			while (a[pl] < x) pl++;
			while (a[pr] > x) pr--;
			if (pl <= pr) {
				swap(int, a[pl], a[pr]);
				pl++;
				pr--;
			}
		} while (pl <= pr); // pl과 pr 교차시 종료(두 그룹으로 분할 마침)

		/* 스택의 최대 용량 줄이는 코드*/
		if (pr - left < right - pl) { // 오른쪽 요소의 개수가 더 많으면
		// 오른쪽 그룹 Push 먼저(요소가 작은 왼쪽 그룹 Pop 먼저도서 최대 스택 용량 줄어듬)
			swap(int, pl, left); // left는 pl, pl는 left
			swap(int, pr, right); // right는 pr, pr는 right
		}

		/* 그룹 분할 완료후 Push */
		if (left < pr) { // 왼쪽 그룹 푸쉬
			Push(&lstack, left); // 맨 첫 요소 
			Push(&rstack, pr);   // 맨 끝 요소 
		}
		if (right > pl) { // 오른쪽 그룹 푸쉬
			Push(&lstack, pl);	// 맨 첫 요소 
			Push(&rstack, right); // 맨 끝 요소 
		}
	}
	Terminate(&lstack); 
	Terminate(&rstack);
}

/* int형 스택 IntStack(헤더) */
#ifndef ___IntStack
#define ___IntStack

/*--- 스택을 구현하는 구조체 ---*/
typedef struct {
	int max;		/* 스택 용량 */
	int ptr;		/* 스택 포인터 */
	int* stk;		/* 스택의 첫 요소에 대한 포인터 */
} IntStack;

/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max);

/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x);

/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x);

/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack* s, int* x);

/*--- 스택 비우기 ---*/
void Clear(IntStack* s);

/*--- 스택의 최대 용량 ---*/
int Capacity(const IntStack* s);

/*--- 스택의 데이터 개수 ---*/
int Size(const IntStack* s);

/*--- 스택이 비어 있나요? ---*/
int IsEmpty(const IntStack* s);

/*--- 스택이 가득 찼나요? ---*/
int IsFull(const IntStack* s);

/*--- 스택에서 검색 ---*/
int Search(const IntStack* s, int x);

/*--- 모든 데이터 출력 ---*/
void Print(const IntStack* s);

/*--- 스택 종료 ---*/
void Terminate(IntStack* s);
#endif

/* int형 스택 IntStack (소스) */
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"

/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max)
{
	s->ptr = 0;
	if ((s->stk = calloc(max, sizeof(int))) == NULL) {
		s->max = 0;								/* 배열의 생성에 실패 */
		return -1;
	}
	s->max = max;
	return 0;
}

/*--- 스택에 데이터를 푸시---*/
int Push(IntStack* s, int x)
{
	if (s->ptr >= s->max)						/* 스택이 가득 참 */
		return -1;
	s->stk[s->ptr++] = x;
	return 0;
}

/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack* s, int* x)
{
	if (s->ptr <= 0)							/* 스택이 비어 있음 */
		return -1;
	*x = s->stk[--s->ptr];
	return 0;
}

/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack* s, int* x)
{
	if (s->ptr <= 0)							/* 스택이 비어 있음 */
		return -1;
	*x = s->stk[s->ptr - 1];
	return 0;
}

/*--- 스택 비우기 ---*/
void Clear(IntStack* s)
{
	s->ptr = 0;
}

/*--- 스택 용량 ---*/
int Capacity(const IntStack* s)
{
	return s->max;
}

/*--- 스택에 쌓여 있는 데이터 수 ---*/
int Size(const IntStack* s)
{
	return s->ptr;
}

/*--- 스택이 비어 있는가? ---*/
int IsEmpty(const IntStack* s)
{
	return s->ptr <= 0;
}

/*--- 스택은 가득 찼는가? ---*/
int IsFull(const IntStack* s)
{
	return s->ptr >= s->max;
}

/*--- 스택에서 검색 ---*/
int Search(const IntStack* s, int x)
{
	int i;

	for (i = s->ptr - 1; i >= 0; i--)	/* 꼭대기(top) → 바닥(bottom)으로 선형 검색 */
		if (s->stk[i] == x)
			return i;		/* 검색 성공 */
	return -1;				/* 검색 실패 */
}

/*--- 모든 데이터 표시 ---*/
void Print(const IntStack* s)
{
	int i;

	for (i = 0; i < s->ptr; i++)		/* 바닥(bottom) → 꼭대기(top)로 스캔 */
		printf("%d ", s->stk[i]);
	putchar('\n');
}

/*--- 스택 종료 ---*/
void Terminate(IntStack* s)
{
	if (s->stk != NULL)
		free(s->stk);		/* 배열을 삭제 */
	s->max = s->ptr = 0;
}

入力値

要素の多いグループを先にプッシュ

より少ない要素のグループを先にプッシュ

/* 추가한 코드 */
if (pr - left < right - pl) { // 오른쪽 요소의 개수가 더 많으면
		// 오른쪽 그룹 Push 먼저(요소가 작은 왼쪽 그룹 Pop 먼저도서 최대 스택 용량 줄어듬)
			swap(int, pl, left); // left는 pl, pl는 left
			swap(int, pr, right); // right는 pr, pr는 right
		}
        
/* 그룹 분할 완료후 Push */
if (left < pr) { // 왼쪽 그룹 푸쉬
			Push(&lstack, left); // 맨 첫 요소 
			Push(&rstack, pr);   // 맨 끝 요소 
		}
if (right > pl) { // 오른쪽 그룹 푸쉬
			Push(&lstack, pl);	// 맨 첫 요소 
			Push(&rstack, right); // 맨 끝 요소 
		}

int sort3elem(int x[], int a, int b, int c) {
	if (x[b] < x[a]) swap(int, x[b], x[a]);
	if (x[c] < x[b]) swap(int, x[c], x[b]);
	if (x[b] < x[a]) swap(int, x[b], x[a]);
	return b;
}
void insertion(int a[], int n) {
	int i, j;

	for (i = 1; i < n; i++) { // 전 값과 비교하기 때문에 1인덱스부터 시작
		int tmp = a[i]; // 삽입할 값 저장
		for (j = i; j > 0 && a[j - 1] > tmp; j--) // 삽입할 값의 앞만 검사
			a[j] = a[j - 1]; // 뒤로 한칸씩 옮김
		// memmove(&a[j], &a[j - 1], sizeof(int)); // memory move 위치 이동 함수
		a[j] = tmp; // 알맞은 위치에 삽입
	}
}
void quick(int a[], int left, int right) { // 배열 분할 함수
	int pl = left; // left pivot
	int pr = right; // right pivot 
	int x; // 피봇 변수
	int m = sort3elem(a, pl, (pl + pr) / 2, pr); // 한쪽으로 치우쳐 지는 분할 해결
	x = a[m]; // 중앙요소 피봇값 대입
	swap(int, a[m], a[right - 1]); // 중앙요소 값과 끝에서 두번째 값과 위치 바꿈

	/* 스캔할 값 3개 줄임 */
	pl++; // left = left + 1
	pr -= 2; // right = right - 2

	if (right - left < 9)
		insertion(&a[left], right - left + 1); // 처음배열 left부터
	else {
		/* 분할(divide) */
		do {
			// 왼쪽피봇값과 오른쪽 피봇값을 서로 교환해야함(작은 값은 왼쪽으로 큰 값은 오른쪽으로)
			while (a[pl] < x) pl++; // 왼쪽 피봇값이 중앙 요소값보다 작을때
			while (a[pr] > x) pr--; // 오른쪽 피봇값이 중앙 요소값보다 클때
			if (pl <= pr) { // pl이 pr보다 작을경우나 같을 경우 둘다 이동시켜야함(같을 경우도 값 교환됨)
				swap(int, a[pl], a[pr]); // 교환
				pl++;
				pr--;
			}
		} while (pl <= pr);

		/* 작은 요소개수 그룹부터 분할준비 */
		if (pr - left < right - pl) { // 오른쪽 요소의 개수가 더 많으면
			// 오른쪽 그룹 함수 호출 먼저
			swap(int, pl, left); // left는 pl, pl는 left
			swap(int, pr, right); // right는 pr, pr는 right
		}

		/* 정복 */
		if (left < pr) quick(a, left, pr);  // pr이 right 값이 됨
		if (right > pl) quick(a, pl, right); // pl이 left 값이 됨
	}
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
	char name[10];	/* 이름 */
	int height;		/* 키 */
	int weight;		/* 몸무게 */
} Person;

/*--- int형 비교 함수(오름차순 정렬에 사용) ---*/
int int_cmp(const int* a, const int* b)
{
	return *a < *b ? -1 : *a > * b ? 1 : 0;
}
/*--- Person형 비교 함수(이름 오름차순 정렬) ---*/
int npcmp(const Person* x, const Person* y)
{
	return strcmp(x->name, y->name);
}

/*--- Person형 비교 함수(키 오름차순 정렬) ---*/
int hpcmp(const Person* x, const Person* y)
{
	return x->height < y->height ? -1 : x->height > y->height ? 1 : 0;
}

/*--- Person형 비교 함수(몸무게 내림차순 정렬) ---*/
int wpcmp(const Person* x, const Person* y)
{
	return x->weight < y->weight ? 1 : x->weight > y->weight ? -1 : 0;
}

/*--- 사람 no명의 데이터를 표시 ---*/
void print_person(const Person x[], int no)
{
	int i;
	for (i = 0; i < no; i++)
		printf("%-10s %dcm %dkg\n", x[i].name, x[i].height, x[i].weight);
}

int main()
{
	Person x[] = {
		{ "sunmi", 170, 52 },
		{ "yoobin", 180, 70 },
		{ "sohee", 172, 63 },
		{ "jina", 165, 50 },
	};

	int nx = sizeof(x) / sizeof(x[0]); 		/* 배열 x의 요소 개수 */

	puts("정렬 전");
	print_person(x, nx);

	/* 이름 오름차순으로 정렬 */
	qsort(x, nx, sizeof(Person), (int(*)(const void*, const void*)) npcmp);
	puts("\n이름 오름차순으로 정렬 후");
	print_person(x, nx);

	/* 키 오름차순으로 정렬 */
	qsort(x, nx, sizeof(Person), (int(*)(const void*, const void*)) hpcmp);
	puts("\n키 오름차순으로 정렬 후");
	print_person(x, nx);

	/* 몸무게 내림차순으로 정렬 */
	qsort(x, nx, sizeof(Person), (int(*)(const void*, const void*)) wpcmp);
	puts("\n몸무게 내림차순으로 정렬 후");

	print_person(x, nx);

	return 0;
}