일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- URP
- 디자인패턴
- 정렬
- 버텍스 쉐이더
- 스레드
- Heap
- 유니티
- 코스피
- 프로세스
- 코스닥
- 자료구조
- HDRP
- c#
- 네트워크
- SQL시험
- vertex shader
- 렌더링파이프라인
- TCP
- 유니티 최적화
- 배칭
- 주식
- 쉐이더
- 픽셀 쉐이더
- 통신
- 운영체제
- unity
- SQL
- 멀티스레드
- SQLD
- SRP
Archives
- Today
- Total
반응형
Let's Girin!
[자료구조&알고리즘] 퀵 정렬 본문
1. 퀵 정렬
퀵 정렬(Quick Sort)은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘으로서, 분할 정복(divide-and-conquer) 방식을 사용한다.
1.1 분할
배열을 두 개의 하위 배열로 분할하기 위해 피벗 요소를 선택하고, 피벗보다 작은 요소들은 왼쪽 하위 배열로, 피벗보다 큰 요소들은 오른쪽 하위 배열로 이동시킨다.
1.2 정복
각 하위 배열에 대해 퀵 정렬을 재귀적으로 호출하여 정렬한다.
퀵 정렬은 추가적인 메모리를 사용하지 않고 주어진 데이터 구조 내에서 작업을 수행하도록 동작하므로 병합 과정이 필요 없다.
2. 시간 복잡도
퀵 정렬의 평균 시간 복잡도는 O(nlogn)이다. 최악의 경우는 이미 정렬된 배열에서 피벗을 항상 최솟값이나 최댓값으로 선택하는 경우로, 이 때 시간 복잡도는 O(n^2)가 된다. 그러나 적절한 피벗을 선택하면 최악의 경우를 피할 수 있다.
3. 구현 방식
3.1 피벗 선택
배열의 임의의 요소를 피벗으로 선택한다.
3.2 분할
피벗을 기준으로 배열을 두 개의 하위 배열로 분할한다.
3.3 재귀 호출
각 하위 배열에 대해 퀵 정렬을 재귀적으로 호출한다.
4. 예시
#include <iostream>
using namespace std;
// 배열을 출력하는 함수.
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// 배열의 두 요소를 교환하는 함수.
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 피벗을 기준으로 배열을 분할하는 함수.
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 마지막 요소를 피벗으로 선택.
int i = (low - 1); // 작은 요소의 인덱스.
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) { // 현재 요소가 피벗보다 작거나 같으면.
i++; // 작은 요소의 인덱스를 증가시키고.
swap(&arr[i], &arr[j]); // 현재 요소와 교환.
}
}
swap(&arr[i + 1], &arr[high]); // 피벗을 올바른 위치로 이동.
return (i + 1); // 피벗의 위치를 반환.
}
// 퀵 정렬 함수
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 분할하고 피벗의 위치를 얻음
quickSort(arr, low, pi - 1); // 피벗의 왼쪽 부분 배열을 정렬
quickSort(arr, pi + 1, high); // 피벗의 오른쪽 부분 배열을 정렬
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
quickSort(arr, 0, n-1); // 배열을 정렬
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
5. 문제
https://www.acmicpc.net/problem/11004
5.1 구현 방식
#include <iostream>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void QuickSort(vector<int>& A, int start, int end, int K);
int Partition(vector<int>& A, int start, int end);
void Swap(vector<int>& A, int start, int end);
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
cin >> N >> K;
vector<int> A(N, 0);
for (int i = 0; i < N; i++)
{
cin >> A[i];
}
QuickSort(A, 0, N - 1, K - 1);
cout << A[K - 1];
}
void QuickSort(vector<int>& A, int start, int end, int K)
{
int pivot = Partition(A, start, end);
if (pivot == K)
return;
if (K < pivot)
QuickSort(A, start, pivot - 1, K);
else
QuickSort(A, pivot + 1, end, K);
}
int Partition(vector<int>& A, int start, int end)
{
if (start + 1 == end)
{
if (A[start] > A[end])
Swap(A, start, end);
return end;
}
int middle = (start + end) / 2;
Swap(A, start, middle);
int pivot = A[start];
int i = start + 1;
int j = end;
while (i <= j)
{
while (pivot < A[j] && j > 0) j--;
while (pivot > A[i] && i < A.size() - 1) i++;
if (i <= j) Swap(A, i++, j--);
}
A[start] = A[j];
A[j] = pivot;
return j;
}
void Swap(vector<int>& A, int start, int end)
{
int temp = A[start];
A[start] = A[end];
A[end] = temp;
}
반응형
'Data Structures & Algorithms' 카테고리의 다른 글
[자료구조&알고리즘] 트리 구조 (0) | 2025.04.14 |
---|---|
[자료구조&알고리즘] 씬 탐색부터 AI FSM까지, 게임 속 트리 구조의 모든 것 (0) | 2025.04.12 |
[자료구조&알고리즘] 버블 정렬 (1) | 2024.05.28 |
[자료구조&알고리즘] 선택 정렬 (1) | 2024.05.28 |
[자료구조&알고리즘] 트리(Tree) (1) | 2024.02.03 |