[Algorithm] 정렬

정렬에는 여러가지 방식이 있고 다음 4가지 정렬만 우선 다루려고 한다.

설명은 오름차순 기준으로 진행하므로 내림차순은 반대로 생각하면 된다.

 

1. 선택정렬(Selection Sort)

    - O(N^2)

    - k번째 작은 데이터를 가져와 k번째 위치에 놓는다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {

    // 삽입정렬
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j-1]) {
                swap(arr[j], arr[j-1]);
            }
        }
    }

    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0 ;
}

2. 삽입정렬(Insertion Sort)

    - O(N^2)

    - 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {

    // 선택정렬
    for (int i = 0; i < arr.size(); i++) {
        int min_index = i;
        for (int j = i+1; j < arr.size(); j++) {
            if (arr[min_index] > arr[j]) {
                min_index = j;
            }
        }
        swap(arr[min_index], arr[i]);
    }

    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0 ;
}

3. 퀵정렬(Quick Sort)

    - O(N^2)

    - 호어 분할 방식 : 리스트에서 첫번째 데이터를 pivot으로 정한다. 이외에도 많은 pivot의 기준을 잡는 방식은 많다.

    1) pivot을 기준으로 왼쪽에서부터 pivot보다 큰 데이터를 찾고  오른쪽부터 pivot보다 작은 데이터를 찾아 교환한다.

    2) 1) 을 반복하다 작은 데이터와 큰 데이터가 바뀌면 작은 데이터와 pivot을 바꾼다.

    3) pivot으로 분할된 왼쪽 리스트와 오른쪽 리스트에 대해 각각 1), 2)를 반복수행한다.

   *C++ sort의 경우 퀵 정렬을 기반으로 하지만 피벗값을 설정할 때 추가적인 로직을 더해 O(NlogN)을 보장한다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

void quickSort(int start, int end) {
    // 원소가 한개인 경우 종료
    if (start >= end) {
        return;
    }

    // 호어 분할 방식 : pivot은 첫번째 원소
    int pivot = start;
    int left = pivot+1;
    int right = end;

    while (left <= right) {
        // pivot보다 큰 데이터를 찾을 때까지 반복 (배열을 초과하지 않을 정도로만)
        while (left <= end && arr[left] <= arr[pivot]) {
            left++;
        }
        // pivot보다 작은 데이터를 찾을 때까지 반복 (pivot index보다 커야함)
        while (right > start && arr[right] >= arr[pivot]) {
            right--;
        }
        // 엇갈렸다면 작은 데이터와 pivot을 교체
        if (left > right) {
            swap(arr[right], arr[pivot]);
        }
        // 엇갈리지 않았다면 큰 데이터와 작은 데이터를 교체
        else {
            swap(arr[left], arr[right]);
        }
    }

    // 분할 후, 왼쪽 리스트와 오른쪽 리스트에서 각각 반복수행
    quickSort(start, right-1);
    quickSort(right+1, end);

}

int main(void) {

    quickSort(0, arr.size()-1);

    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0 ;
}

계수 정렬(Counting Sort)

• O(N+K)
• 정렬된 리스트에 가장 작은 데이터부터 큰 데이터까지의 빈도를 세서 저장해주는 것이다. 말 그대로 count다.
• 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다. (이를 넘어가면 공간 복잡도를 초과한다.)
• 즉, 시간 복잡도를 위해 공간 복잡도를 희생한다.
• 말도 안되게 빠른 정렬을 요하는 문제는 무조건 계수정렬이다.

#include <iostream>
#include <vector>

#define MAX_VALUE 9

using namespace std;

int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int cnt[MAX_VALUE + 1];

int main(void) {
    for (int i = 0; i < n; i++) {
        cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
    }
    for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << ' '; // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
        }
    }
}