Sort

정렬

버블 정렬

time complexity : $O(n^2)$

for(int i = 0; i<n; i++){
    for(int j = 0; j< n-1; j++){
        if(array[j] > array[j+1]){
            swap(array[j], array[j+1]);
        }
    }
}

역위의 개수는 배열을 정렬하는데 필요한 작업량을 나타냄
연달아 있는 두 원소의 순서가 잘못되어 있을 때, 이 둘을 바꾸는 것은 역위의 개수가 정확하게 한 개 줄어듬

• 역위
  배열 인덱스의 조합 (a, b)가 a<b 이지만 array[a] > array[b]를 만족할 때, 즉 원소의 순서가 잘못되었을 때 이를 역위라 한다.
  배열에 역위가 없을 시 정렬된 것, 반면에 배열의. 원소가 역순일 대 역위의 개수는 $n(n-1) \over 2$

병합 정렬

time complexity: $O(n \log n)$
위에서 볼 수 있듯이 연달아 있는 두 원소를 바꾸는 것은 역위를 한 개만 없애기 때문에 정렬 알고리즘을 효율적으로 만들기 위해서는 다른 위치에 있는 원소들의 순서를 바로잡는 방식이 필요
병합 정렬이 효율적인 이유는 단계마다 부분 배열의 크기를 절반으로 줄이고 정렬된 부분 배열을 선형 시간에 병합하기 때문
재귀 호출 단계가 $O(\log n)$이고 각 단계를 처리하는데 총 O(n) 따라서 전체 시간 복잡도는 $O(n \log n)$

• 정렬의 하한
  배열의 원소를 비교하는 데에 기반을 둔 정렬 알고리즘은 $O(n \log n)$ 보다 빠를 수 없음이 알려져 있다.

계수 정렬

time complexity: O(n)
비교 대신 다른 정보를 사용하면 위의 정렬의 하한이 적용되지 않음

배열의 모든 원소가 0 … c 범위의 정수이며 c = O(n)일 때 O(n) 시간에 배열을 정렬
인덱스가 요소의 값이 되는 장부 배열을 만드는 데 O(n), 장부 배열을 통해 정렬된 배열을 만드는 데 O(n)으로 전체 시간 복잡도가 O(n)이다.

정렬을 사용한 문제 해결

스윕 라인 알고리즘

정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링하는 방법

이벤트 스케줄링

데이터를 정렬 후 greedy 전략으로 해를 구하여 풀 수 있는 스케줄링 문제가 여럿 있다.

작업과 데드라인

작업 n개의 소요 시간과 데드라인이 주어질 때, 작업을 어떤 순서로 수행할 지 결정

이진 탐색

정렬된 배열에 특정 원소가 존재하는지 여부를 파악하는 등의 문제를 $O(\log n)$ 시간에 해결하는 알고리즘

구현

1. 단계마다 살펴보고 있는 부분 배열 중앙의 원소를 검사하고 재귀적으로 탐색

   int a = 0, b = n-1;
   while(a <=b ){
    int k = (a+b)/2;
    if(array[k] == x){
        // 위치 k에서 x를 찾음
    }
    if(array[k] < x) a = k+1;
    else b = k-1;
   }
   

2. 왼쪽에서 오른쪽으로 건너뛰어 가며 살펴보는 것

   int k = 0;
   for(int b = n/2; b>= 1; b /=2){
    while(k+b < n && array[k+b] <= x) k += b;
   }
   if(array[k] == x){
    // 위치 k에서 x를 찾음
   }
   

최적해 구하기

valid(x)가 옯른 해이면 true를 반환하고 x < k일 대 false 이고 x >= k일 때 true임을 알고 있다고 하면 이진탐색을 활용하여 효율적으로 k의 값을 구할 수 있음

valid(x)가 false인 x의 최댓값을 이진 탐색으로 구하면 그 다음 값인 k = x+1은 valid(k)가 true 인 k의 최솟값

int x = -1;
for(int b = z; b >= 1; b/= 2){
    while(!valid(x+b)) x += b;
}
int k = x+1;

위의 코드에서는 valid(z)가 true임이 확실하다는 것이 보장되어야 함
valid 함수를 $O(\log z)$ 번 호출하며 전체 수행 시간은 valid 의 시간 복잡도에 달려있다