☀️ 알고리즘:: 퀵 정렬(Quicksort)
🚀 What I Will Learn
- 퀵 정렬(Quicksort)의 원리를 이해한다
퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다
퀵 정렬 알고리즘
1️⃣ 퀵 정렬이란?
1) 피벗(pivot)을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법
2) 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로
3) 전체 원소를 나누는 데에 평균적으로 logN
번이 소요된다
4) 평균적으로 0(NlogN)
의 시간 복잡도를 가진다
시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미
✔️ 퀵 정렬 알고리즘 예시
퀵 정렬을 수행할 때 피벗값이 가장 왼쪽 값이라고 가정.
1) 가장 왼쪽 값인 5를 기준으로 오른쪽으로 출발해서 5보다 큰 값을 찾는다. 그럼 8
2) 배열의 오른쪽부터 시작해서 5보다 작은 값을 구하면 2
3) 비교를 통해 찾았던 8과 2의 자리를 서로 교체
4) 마찬가지로 원소를 찾는다.
- 왼쪽에서 부터 5보다 큰 값은 9,
- 오른쪽에서 부터 5보다 작은 값은 1
5) 같은 방법으로 원소를 찾는다.
- 왼쪽에서 부터 5보다 큰 값은 6,
- 오른쪽에서 부터 5보다 작은 값은 1
6) 원소를 찾다보면 5)번과 같이 엇갈리는 경우가 발생하는데, 이렇게 큰 값과 작은 값이 엇갈리는 경우에는 피벗값과 더 작은 값을 서로 교체
7) 다시 피벗값을 기준으로 재귀적으로 반복하며 퀵 정렬을 수행
8) 각각의 부분 배열들이 정렬을 수행하면서 정렬 수행
📌 참고
퀵 정렬은 원소를 절반씩 나눌 때 logN의 시간 복잡도가 나오는 대표적인 완전 이진 트리와 흡사한 구조를 갖는다.
이진트리: 원소를 절반씩 나눌 때 𝑙𝑜𝑔𝑁의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리. 완전 이진 트리 형태는 흔히 컴퓨터 공학에서 가장 선호하는 이상적인 형태이다.
2️⃣ 퀵 정렬의 구현
1) 배열 선언
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000
int a[SIZE];
int swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
2) 퀵 정렬 구현
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]);
system("pause");
return 0;
}
✨ tl;dr
- 퀵 정렬은 시간 복잡도가
𝑂(𝑁𝑙𝑜𝑔𝑁)
인 가장 보편적인 정렬 알고리즘이다
Author And Source
이 문제에 관하여(☀️ 알고리즘:: 퀵 정렬(Quicksort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@april_5/알고리즘-퀵-정렬Quicksort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)