[개념] 정렬 알고리즘

정렬

• 데이터를 특정한 기준에 따라 순서대로 나열한 것

---

선택정렬

• 시간복잡도 - $O(N^2)$
• 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복
• 가장 작은 것을 선택

#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8 };
    // 선택 정렬
    for (int i = 0; i <10; i++) {
        int idx = i; // 가장 작은 원소 인덱스
        for (int j = i; j < 10; j++) {
            if (num[j] < num[idx]) {
                idx = j;
            }
        }
        swap(num[idx], num[i]);
    }
    for (int i = 0; i < 10; i++) {
        cout << num[i] << " ";
    }

---

삽입 정렬

알고리즘 문제 풀이에 사용하기엔 느림
But 정렬이되어 있는 상태로 입력이 주어지는 문제라면 다른 알고리즘을 사용하는 것보다 효율적

• 시간 복잡도 - 최선 $O(N)$ , 최악 $O(N^2)$
• 필요할 때만 위치를 바꿔서 '데이터가 거의 정렬 되어 있을 때' 효율적
• 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다

#include <iostream>
#include <stdlib.h>
#include<algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8 };
    // 삽입 정렬
    for (int i = 1; i < 10; i++) {
        for (int j = i; j>0; j--) {
            if (num[j] < num[j - 1]) {
                swap(num[j], num[j - 1]);
            }
            else {
                break;
            }
        }
    }
    for (int i = 0; i < 10; i++) {
        cout << num[i] << " ";
    }
}

---

퀵 정렬

c++ STL의 algorithm 헤더에 있는 sort() 함수 ⇒ 퀵정렬

• 시간 복잡도 - $O(NlongN)$
• 기준을 설정한 다음 큰 수와 작은 숫자를 교환한 후 리스트를 반으로 나누는 방식
• 피봇 : 큰 수와 작은 수를 교환 할 때, 교환하기 위한 기준을 명칭

#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;
void quickSort(int* arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
    int pivot = start; // 피벗은 첫 번째 원소
    int left = start + 1;
    int right = end;
    while (left <= right) {
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 피벗을 교체
        if (left > right) swap(arr[pivot], arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else swap(arr[left], arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8 };
    // 퀵 정렬
    // 라이브러리 이용
    // sort(num, num + 10);
    // 일반 구현
    quickSort(num, 0, 9);
    for (int i = 0; i < 10; i++) {
        cout << num[i] << " ";
    }

}

---

계수 정렬

• 시간복잡도 - $O(N+K)$
• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 데이터의 크기 범위가 제한되어 정수로 표현할 수있을 때만 사용 가능
• 가장 큰 데이터와 작은 데이터 크기가 작아야함

#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num[] = { 7,5,9,0,3,1,6,2,4,8,0,5,2};
    int ans[13] = {0,};
    // 계수 정렬
    for (int i = 0; i < 13; i++) {
        ans[num[i]]++;
    }
    for (int i = 0; i < 10; i++) {
        if (ans[i] > 0) {
            while (ans[i]--) {
                cout << i << " ";
            }
        }
    }
}

---

C++ sort STL

오름차순 (default)

• sort()는 algorithm 헤더 파일에 속함
• 퀵 정렬이용
• 평균 시간복잡도 - $O(NlongN)$

사용법

sort(arr, arr+1);
sort(v.begin(), v.end());
sort(v.begin(), v.end(), compare); // compare : 사용자 정의 함수
sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
sort(v.begin(), v.end(), less<자료형>()); // default - 오름차순