Let's Girin!

[자료구조&알고리즘] 퀵 정렬 본문

Data Structures & Algorithms

[자료구조&알고리즘] 퀵 정렬

window= 2024. 5. 29. 21:34

1. 퀵 정렬

퀵 정렬(Quick Sort)은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘으로서, 분할 정복(divide-and-conquer) 방식을 사용한다. 

 

1.1 분할

배열을 두 개의 하위 배열로 분할하기 위해 피벗 요소를 선택하고, 피벗보다 작은 요소들은 왼쪽 하위 배열로, 피벗보다 큰 요소들은 오른쪽 하위 배열로 이동시킨다.

1.2 정복

각 하위 배열에 대해 퀵 정렬을 재귀적으로 호출하여 정렬한다.

퀵 정렬은 추가적인 메모리를 사용하지 않고 주어진 데이터 구조 내에서 작업을 수행하도록 동작하므로 병합 과정이 필요 없다.


2. 시간 복잡도

퀵 정렬의 평균 시간 복잡도는  O(nlog⁡n)이다. 최악의 경우는 이미 정렬된 배열에서 피벗을 항상 최솟값이나 최댓값으로 선택하는 경우로, 이 때 시간 복잡도는 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;
}
반응형