[바킹독의 실전 알고리즘] 0x0E강 - 정렬 1

기초 정렬

선택 정렬

시간 복잡도: $N + (N-1) + (N-2) + ... + 1 = (N^2+N)/2 = O(N^2)$

int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for (int i = n-1; i > 0; i--){
	int mxidx = 0;
    for (int j = 1; j <= i; j++) {
    	if (arr[mxidx] < arr[j]) mxidx = j;
    }
    swap(arr[mxidx], arr[i]);
}

// STL 이용
int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for (int i = n-1; i > 0; i--) {
	swap(*max_element(arr, arr+i+1), arr[i]);
}

제일 끝부터 가장 큰 원소가 오게 하기
1. 0 ~ i 수 중 가장 큰 것의 인덱스 -> mxidx
2. arr[mxidx]와 arr[i]를 swap

max_element(arr, arr+k)
: arr[0], arr[1], arr[2], ..., arr[k-1]에서 최댓값인 원소의 주소를 반환해주는 함수
/ 함수 범위 내의 원소를 다 살펴보는 함수
/ 시간 복잡도: $O(N^2)$
=> mxidx를 찾기 위해 for문을 돌리는 것과 같은 역할
IF. 전체 배열에서 가장 큰 원소가 들어있는 인덱스 알고 싶음
-> k = max_element(arr, arr+n)-arr
=> 포인터 - 포인터 -> 인덱스 구하기

버블 정렬

• 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복
  => 제일 큰 것부터 오른쪽에 쌓임
• 시간 복잡도: $O(N^2)$

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

 

+ 삽입 정렬_시간 복잡도:  $O(N^2)$

---

Merge Sort

• 재귀적으로 수열을 나눠 정렬한 후 합치는 방법
• 시간 복잡도: $O(NlgN)$

 

• N, M인 두 정렬된 리스트를 합쳐서 길이 N+M의 정렬된 리스트를 만드는 방법을 알아야 함
• 버블 정렬과 같은 방법 사용 -> 시간 복잡도: $O((N+M)^2)$
• 제일 앞에 와야 하는 수 == 전체 중에 가장 작은 원소
  -> N+M개의 모든 원소 다 보지 X 두 리스트에서 각각 가장 작은 원소만 비교
  => 시간 복잡도: O(1)
  • ex. {-9, 1, 6, 8, 12}, {-7, 7, 13, 15}
    -> -9와 -7만 비교 => -9 -> 1과 -7 비교
  • => 각 리스트에서 사용된 수 빼고 나머지 중에서 가장 앞에 있는 것만 채워넣으면 됨
• 비교 1번에 1개의 원소를 제자리에 보냄 => 길이가 N, M인 두 정렬된 리스트 합치는 것: O(N+M)

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[1000005], b[1000005], c[2000005];

int main(void) {
	ios:sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    
    int aidx = 0, bidx = 0;
    // 중요
    for (int i = 0; i < n+m; i++) {
    	if (bidx == m) c[i] = a[aidx++];
        else if(aidx == n) c[i] = b[bidx++];
        // IF.a[aidx] < b[bidx] => a[aidx] == b[aidx]일 때 b[bidx]가 c에 들어감
        else if(a[aidx] <= b[bidx]) c[i] = a[aidx++]; // a[aidx]가 c에 들어감
        else c[i] = b[bidx++];
    }
    for (int i = 0; i < n+m; i++) cout << c[i] << ' ';
}

// (중요 -> 코드 수정할 경우) 오류
for (int i = 0; i < n+m; i++) {
	if(aidx == n || a[aidx] > b[bidx]) c[i] = b[bidx++];
    else c[i] = a[aidx++];
}

bidx == m인 경우 고려 X
=> b[m]이라는 잘못된 원소에 접근해서 이상한 값 읽어와 런타인 에러 or 이상한 값이 c에 기록될 수 있음

 

stable sort

우선 순위가 같은 원소 여러 개 -> 정렬한 결과 유일하지 X 수 있음 

=> 원래의 순서 따라가도록 하는 정렬

=> 둘의 크기가 같을 때 앞쪽의 원소, a[aidx]에 들어가야 함

정리

1. 주어진 리스트를 2개로 나눔
2. 리스트 2개 각 정렬 (-> 재귀)
3. 정렬된 두 리스트 합치기

길이: $N = 2^k$

• 리스트가 분할하는 과정 
  • 함수 호출 1+2+4+...+2^k = 2N-1번 발생
    => 시간 복잡도: O(N)
• 합쳐나가는 과정
  
  • 각 줄에서 모두 N번의 연산 필요(전체 원소의 갯수만큼 필요)
    • ex. 길이가 N/4인 4개의 정렬된 리스트를 둘씩 짝지어 합치는 상황
      -> 필요한 연산 횟수: N/4 + N/4 + N/4 + N/4 = N
  • 분할이 완료됐을 때 리스트위 원소는 1개였다가 2^k개가 될 때까지 매번 2배씩 커짐 
    -> 줄: k개 => O(Nk)
    => 시간 복잡도: $O(NlgN)$

=> 시간 복잡도: $O(NlgN)$

#include <bits/stdc++.h>
using namespace std;

int n = 10;
int arr[1000001] = {...};
int tmp[1000001];

void merge(int st, int en) {
	int mid = (st+en)/2;
    int lidx = st; // arr[st:mid]에서 값을 보기 위해 사용하는 index
  	int ridx = mid; // arr[mid:en]에서 값을 보기 위해 사용하는 index
    for(int i = st; i < en; i++){
        if(ridx == en) tmp[i] = arr[lidx++];
        else if(lidx == mid) tmp[i] = arr[ridx++];
        else if(arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
        else tmp[i] = arr[ridx++];
  	}
  	for(int i = st; i < en; i++) arr[i] = tmp[i]; // tmp에 임시저장해둔 값을 a로 다시 옮김
}

void merge_sort(int st,  int en) {
	if(en == st+1) return; // 리스트 길이 1인 경우
    int mid = (st+en)/2;
    merge_sort(st, mid); // arr[st:mid] 정렬
    merge_sort(mid, en); // arr[mid:en] 정렬
    merge(st, en); // arr[st:mid] + arr[mid:en]
}

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);
    merge_sort(0, n);
    for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}

---

Quick Sort

• 재귀적으로 구현되는 정렬
• 매 단계마다 pivot이라고 이름 붙은 원소 하나를 제자리로 보내는 작업 반복
  • pivot: 늘 가장 안쪽에 위치
  • pivot을 올바른 자리에 넣고, 왼쪽은 작은 원소, 오른쪽에는 큰 원소 오게끔 
• 리스트 크기 <= 1 -> base condition에 도달
• (+) 추가적인 공간 필요 X (= In-Place Sort)
• (+) 배열 안에서의 자리 바꿈만으로 처리 => cache hit rate ↑ -> 속도 ↑

STL 못 쓰고 직접 정렬 구현 => 퀵 소트 X 머지 소트 O

int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int tmp[8];
int tidx = 0;
int pivot = arr[0];
for (int i = 1; i < 8; i++) 
	if(arr[i] <= pivot) tmp[tidx++] = arr[i];
tmp[tidx++] = pivot;
for (int i = 1; i < 8; i++)
	if(arr[i] > pivot) tmp[tidx++] = arr[i];
for (itn i = 0; i < 8; i++) arr[i] = tmp[i];

=> 리스트 전체 순회 2번 -> O(N)에 동작 But, 퀵 소트 장점 사용 X 

=> 원소의 위치 서로 잘 바꾸기 -> 추가적인 공간 사용 X 

: 양쪽 끝에 포인터 2개 두고 적절하게 swap

• l: pivot보다 큰 값이 나올 때까지 오른쪽으로 이동
• r: pivot보다 작거나 같은 값이 나올 때까지 왼쪽으로 이동

=> l과 r이 교차할 때까지 반복

int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int pivot = arr[0];
int l = 1, r = 7;
while(1) {
	while(l <= r && arr[l] <= pivot) l++;
    while(l <= r && arr[r] > pivot) r--;
    if (l > r) break;
    swap(arr[l], arr[r]);
}
swap(arr[0], arr[r]);

=> 시간 복잡도: O(N)