JArchive 프로그래밍 일기

목차 

0x00 기초정렬

0x01 Merge Sort 

0x02 Quick Sort

---

0x00 기초정렬

1. 선택정렬 

책꽂이에 꽂힌 책을 높이 순으로 정렬하려면 어떻게 해야 할까? 

제일 큰 숫자를 찾아서 뒤로 보낸다.

그 다음 큰 것을 찾아서 뒤로 보낸다 ... 이렇게 이어질 테니 계산해보면 시간복잡도는 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--){ // 최대값을 찾으면 i위치로 보낼것이다. i:맨 마지막부터 앞에서 두번째 까지.
  int mxidx = 0;
  for(int j = 1; j <= i; j++){
    if(arr[mxidx] < arr[j]) mxidx = j;
  }
  swap(arr[mxidx], arr[i]);
}

선택 정렬은 가장 큰 수를 찾으면, 인덱스 i로 이동시킨다. 
내부 반복문에서 mxidx 인덱스와 j인덱스 자리의 숫자를 비교한다. 이 반복문이 종료되면 가장 큰 숫자의 인덱스가 mxidx에 저장된다. 
가장 큰 숫자 인덱스 mxidx와 뒤쪽 인덱스 i를 swap한다. ( == 가장 큰 숫자를 뒤로 보낸다)

max_element 함수로 줄여본 코드 

max_element(arr, arr+k) 
// arr[0], arr[1], arr[2], .. , arr[k-1] 에서 최댓값인 원소의 주소를 반환

arr[0]부터 arr[k-1] 까지 탐색한 후 최댓값인 원소 주소를 반환한다. 

arr[k]가 아니라 arr[k-1]임을 주의하자. 

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]);
}

최댓값을 찾으면 인덱스 9와 swap, 최댓값을 찾으면 인덱스 8과 swap, 최댓값을 찾으면 인덱스 7과 swap..을 반복한다. 

max_element함수는 범위 내의 원소를 모두 살피니까 O(N^2)의 시간복잡도라는 점을 인지하자. 

2. 버블정렬 

인접한 원소가 자기보다 크면 자리를 바꾼다. 보글보글 인접한 원소끼리만 swap하는 모양 때문에 이름이 버블정렬이다. 

이중 반복문이라서 시간복잡도가 O(N^2)다. 

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

정렬 1회전이 끝나면, 가장 큰 숫자가 맨 뒤에 위치한다. 13이 arr[4]에 가 있을 것이다. 

내부 반복문 j에서는 (인덱스 0과 1) (인덱스 1과 2) 이렇게 인접한 숫자를 비교하니까. j를 0부터 n-1까지 순회해야 한다.

그래야 없는 인덱스를 참조하는 런타임 에러가 안난다. 

내부 반복문 종료 조건을 j < n-i-1 로 해도 정상 동작하는 이유는 뭘까?

버블 정렬에서 정렬 1회전이 끝나면, 가장 큰 숫자가 맨 뒤에 위치한다.

 

정렬 1회전이 끝나면 13이 arr[4]에 있다. 인덱스 4에 있는 숫자를 이제 비교할 필요 없다.

정렬 2회전에서는 인덱스 0, 1, 2, 3 까지만 비교하면 된다! 정렬 2회전이 끝나면 6이 arr[3]에 있다. 인덱스 3부터는 비교할 필요 없다.

이렇게 이미 맨 뒤에 정렬이 끝난 숫자는 비교를 안해도 올바른 자리에 가 있기 때문이다. 

---

0x01 Merge Sort

재귀적으로 수열을 나눠 정렬한 후 합치는 정렬이다. 시간복잡도는 O(NlogN)이다. 

N이 10만 정도라면, O(N^2) 알고리즘의 경우, 10초~1분 소요된다. O(NlogN)알고리즘이면 눈 감았다 뜨기 전에 종료된다. 

1. 두 정렬된 리스트를 합친다는건 어떻게 할까? 

병합정렬을 배우기 전에, 길이가 N, M인 두 정렬된 리스트를 합쳐서 길이 N+M의 정렬된 리스트를 만드는 방법을 알아야 한다. 

그림을 보고 제일 앞에 와야하는 수(가장 작은 수)는 어떻게 택해야 할지 생각해보자.

빨강 리스트와 파랑리스트의 모든 원소를 확인해야 할까?

아니다. 

-> 두 리스트의 가장 앞에 있는 원소만 비교하면 된다! 

왜냐하면 이미 정렬된 리스트이기 때문에 가장 작은 수가 이미 각 리스트의 맨 앞에 있다. 

"-9와 -7만 비교하면 -9가 제일 작으니까 리스트를 합쳤을 때 -9가 제일 앞에 오게 된다" 는 것을 O(1)에 알 수 있다. 

 

그러면 -9 다음에 오는 수는 어떻게 알까?

두 리스트의 맨 앞을 비교하면 1과 -7이 있다. -7을 선택한다.  

다음은? 두 리스트의 맨 앞을 비교하면 6과 1이 있다. 1을 선택한다.  

이렇게 비교 1번 당 1개의 원소를 제자리에 보낼 수 있으니까 정렬된 두 리스트를 합치는건 O(N+M)에 수행 가능하다. 

 

혼자 힘으로 '정렬된 배열 합치기'를 구현해보자.  백준 11782번 배열 합치기 문제를 풀고 오자.

11782번 문제 내 코드  아래는 바킹독님의 코드 

// http://boj.kr/eff70b5b64974fdebbcd7d2a1fdf29a5
#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++];
    else if(a[aidx] <= b[bidx]) c[i] = a[aidx++];
    else c[i] = b[bidx++]; 
  }
  for(int i = 0; i < n+m; i++) cout << c[i] << ' ';
}

2. Merge Sort 는 어떻게 구현할까? 

병합 정렬은 3단계로 요약할 수 있다.

step1. 주어진 리스트를 2개로 나눈다.
step2. 각각의 리스트를 정렬한다. 
step3. 정렬된 두 리스트를 합친다. 

"나눈 리스트는 어떤 방법으로 정렬할까?"

-> "재귀"에서 아이디어를 얻을 수 있다. 

재귀를 배울 때 도미노가 쓰러지는 것에 비유하여 귀납법을 이해했다. 

"1번 도미노가 쓰러지면 100번 도미노가 쓰러진다." 는 것을 납득시키려면? 

100번 도미노가 쓰러지려면, 99번 도미노가 쓰러져야하고, 99번 도미노가 쓰러지려면 98번 도미노가 쓰러져야 하고, ... 

2번 도미노가 쓰러지려면 1번 도미노가 쓰러져야 한다. 

일단 1번 도미노는 확실히 쓰러지게 되어 있으니까. 따라서 100번 도미노가 쓰러지면 1번 도미노가 쓰러진다.

이러한 귀납법을 병합 정렬에 적용하면. 

길이가 8인 리스트를 정렬하려면, 길이가 4인 리스트를 정렬할 수 있어야 하고. 

길이가 4인 리스트를 정렬하려면 길이가 2인 리스트를 정렬할 수 있어야 하고. 

길이가 2인 리스트를 정렬하려면 길이가 1인 리스트를 정렬할 수 있어야 하는데. 

길이가 1인 리스트는 아주 쉽게 정렬할 수 있으니까. 결국 우리는 {6, -8, 1, 12, 8, 15, 7, -7}를 정렬할 수 있다! 

3. 구현하기 전에 병합 정렬의 시간복잡도를 확인하자

병합 정렬의 전체 과정을 살펴보면, 리스트가 분할하는 과정과 합쳐나가는 과정으로 구분된다. 

1) 분할하는 과정 

분할한다는 것은 관념적으로 분할 되었다고 생각하는 것이다. 

함수 호출의 횟수는 각 줄별로 1, 2, 4, ... , 2의 k승 번이다. 이 횟수는 각 줄에 리스트가 몇 개 있는지 보면 된다. 

예를들어, 3번째 줄을 보자.

리스트가 {6, -8}, {1, 12}, {8, 15}, {7, -7} 총 4개가 있다. 각각에 대해 함수가 호출되니까 3번째 줄은 4번 호출된다. 

 

분할하는 과정에서 함수 호출은 1+2+4+ ... + 2의 k승 == 2N-1 = O(N)번 발생한다. 

즉, 분할하는 과정의 시간복잡도는 O(N)이다. 

 

2) 합쳐나가는 과정 

합쳐나가는 과정의 시간복잡도는 각 줄에서 모두 N번의 연산이 필요하다. 

아까 두 정렬된 리스트를 O(A+B)에 구하는 방법을 배웠다. 

그러면 각 줄에서 둘씩 짝지어 합쳐서 다음 단계로 넘어가려면 그냥 전체 원소의 갯수만큼 필요하다는 것을 알 수 있다. 

예를 들어, 5번째 줄을 보자. 

{-8, 6}, {1, 12}, {8,15}, {-7, 7} 길이가 N/4인 4개의 정렬된 리스트들을 2개씩 짝지어 합치는 상황이다. 

필요한 연산의 횟수는 N/4 + N/4 + N/4 + N/4 == N이 된다. 

분할이 완료됬을 때, 리스트의 원소는 1개 였다가 2의 k승 개가 될때까지 매번 2배씩 커지니까 줄은 k개다. 

(1개 -> 2개 -> 4개 -> 8개)

그렇기 때문에 합쳐나가는 과정은 O(Nk) == O(NlogN) 이다. 

분할하는 과정은 O(N)이고 합쳐나가는 과정은 O(NlogN)인데. O(N)보다 O(NlogN)이 더 크다. 

최종적으로 병합 정렬은 O(NlogN)의 시간복잡도를 가진다. 

4. [중요] 이제 직접 Merge Sort를 구현해보자. 

기본 틀 코드를 받아서 스스로 빈칸을 채워보자.

아래는 바킹독님의 정답 코드다. 

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

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
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로 다시 옮김
}

// a[st:en]을 정렬하고 싶다.
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] << ' '; // -53 3 12 15 16 22 23 25 46 357
}

 

merge함수에서 두 리스트를 합친 결과를 임시롤 저장할 곳이 필요해서 tmp 변수가 필요하다. 

merge_sort함수에서 배열의 크기가 1일 때는 아무것도 안해도 정렬이 완료된다.

이후에는 재귀적으로 절반을 나눠 각각 정렬이 되게 한다. 

 

아직 헷갈리더라도 이건 어려운 내용인것이 맞고 시간과 반복시도가 해결해주는 문제니까 계속 가면 된다.

백준 2751번 문제도 풀어보자. (바킹독님 2751번 정답코드) 

5. [중요] 병합 정렬의 Stable Sort 성질 

사람들을 나이 순으로 정렬하는 상황이 있다. 

검정셔츠 입은 사람만 38살이고, 나머지 색깔의 사람들은 21살이다. 나이순으로 생각하면 3가지가 모두 올바른 정렬이 맞다.

이렇게 우선 순위가 같은 원소가 여러 개일 땐 정렬 결과가 유일하지 않다!

그런데 그 중에서 우선순위가 같은 원소들 끼리는 원래의 순서를 따라가도록 하는 정렬이 Stable Sort 이다.

즉, 정렬 전에 나이가 21살인 사람의 순서가 파랑, 빨강, 초록이니까. 정렬 후에도 이 순서를 같게 두는 것이다. 

 

병합정렬은 Stable Sort인데. 이 성질을 만족시키려면, a와 b의 우선순위가 같을 때, a를 먼저 선택해줘야 한다. 

아까 병합 정렬은 구현했을 때 Stable Sort성질이 드러난 코드다.

  for(int i = st; i < en; i++){
    else if(arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++]; 
    // <-- arr[lidx] == arr[ridx]인 경우처럼 우선순위가 같다면? 앞에 있는 lidx를 먼저 선택해준다!
  }

Stable Sort를 응용해보자.

1) 파일을 정렬하는 경우 

조건: 파일을 크기 순으로, 크기가 동일하다면 먼저 생성된 순으로 정렬하자. 

병합 정렬은 Stable Sort임을 기억하자!

따라서 생성 시간은 신경쓰지 않고, 파일을 크기를 기준으로 정렬하면 조건을 만족시킬 수 있다. 

 

2) 2차원 좌표를 정렬하는 경우 

조건: x가 작은 순으로, x가 동일하다면 y가 작은 순으로 정렬하자. 

먼저 y 크기를 기준으로 병합 정렬을 수행하고, 그 다음에 x크기를 기준으로 병합 정렬을 수행하면 된다. 

이렇게 하면 Stable Sort성질 때문에 일단 x가 작은게 앞으로 오게 되기 때문이다. 

그리고 이 상태에서 x가 같다면, x를 정렬하기 전에 앞에있었을 원소, 즉 y가 작은 원소가 앞에 온다. 

 

다만, 2차원 좌표의 정렬은 병합 정렬2번이 아니라 a[aidx]와 b[bidx]를 비교하는 부분을 살짝 바꾸면 1번 정렬로도 해결된다. 

---

0x02 Quick Sort

퀵 소트는 거의 모든 정렬 알고리즘 보다 빠르다. 

[참고]

만약, 코딩테스트에서 STL을 못 쓰고 직접 정렬을 구현해야 한다면, 퀵 소트를 쓰지 말고, 머지 소트를 써야 한다. 

1. 퀵 소트는 머지 소트 처럼 재귀적으로 구현되는 정렬이다. 

매 단계마다 pivot이라는 원소를 알맞은 자리로 보내는 작업을 반복한다. 

아래 조건을 만족하면 pivot은 올바른 자리에 있는 것이다. 
1) pivot 왼쪽은 전부 pivot 보다 작은 원소들 
2) pivot 오른쪽은 전부 pivot보다 큰 원소들 

퀵 소트의 장점은 추가적인 공간이 필요 없다는 점이다.

배열 안에서 포인트 변수2개를 이용해 자리 바꿈만으로 처리할 수 있다. (그래서 cache hit rate가 높아서 속도 빠름)

참고로 이렇게 추가적인 공간이 필요 없는 정렬을 In-Place Sort라고 부른다. 

pivot을 제외하고, 양쪽 끝에 포인터를 두고 적절하게 스왑하자. 

우선 l, r 이라는 포인터 2개를 둔다. pivot은 처음에 0번째 원소로 정한다. 

l은 1번째에서 오른쪽으로 이동하고, r은 맨 마지막 인덱스에서 왼쪽으로 이동한다. 

l은 pivot보다 큰 값이 나올때 까지 오른쪽으로 이동한다. r은 pivot보다 작은 값이 나올 때 까지 왼쪽으로 이동한다. 

그 다음 두 포인터가 가리키는 원소의 값을 스왑한다. l은 12에 도달했다. r은 -7에 도달했다. 

또 다시 l을 이동시키면 6보다 큰 8에 도달한다. r은 6보다 작은 3에 도달한다. 

그러면 3과 8을 스왑한다. 

l을 옮기려고 보니 r이 l보다 왼쪽에 와있다!  이렇게 r이 l보다 작아진 순간에는 멈춰서 pivot을 r과 스왑하면 된다. 

여기까지가 pivot하나를 올바른 자리에 두는 과정이다. 

이 방법이 왜 pivot을 제자리로 보내는지 이해하려면

"모든 순간에 l의 왼쪽에는 pivot보다 작거나 같은 원소들만 있고, r의 오른쪽에는 pivot보다 큰 원소들만 있다"는 점만 주목하면 된다. 

2. 퀵 소트를 구현한 코드 

인덱스 l 은 pivot보다 큰 원소를 찾을 때 까지 이동한다. 

인덱스 r 은 pivot보다 작은 원소를 찾을 때 까지 이동한다. 

만약 l 과 r이 타겟을 못찾으면 l > r 이 된다. 인덱스 l과 r이 역전되버린다. 이 때는 break 로 탐색을 멈춘다. 

l 과 r이 타겟을 찾으면, swap(arr[l], arr[r]) 스왑 한다! 

스왑이 종료되면, 인덱스 r과 인덱스 pivot을 스왑한다. 

그리고  pivot을 기준으로 왼쪽과 오른쪽을 보면 pivot이 올바른 자리에 있음을 확인할 수 있다. 

나머지 부분은 재귀호출해서 정렬시킨다. 

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

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en) { // arr[st to en-1]을 정렬할 예정
  if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
  int pivot = arr[st]; // 제일 앞의 것을 pivot으로 잡는다. 임의의 값을 잡고 arr[st]와 swap해도 상관없음.
  int l = st+1; // 포인터 l
  int r = en-1; // 포인터 r
  while(1){
    while(l <= r && arr[l] <= pivot) l++;
    while(l <= r && arr[r] >= pivot) r--;
    if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
    swap(arr[l], arr[r]);
  }
  swap(arr[st], arr[r]);
  quick_sort(st, r);
  quick_sort(r+1, en);
}

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

 

3. 퀵 소트의 시간복잡도 

pivot 하나를 올바른 자리에 보낼 때 마다 상수번의 연산으로 l과 r이 한 칸씩 가까워진다.

따라서 한 세트의 시간복잡도는 O(N)이다. 

재귀 종료 조건인 base condition은 구간의 길이가 1 이하일 때다. pivot을 제자리로 보낸 뒤에, 재귀적으로 자기 자신을 호출한다.

pivot 하나를 올바른 자리에 보내는 세트가  O(N)이 걸리는데. 

pivot 을 하나씩 제외하면 N, N-1, N-2 ... 번의 연산이 필요하다. 

4. 퀵 소트의 단점? 

만약 pivot이 매번 완벽하게 중앙에 위치한다면?

리스트를 균등하게 반으로 쪼개서 재귀를 호출하게 된다. 

이 때는 n, n/2, n/4 ... 번의 연산이 필요할 것이다. 그러면 머지 소트때와 같이 세트마다 O(logN)이 걸린다. 

한 세트의 연산횟수 N과 재귀 호출 연산횟수 logN을 곱하면 된다. 

 

물론 항상 pivot이 완벽하게 중앙에 오지 않겠지만 대략 시간복잡도는 O(NlogN)이 된다. 

그리고 앞서 말한 cache hit rate가 높아서 퀵 소트는 속도가 굉장히 빠르다.

 

{1,2,3,4,5,6,7,8} 을 퀵 소트로 정렬하면 시간 복잡도가 얼마일까? 

pivot은 항상 중앙에 있는게 아니라. 제일 왼쪽에 위치하게 된다. 

그래서 한 단계마다 longN개가 아니라 N개를 확인해야 한다. -> 시간복잡도는 O(N^2)이 된다. 

퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이다. 

단순히 제일 왼쪽 값을 pivot으로 선택해보면 지금처럼 리스트가 오름차순 이거나 내림차순일 때 O(N^2)이 된다. 

 

[참고]

STL을 못 쓰는 경우, 정렬을 직접 구현해야 한다면 퀵 소트를 쓰는게 아니라 머지 소트를 구현하라고 한 이유가 여기에 있다. 

최악의 경우 O(N^2)의 시간복잡도인 퀵 소트를 쓸 필요가 없다. 

하지만 대부분의 정렬 라이브러리는 퀵 소트를 쓰는 것도 사실이다. 

pivot을 '잘'고르는 것이 관건인데. 랜덤으로 선택하거나. 후보 3개를 정해서 중앙값을 선택하기도 한다. 

최악의 경우에도 O(NlogN)을 보장하기 위해 일정 깊이 이상의 재귀가 호출되면 힙 소트로 정렬한다.

재귀가 과도하게 호출되면 오버헤드 때문에 성능저하가 오는 데 이를 피하기 위함이다. 이러한 정렬을 Introspective sort라고 한다. 

---

5. 머지 소트 VS 퀵 소트 

머지소트와 퀵 소트는 둘 다 재귀적 구조로 구현된다. 

먼저 시간복잡도를 보면 머지소트는 무조건 O(NlogN)이고. 퀵 소트는 최악에 O(N^2), 평균적으로 O(NlogN)이다. 

평균적으로 (이름값하는) 퀵 소트가 빠르다. 

퀵 소트는 In-Place Sort 인 점을 기억하자. 

그리고 머지 소트는 우선 순위가 같은 원소들끼리의 원래 순서가 유지되는 Stable Sort이지만 퀵 소트는 아니다. 

---

정렬1 문제집

백준 문제	내 코드
2750 수 정렬하기	2750 내 코드
2751 수 정렬하기 2	2751 내 코드(머지소트 구현)
10989 수 정렬하기 3	10989 내 코드 (메모리 제한 주의 )
11931 수 정렬하기 4	11931 내 코드(머지소트 구현)
15688 수 정렬하기 5	15688 내 코드 (머지소트 구현)
10814 나이순 정렬	10814 내 코드
11650 좌표 정렬하기	11650 내 코드
11651 좌표 정렬하기 2	11651 내 코드

 

---

다음 시간에는 정렬2(Counting Sort, Radix Sort)를 배운다. 

공부 자료 출처 : 바킹독 알고리즘 정렬1