정렬 알고리즘(퀵 정렬)

ggh·2022년 5월 11일

algorithm

목록 보기

5/13

퀵 정렬(Quick Sort)

개yo

앞선 포스팅에서는 선택정렬 , 버블정렬 , 삽입정렬에 대해 알아보았다. 3개의, 정렬 알고리즘의 시간 복잡도는 주어진 데이터에 따라 달라지지만 보통 O(N^2) 의 형태를 띄고 있다. 하지만 이번 포스팅에서 설명할 퀵 정렬 의 시간복잡도는 O(N^2)가 아닌 O(N * log N) 를 가지고 있다. 이런 특징 때문에 여러 언어의 정렬 알고리즘의 기반이 되는 알고리즘으로 쓰이고 있다. ex) C++의 sort( ) 등등

문제

문제 : 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성 하여라

[ 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 ]

SOL

문제를 해결하기 위해 퀵정렬을 쓴다면 “특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누어 배치하기” 를 생각해 볼 수 있다.

위와 같은 방식을 퀵정렬 이라고 한다.

특징

평균 시간 복잡도는 O(N * log N)이다.

최악(데이터가 거의 정렬되어 있는)의 경우의 시간 복잡도는 O(N^2)이다.

효율성이 좋아 각 언어의 sort lib의 기반이 되는 알고리즘으로 사용된다.

구현

#include <iostream>

using namespace std; 

void QuickSort(int *arr, int begin, int end)
{
    if(begin >= end) return; // 원소가 1개인 경우 종료
    int pivot = begin; // 기준값(pivot)은 첫번째 인덱스 
    int left = begin + 1;
    int right = end;
    while (left <= right)
    {
        // Left값이 Pivot값 보다 작은경우 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // Right값이 Pivot값 보다 큰경우 반복
        while (right > begin && arr[right] >= arr[pivot]) right--; 
        // Left, Right의 인덱스 즉 순서가 엇갈리면, Pivot, Right swap
        if(left > right) swap(arr[pivot], arr[right]);
        // Pivot값보다 L, R의 조건이 모두 맞지 않는 경우 swap(L, R)
        else swap(arr[left], arr[right]);
    }
    // 재귀적 호출 (log N)번 실행
    // pivot 보다 작은 값들의 리스트 (pivot 포함 O)
    QuickSort(arr, begin, right - 1); 
    // pivot 보다 큰 값들의 리스트   (picot 포함 X)
    QuickSort(arr, right + 1, end);
}

int main()
{
    int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
    int n = 10;
    QuickSort(arr, 0, n-1);
    for(auto el : arr)
        cout << el << " ";
    cout << endl;
    return 0;
}

출력

0 1 2 3 4 5 6 7 8 9

해설

위 코드를 실행하면 오름차순으로 배열이 정리된 모습을 확인 할 수 있다.

리스트 안의 요소 한개를 선택한다. - 기준값(Pivot) 설정
```
int pivot = begin; // 기준값(pivot)은 첫번째 인덱스 
```

설정한 기준값(Pivot)을 기준으로 보다 작은 요소는 왼쪽 보다 큰 요소들은 모두 오른쪽으로 반복적으로 옮긴다.

// Left값이 Pivot값 보다 작은경우 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// Right값이 Pivot값 보다 큰경우 반복
while (right > begin && arr[right] >= arr[pivot]) right--;

기준값(Pivot)을 제외한 왼쪽, 오른쪽 리스트를 정렬한다.

// Left, Right의 인덱스 즉 순서가 엇갈리면, Pivot, Right swap
if(left > right) swap(arr[pivot], arr[right]);
// Pivot값보다 L, R의 조건이 모두 맞지 않는 경우 swap(L, R)
else swap(arr[left], arr[right]);

분할된 부분의 리스트를 다시 호출 - 정렬한다.

분할 된 리스트도 마찬가지고 기준값(Pivot)을 기준으로 2개의 리스트로 나누는 과정을 재귀적으로 반복한다.

// 재귀적 호출 (log N)번 실행
// pivot 보다 작은 값들의 리스트 (pivot 포함 O)
QuickSort(arr, begin, right - 1); 
// pivot 보다 큰 값들의 리스트   (picot 포함 X)
QuickSort(arr, right + 1, end);

언제까지?? ~~> 리스트의 크기가 0이나 1이 될때까지
```
if(begin >= end) return; // 원소가 1개인 경우 종료
```

예시문제

두개의 배열 A, B가 존재한다. 이 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.

두 배열 A, B를 서로 K 번의 스왑을 할 수 있을 때 배열 A의 모든 원소의 합이 최대가 되어야 한다.

SOL

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 


void solution(vector<int> arr_1, vector<int> arr_2, int k)
{
    int answer = 0;
    sort(arr_1.begin(), arr_1.end());
    sort(arr_2.rbegin(), arr_2.rend());
    for(int i=0; i < k; i++)
        if(arr_1[i] < arr_2[i]) swap(arr_1[i], arr_2[i]);
    for(auto el : arr_1)
        answer += el;
    cout << answer << endl;
}

int main()
{
    vector<int> arr_1{1,2,5,4,3};
    vector<int> arr_2{5,5,6,6,5};
		int k = 3;
    solution(arr_1, arr_2, k);

    return 0;
}