[코딩테스트][C++]이론4-2. 정렬

1. 퀵정렬

퀵정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터를 왼쪽에 큰 데이터를 오른쪽에 분류하는 것을 반복해 정렬한다. 

문제 예시1.

K번째 수 구하기

 

내장함수를 통해서 정렬할 수 도 있지만  퀵정렬의 원리를 이해하기위해 퀵정렬로 풀어보려고 한다.  

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void quickSort(vector<int>& A, int S, int E, int K);
int partition(vector<int>& A, int S, int E);
void swap(vector<int>& A, int i, int j);

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 S, int E, int K) {
    int pivot = partition(A, S, E);
    if (pivot == K)
        return;
    else if (K < pivot) 
        quickSort(A, S, pivot - 1, K);
    else 
        quickSort(A, pivot + 1, E, K);
}
int partition(vector<int>& A, int S, int E) {
    if (S + 1 == E) {
        if (A[S] > A[E])swap(A, S, E);
        return E;
    }
    int M = (S + E) / 2;
    swap(A, S, M); 
    int pivot = A[S];
    int i = S + 1, j = E;
    while (i <= j) {
        while (j >= S + 1 && pivot < A[j]) {   
            j--;
        }
        while (i <= E && pivot > A[i]) {  
            i++;
        }

        if (i < j) {
            swap(A, i++, j--);  // 찾은 i와 j를 교환하기
        }
        else {
            break;
        }
    }
    // i == j 피벗의 값을 양쪽으로 분리한 가운데에 오도록 설정하기
    A[S] = A[j];
    A[j] = pivot;
    return j;
}
void swap(vector<int>& A, int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

 

2.병합정렬

병합 정렬은 divide and conquer 방식 즉 배열은 나누고 합치는 과정에서 정렬을 해주는 방식이다. 

문제 예시2.

버블정렬프로그램2

n의 최대 범위가 500,000이므로 O(nlogn)의 시간복잡도로 정렬을 수행하면 된다.

하지만 제목처럼 버블정렬을 사용하면 제한 시간을 초과한다. 그런데 병합정렬의 수행과정을 보면 swap이 포함되어 있기때문에 정렬하는 과정에서 원소가 앞으로 이동한 거리만큼 더해서 그 값을 출력해주면 된다.

#include <iostream>
#include <vector>
using namespace std;
void merge_sort(int s,int e);
static vector<int> a;
static vector<int> tmp;
static long result;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    a = vector<int>(n + 1, 0);
    tmp= vector<int>(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    result = 0;
    merge_sort(1, n);
    cout << result << "\n";
}

void merge_sort(int s, int e) {
    if (e - s < 1) {
        return;
    }

    int m = s + (e - s) / 2;            //중앙값

    merge_sort(s, m);                   //시작~중앙
    merge_sort(m + 1, e);               //중앙~끝
    
    for (int i = s; i <= e; i++) {
        tmp[i] = a[i];
    }

    int k = s;
    int idx1 = s;
    int idx2 = m + 1;

    while (idx1 <= m && idx2 <= e) {            //병합
        if (tmp[idx1] > tmp[idx2]) {
            a[k] = tmp[idx2];               //값을 작은값으로 업데이트 해주기 
            result += idx2 - k;         //이동한 만큼 더해주기
            k++;
            idx2++;
        }
        else {
            a[k] = tmp[idx1];
            k++;
            idx1++;
        }
    }

    while (idx1 <= m) {         //남은값 배열에 채워주기
        a[k] = tmp[idx1];
        k++;
        idx1++;
    }
    while (idx2 <= e) {         //남은값 배열에 채워주기
        a[k] = tmp[idx2];
        k++;
        idx2++;
    }
}

 

3. 기수정렬

기수정렬은 값을 비교하는 것이아니라 값을 놓고 비교할 자릿수를 정한다음 해당 자릿수만 비교하여 정렬하는 것으로

시간복잡도는 O(kn)으로 k가 데이터의 자릿수이다.

기수 정렬은 값의 자릿수를 대표하는 10개의 큐를 사용한다. 

문제예시3.

수 정렬하기 3

 이 문제는 n의 최대 10,000,000이 나올 수 있기 때문에 nlogn 보다 빠른 알고리즘이 필요하다. 숫자의 크기가 10,000 이하이기 때문에 기수 정렬과 함께 많이 사용되는 계수 정렬을 사용하여 문제를 풀어보려고  한다.

계수정렬은  수 값을 받아 수의 값을 인덱스 값으로 판단하고 그 인덱스에 해당하는 값을 1증가시키고 배열에 1이상인 것들을 출력시켜주면 된다. 

#include <iostream>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    int cnt[10001] = { 0 };
    int num = 0;

    for (int i = 1; i <= n; i++) {
        cin >> num;
        cnt[num]++;
    }
    for (int i = 0; i <= 10000; i++) {
        if (cnt[i] != 0) {
            for (int j = 0; j < cnt[i]; j++) {
                cout << i << "\n";
            }
        }
    }
}