<div id="readability-page-1" class="page"><div><h2 id="퀵-정렬quick-sort">퀵 정렬(Quick Sort)</h2>
퀵 정렬은 분할 정복 알고리즘의 일종으로, 리스트를 정렬하는 효율적인 방법 중 하나이다. 작동 원리는 다음과 같다.
<h2 id="작동-원리">작동 원리</h2>
<img src="https://velog.velcdn.com/images/jwlee010523/post/de63f6c9-6d48-435f-a073-7022760d1076/image.png">
<h3 id="1-피벗-선택pivot">1. 피벗 선택(Pivot)</h3>
정렬한 리스트에서 하나의 기준 값(피벗)을 선택한다. 피벗은 리스트의 임의의 값일 수 있으며, 일반적으로 처음, 중간, 마지막 값 중 하나로 설정한다.
<h3 id="2-분할partitioning">2. 분할(partitioning)</h3>
피벗을 기준으로 리스트를 두 개의 부분 리스트로 나눈다.
<ul>
<li>피벗보다 작은 값들로 이루어진 부분 리스트</li>
<li>피벗보다 큰 값들로 이루어진 부분 리스트</li>
</ul>
<h3 id="3-재귀적으로-정렬recursive-sorting">3. 재귀적으로 정렬(Recursive Sorting)</h3>
분할된 두 개의 부분 리스트에 대해 퀵 정렬을 재귀적으로 적용한다. 이 과정은 리스트가 더 이상 나눌 수 없을 때(부분 리스트의 크기가 1 이하일 때) 종료된다.
<h3 id="4-합치기combine">4. 합치기(Combine)</h3>
정렬된 부분 리스트를 결합하여 최종 정렬된 리스트를 만든다.
<h2 id="시간-복잡도와-공간-복잡도">시간 복잡도와 공간 복잡도</h2>
<h3 id="시간-복잡도">시간 복잡도</h3>
<ul>
<li>평균: <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(nlogn)</annotation></semantics></math></li>
<li>최악: 이미 정렬된 경우 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></li>
</ul>
<h3 id="공간-복잡도">공간 복잡도</h3>
<ul>
<li><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(logn)</annotation></semantics></math> (재귀 호출 스택 사용)</li>
</ul>
<h2 id="장점과-단점">장점과 단점</h2>
<h3 id="장점">장점</h3>
<ul>
<li>정렬 속도가 빠르고 대부분의 경우 효율적이다.</li>
<li>추가 메모리 공간을 적게 사용한다.</li>
</ul>
<h3 id="단점">단점</h3>
<ul>
<li>최악의 경우 시간이 많이 걸릴 수 있다.</li>
<li>피벗 선택이 중요한 성능 요인이다.</li>
</ul>
<h2 id="전체-코드">전체 코드</h2>
<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;

#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++;
		// 피봇보다 큰 데이터가 있을 때까지 반복
		while (list[low] &lt; pivot);
		do
			// low와 맞춰주기 위해 1 증가한 상태에서 다시 1 갑소
			high--;
		// 피봇보다 작은 데이터가 있을 때까지 반복
		while (list[high] &gt; pivot);
		if (low &lt; high)
			SWAP(list[low], list[high], temp);
		// low와 high이 겹칠 때 반복문 탈출
		// low의 증가와 high의 감소가 함께 움직이므로 둘은 교차하게 됨
	} while (low &lt; high);

	// 교차한 상태에서 high의 위치가 피봇의 위치임
	// 만약 피봇보다 작거나 큰 값이 없다면 
	// 작은 경우에는 오른쪽 서브 파일만 생기고, 큰 경우 왼쪽 서브 파일만 생김
	SWAP(list[left], list[high], temp);
	return high;
}

void quick_sort(int list[], int left, int right) {
	if (left &lt; 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 &lt; n; i++) 	// 난수 생성 및 출력 
		list[i] = rand() % 100;

	quick_sort(list, 0, n - 1); // 퀵정렬 호출 
	for (i = 0; i &lt; n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}</code></pre>
<blockquote>
출처 
C언어로 쉽게 풀어쓴 자료구조 - 천인구
</blockquote></div></div>

jwlee010523.log

퀵 정렬(Quick Sort)
퀵 정렬은 분할 정복 알고리즘의 일종으로, 리스트를 정렬하는 효율적인 방법 중 하나이다. 작동 원리는 다음과 같다.
작동 원리
1. 피벗 선택(Pivot)
정렬한 리스트에서 하나의 기준 값(피벗)을 선택한다. 피벗은 리스트의 임의의 값일 수 있으며, 일반적으로 처음, 중간, 마지막 값 중 하나로 설정한다.
2. 분할(partitioning)
피벗을 기준으로 리스트를 두 개의 부분 리스트로 나눈다.
피벗보다 작은 값들로 이루어진 부분 리스트
피벗보다 큰 값들로 이루어진 부분 리스트
3. 재귀적으로 정렬(Recursive Sorting)
분할된 두 개의 부분 리스트에 대해 퀵 정렬을 재귀적으로 적용한다. 이 과정은 리스트가 더 이상 나눌 수 없을 때(부분 리스트의 크기가 1 이하일 때) 종료된다.
4. 합치기(Combine)
정렬된 부분 리스트를 결합하여 최종 정렬된 리스트를 만든다.
시간 복잡도와 공간 복잡도
시간 복잡도
평균: $O(nlogn)$
최악: 이미 정렬된 경우 $O(n^2)$
공간 복잡도
$O(logn)$ (재귀 호출 스택 사용)
장점과 단점
장점
정렬 속도가 빠르고 대부분의 경우 효율적이다.
추가 메모리 공간을 적게 사용한다.
단점
최악의 경우 시간이 많이 걸릴 수 있다.
피벗 선택이 중요한 성능 요인이다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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++;
 // 피봇보다 큰 데이터가 있을 때까지 반복
 while (list[low] < pivot);
 do
 // low와 맞춰주기 위해 1 증가한 상태에서 다시 1 갑소
 high--;
 // 피봇보다 작은 데이터가 있을 때까지 반복
 while (list[high] > pivot);
 if (low < high)
 SWAP(list[low], list[high], temp);
 // low와 high이 겹칠 때 반복문 탈출
 // low의 증가와 high의 감소가 함께 움직이므로 둘은 교차하게 됨
 } while (low < high);
 // 교차한 상태에서 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");
 return 0;
}
출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

퀵 정렬(Quick Sort)

댓글