일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- Machine Learning
- 해시테이블
- 자바스크립트
- RT scheduling
- 프로그래머스
- 알고리즘
- 컨테이너
- cors
- 스택
- 웹팩
- alexnet
- 프로세스
- GraphQL
- 포인터
- 이진탐색
- 프론트엔드
- 연결 리스트
- 타입스크립트
- 배열
- 큐
- C
- pytorch
- 브라우저
- vue3
- 코딩테스트
- 연결리스트
- 릿코드
- RxJS
- 자료구조
- APOLLO
- Today
- Total
프린세스 다이어리
[C] 퀵 정렬이란? C언어로 퀵 정렬 구현하는 코드 본문
1. 퀵 정렬이란
퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로, 평균적으로 0(NlogN)의 시간 복잡도를 가진다.
퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 최악의 경우 O(N2) 이다. 따라서 실제로 정렬할 때는 퀵 정렬을 굳이 직접 구현하지는 않는다. C++에 Algorithm 라이브러리에 포함된 sort() 함수는 퀵 정렬을 기반으로 하면서 O(NlogN)을 보장한다.
피벗 값이 가장 왼쪽이라고 가정한다.
5 | 4 | 3 | 8 | 9 | 6 | 7 | 1 | 10 | 2 |
(1) 5의 왼쪽부터 시작해서 5보다 큰 값을 찾는다. 또 오른쪽부터 시작해서 5보다 작은 값을 찾는다. 그리고 둘을 교체한다.
5 | 4 | 3 | 8 | 9 | 6 | 7 | 1 | 10 | 2 |
교체 후,
5 | 4 | 3 | 2 | 9 | 6 | 7 | 1 | 10 | 8 |
(2) 다시 왼쪽부터 하나씩 살피며 5보다 큰 수를 찾고, 오른쪽부터 하나씩 살피며 5보다 작은 수를 찾아 둘을 교체한다.
5 | 4 | 3 | 2 | 9 | 6 | 7 | 1 | 10 | 8 |
교체 후,
5 | 4 | 3 | 2 | 1 | 6 | 7 | 9 | 10 | 8 |
(3) 마찬가지로 왼쪽부터 5보다 큰 수, 오른쪽부터 5보다 작은 수를 찾는다. 그런데 이번엔 둘의 위치가 엇갈려서 큰 수가 작은 수보다 뒤에 온다.
5 | 4 | 3 | 2 | 1 | 6 | 7 | 9 | 10 | 8 |
이 경우, 작은 값과 피벗 값을 바꿔준다.
1 | 4 | 3 | 2 | 5 | 6 | 7 | 9 | 10 | 8 |
(4) 5를 기준으로 5를 포함하여 왼쪽에 있는 수끼리, 5보다 오른쪽에 있는 수 끼리 재귀적으로 똑같은 연산을 수행해 준다.
1 | 4 | 3 | 2 | 5 | 6 | 7 | 9 | 10 | 8 |
(5) 완성
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
원소를 절반씩 나눌 때 logN의 시간 복잡도가 나오는 대표적인 구조가 완전 이진 트리다. 정렬을 한 번 마친 후 오른쪽과 왼쪽에서 각각 수행을 하기 때문에 높이가 짧다.
2. 퀵 정렬 구현
(1) 배열 a를 초기화해주고 swap 함수를 만든다.
#include <stdio.h>
#define SIZE 1000
int a[SIZE];
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
(2) 해당 부분 배열의 시작과 끝 인덱스를 인자로 받는 quickSort 함수를 만들어준다.
- i는 왼쪽에서, j는 오른쪽에서 출발한다.
- i 인덱스와 j 인덱스가 엇갈리지 않을 때까지만 반복하는 while문에서는 부분 배열에서 피벗보다 큰 값, 작은 값을 하나씩 찾아내어 교체하는 작업을 한 번씩 해 준다.
- 그 작업이 끝나면 부분배열을 나눠서 quickSort 함수를 재귀적으로 호출해 준다.
void quickSort(int start, int end) {
if (start >= end) return;
int key = start, i = start + 1, j = end, temp;
while (i <= j) {
while (i <= end && a[i] <= a[key]) i++;
while (j > start && a[j] >= a[key]) j--;
if (i > j) swap(&a[key], &a[j]);
else swap(&a[i], &a[j]);
}
quickSort(start, j - 1);
quickSort(j + 1, end);
}
(3) 입력을 받아서 퀵 정렬을 해 본다.
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort(0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
}
(4) 결과를 확인한다.
5
3 4 1 9 7
1 3 4 7 9
'C, C++' 카테고리의 다른 글
[C] 이진 트리 구현 코드 (0) | 2021.11.13 |
---|---|
[C] 이진 트리란? 이진 트리 관련 용어 정리 (0) | 2021.11.11 |
[C] 선택 정렬과 삽입 정렬 원리, C언어로 구현하기 (0) | 2021.11.06 |
자료구조 큐를 C언어 연결 리스트로 구현하기 (0) | 2021.10.25 |
incompatible pointer types assigning to 'struct Node *' from 'Node *' [-Wincompatible-pointer-types] 해결 방법 (0) | 2021.10.14 |