[정렬]

수를 차례대로 정렬!

• 주로 배열을 대상으로 적용.
• 구현하기 쉬운 정렬 : 버블 정렬 O(n^2)
• 실행 속도가 빠른 정렬 : 병합 정렬 O(nlogn)
• 특수한 경우 적용 가능한 정렬 : 카운팅 정렬 O(n)

버블 정렬 O(n^2)

• i번째와 i+1번째 수를 비교하고 큰 수를 뒤에 배치 -> 배열의 마지막에 가장 큰 수가 배치 !
• 이를 정렬이 완료될 때 까지 반복

참고 코드
for (int i=0; i<N; i++) {
    for (int j=0; j<N-1-i; j++) {
        if (arr[j] > arr[j+1]) {
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

병합 정렬 O(nlogn)

• 분할 정복 (Divide and Conquer) 방식 -> 문제를 작은 문제들로 분리하고 각각을 해결하여 결과를 모으는 것.

전체 과정
* 리스트 활용!
* 참고 블로그

1. 리스트 길이가 0 또는 1 이면 이미 정렬된 것이다.
2. 그렇지 않은 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트를 만든다.
3. 각 부분 리스트를 재귀적으로 합친다(과정 아래 참조).

합치기 과정

1. 합치는 두 리스트에 대하여 앞의 값들만 비교하여 작은 값을 새로운 리스트에 삽입
2. 모든 원소가 리스트에 삽입되면 병합 완료

• 코드 구현은 STL중 algorithm을 이용!

참고 코드
sort(v.begin(), v.end()); // 오름차순
bool compare(int x, int y) { return x>y; } // 내림차순 1
sort(v.begin(), v.end(), compare); // 내림차순 2

카운팅 정렬 O(n)

• 만약 수의 범위가 1부터 10000까지 같이 좁다면 사용 가능.
• 수의 범위 만큼의 배열을 생성
• 배열의 원소(i)마다 돌면서 무슨 수가 몇 개 있는지 세기!

참고 코드
int arr[10001];
for (int i=0; i<N; i++) { cin >> input_; arr[input_]++; }

예시 문제

• 백준 단계 12 정렬