2018-10-13프로그래밍 / 알고리즘

정렬 알고리즘 정리 (Bubble, Selection, Insertion, Merge, Quick)

이번 포스팅에서는 대표적인 정렬알고리즘 5가지와 대략적인 빅오표기법에 대해서 정리하려고 한다. 먼저, 그 5가지 정렬알고리즘은 다음과 같다.

버블정렬(Bubble sort)
선택정렬(Selection sort)
삽입정렬(Insertion sort)
병합정렬(Merge sort)
퀵정렬(Quick sort)

그리고 이 알고리즘들의 성능은 빅오표기법으로 표현하므로, 빅오표기법에 대한 설명도 간단히 하고 넘어가려한다.

Big O 표기법과 시간복잡도

알고리즘들의 성능을 판단하는 지표로는 시간 복잡도(Time Complexity)와 공간 복잡도(Time Complexity)가 있다. 시간 복잡도는 알고리즘의 수행시간을 의미하는 지표이며, 공간 복잡도는 알고리즘의 메모리 사용량을 의미한다.

보통 알고리즘에 대해서 공부하다보면 이 알고리즘의 시간복잡도는 O n입니다 혹은 O의 n제곱입니다 이런 식으로 이야기하거나 $O(n)$ 이런 식으로 작성되어있는 것을 볼 수 있었을 것이다.

이게 바로 빅오(Big O) 표기법이다. 말로 풀어보자면 $O(n)$ 의 의미는 다음과 같다.

이 함수는 n만큼의 데이터가 주어졌을 때, “최악”의 경우 n만큼의 리소스를 소모한다

이때 위에서 말한 리소스는 시간복잡도라면 시간이고 공간복잡도라면 메모리공간이 될 것이다. 하지만 보통 정렬알고리즘을 평가할때는 주로 시간복잡도에 집중하므로 여기서는 시간복잡도만 살펴보도록 하겠다.

먼저 시간복잡도에 대한 이해를 더 하기위해 이진탐색 알고리즘의 시간복잡도를 살펴보자. 혹시 이진탐색을 잘모르는 사람은 술게임인 업다운을 생각해보자. 다들 잘 알겠지만 업다운은 다른 사람이 생각한 임의의 숫자를 맞춰야하는 게임이다.

이때, 가장 질문을 최소화할 수 있는 방법은 무엇일까? 바로 첫 질문에 중간 값인 50을 부르는 것이다. 50을 부르고 상대방이 업 또는 다운을 하게되면 우리는 반대쪽에 있는 50개의 수는 버리고 나머지 50개만 다시 생각하면 되는 것이다.

만약 운좋게 상대방이 생각한 수가 50이라면 바로 게임이 끝나고 상대방은 벌주를 먹게 된다.

어쨌든 이 게임에서 최악의 경우는 계속 업 & 다운을 반복하다가 $O({\log}N)$ 번만에 끝나는 것이고 최선의 경우는 찾고자 하는 값을 첫 번째 추측으로 맞춰버린 상황. 즉, 시간복잡도는 $O(1)$ 이 된다.

보는 바와 같이 최선의 결과와 최악의 결과 간 차이는 늘 있을 수 밖에 없기 때문에 보통 알고리즘을 평가할 때는 주로 최악의 경우를 생각한다. 그리고 이런 최악의 경우를 표현할 때 바로 빅오 표기법을 사용하는 것이다.

자주 나오는 것들은 보통 $O(1)$ , $O(n)$ , $O(n^2)$ , $O({\log}N)$ 정도가 있는데 알기 쉽게 2차원 그래프로 그려보면 다음과 같이 나타난다.

빅오 표기법의 계산방법과 같은 더 자세한 내용은 다른 포스팅에서 다시 설명하도록 하겠다.

정렬알고리즘

정렬알고리즘은 컴퓨터 공학에서 중요시되는 문제 중 하나로, 어떤 데이터셋이 주어졌을 때 이를 정해진 순서대로 나열하여 재배치하는 문제이다.

실제 개발을 하다보면 불규칙한 데이터들을 정렬 후 탐색해야하는 경우가 꽤나 많이 발생하게 되는데 이때 상황에 맞는 알고리즘을 사용하여 효과적으로 문제를 해결할 수 있느냐가 핵심이라고 볼 수 있다.

예를 들어 1부터 10까지 적혀있는 공이 불규칙하게 들어있는 주머니에서 공을 하나씩 꺼내어 작은 수부터 큰 수의 순서로 공을 나열한다고 생각해보자. 보통 이런 경우 사람도 어렵지 않게 쓱쓱 정렬해낸다. 하지만 컴퓨터가 주로 다루는 데이터는 10,000개일수도 10,000,000개일수도 있다. 그리고 데이터베이스 같은 경우는 이론상 무한 개의 데이터를 다룰 수 있어야 한다.

이때 데이터가 정렬되어 있지 않다면 순차적으로 하나씩 데이터를 봐가면서 탐색해야하지만, 데이터가 이미 정렬되어있다면 위에서 예시로 들었던 이진탐색(Binary Search)와 같은 강력한 알고리즘을 사용할 수도 있다.(사실 이게 제일 큰 이유이다)

자 그럼 대표적인 정렬알고리즘인 버블정렬, 선택정렬, 삽입정렬, 병합정렬, 퀵정렬을 한번 살펴보도록 하자.

버블정렬(Bubble sort)

버블정렬은 거의 모든 상황에서 최악의 성능을 보여주지만, 이미 정렬된 자료에서는 1번만 순회하면 되기 때문에 최선의 성능을 보여주는 알고리즘이다. 이미 정렬되어 있는 데이터를 왜 정렬하냐는 의문이 들 수 있지만, 정렬알고리즘 자체는 데이터가 정렬되어 있는지 아닌지 모르고 작동하는 것이기 때문에 의미는 있다.

버블정렬은 다음과 같은 순서로 작동한다.

0번째 원소와 1번째 원소를 비교 후 정렬
1번째 원소와 2번째 원소를 비교 후 정렬
…
n-1번째 원소와 n번째 원소를 비교 후 정렬

한번 순회할 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여서 버블정렬이라고 부른다. 원리도 직관적이라서 구현하기 편하긴 하지만 꽤나 비효율적인 정렬 방식이다. 그래서 보통 처음 배울 때 한번 짜보고 나면 실무에서 쓰는 경우는 거의 못 봤다.(물논 시간이 없다면 쓸 수도 있다…)

버블정렬의 구현코드는 다음과 같다.

function bubbleSort (input) {
  const len = input.length;
  let tmp = null;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (input[j] > input[j + 1]) {
        // Swap
        tmp = input[j];
        input[j] = input[j + 1];
        input[j + 1] = tmp;
        tmp = null;
      }
    }
  }
  return input;
}

선택정렬(Selection sort)

선택정렬은 주어진 자료들 중에 현재 위치에 맞는 자료를 찾아 선택하여 위치를 교환하는 정렬 알고리즘이다. 한번 순회를 돌게되면 알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하게 되므로 그 다음 순회부터는 1번 인덱스부터 순회를 돌며 반복하면 된다.

선택정렬은 다음과 같은 순서로 작동한다.

0번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 0번째 인덱스와 swap한다
1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 1번째 인덱스와 swap한다
…
n-1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 n번째 인덱스와 swap한다

선택정렬은 현재 자료가 정렬이 되어있던말던 무조건 전체 리스트를 순회해가며 검사하기 때문에 최선의 경우든 최악의 경우든 한결같이 $O(n^2)$ 의 시간복잡도를 가지고 있다. 선택정렬의 구현코드는 다음과 같다.

function selectionSort (input) {
  const len = input.length;
  let tmp = null;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (input[i] < input[j]) {
        // Swap
        tmp = input[j];
        input[j] = input[i];
        input[i] = tmp;
        tmp = null;
      }
    }
  }
  return input;
}

삽입정렬(Insertion sort)

삽입정렬은 주어진 자료의 모든 요소를 앞에서부터 차례대로 정렬된 자료 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬이다. 사실 인간이 직접 정렬하는 순서와 제일 흡사하다고 할 수 있는 정렬인데, 직접 손안에 있는 카드를 정렬한다고 생각해보자. 대충 다음과 같은 순서로 행동할 것이다.

카드를 하나 고른다.
내가 가지고 있는 카드를 쭉 살펴본다.
현재 카드가 들어가야할 순서에 카드를 껴넣는다.

삽입정렬은 이 순서와 비슷하게 작동한다.

0번 인덱스는 건너뛴다.
0~1번 인덱스 중 1번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
0~2번 인덱스 중 2번 인덱스 값이 들어가야할 위치를 찾아서 넣는다
…
0~n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 넣는다

삽입정렬은 최선의 경우 전체 자료를 한번만 순회하면 되기때문에 $O(n)$ 의 시간복잡도를 가지지만 최악의 경우 $O(n^2)$ 의 시간복잡도를 가진다.

삽입정렬의 구현코드는 다음과 같다.

function insertionSort (input) {
  const len = input.length;
  for (let i = 1; i < len; i++) { // 두번째 카드부터 시작
    const value = input[i]; // 카드를 잡는다
    let j = i-1;
    for (;j > -1 && input[j] > value; j--) {
      // 이미 정렬된 카드들을 뒤에서부터 살펴보다가
      // 살펴본 카드가 현재 카드보다 크다면
      // 살펴본 카드를 뒤로 한칸 보낸다
      input[j+1] = input[j];
    }
    // 뒤로 보내는 행위가 끝나면
    // 현재 카드보다 작은 카드의 한칸 뒤에
    // 현재 카드를 위치시킨다
    input[j+1] = value;
  }
  return input;
}

병합정렬(Merge sort)

병합정렬은 일종의 분할 정복법 중 하나로 큰 문제를 작은 여러 개의 문제로 쪼개서 각각을 해결한 후 결과를 모아서 원래의 문제를 해결하는 방법이다. 병합이라는 이름 그대로 주어진 자료를 잘게 쪼갠 뒤 합치는 과정에서 정렬을 하는 알고리즘이다. 순서를 살펴보면 다음과 같다.

[5, 0, 4, 1]라는 자료를 받았다
length가 1이 될때까지 자료 리스트를 반으로 쪼갠다
[5, 0], [4, 1]가 된다.
[5], [0], [4], [1]가 된다
각 리스트의 길이가 1이 되었으므로 병합을 시작한다
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합. [5]와 [0] 중 0이 더 작으므로 새로운 리스트에 0을 먼저 병합한다
[0, 5] 생성
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합. [4]와 [1] 중 1이 더 작으므로 새로운 리스트에 1을 먼저 병합
[1, 4] 생성
이제 [0, 5]와 [1, 4]를 병합한다. 이 리스트들은 정렬되었기 때문에 작은 인덱스일 수록 작은 값을 가진다는 것이 보장되어있다.
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[0] 생성. [5]와 [1, 4]가 남았다
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[0, 1] 생성. [5]와 [4]가 남았다
왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합
[0, 1, 4] 생성. [5]가 남았다
값이 남았으므로 그냥 병합해준다.
[0, 1, 4, 5] 정렬완료

위 과정 중에서 강조 처리된 왼쪽의 0번 인덱스와 오른쪽의 0번 인덱스를 비교하여 적은 값을 먼저 병합 을 보면 이 과정이 계속 반복되고 있는 것을 볼 수 있다.

같은 방식으로 계속 반복하여 병합하고 있기 때문에 병합정렬은 보통 재귀함수로 구현한다. 또한 병합정렬은 항상 $O({n\log n})$ 의 시간복잡도를 가지기 때문에 효율적이다. 그러나 원소의 개수만큼 리스트를 쪼개고 따로 저장하고 있어야하기 때문에 $O(n)$ 의 공간복잡도를 가진다. 한마디로 메모리를 팔아 수행속도를 얻는 경우라고 할 수 있다.

병합정렬의 구현코드는 다음과 같다

function merge (left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    }
    else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while(right.length) {
    result.push(right.shift());
  }
  return result;
}

function mergeSort (input) {
  if (input.length < 2) {
    return input;
  }
  const middle = parseInt(input.length / 2);
  const left = input.slice(0, middle);
  const right = input.slice(middle, input.length);
  return merge(mergeSort(left), mergeSort(right));
}

퀵정렬(Quick sort)

퀵정렬도 병합정렬과 마찬가지로 분할정복을 통한 정렬방법이다. 병합정렬과의 차이점은 병합정렬은 분할 단계에서는 아무것도 하지않고 병합하는 단계에서 정렬을 수행하지만, 퀵정렬은 분할 단계에서 중요한 작업들을 수행하고 병합시에는 아무것도 하지않는다는 점이다.

퀵정렬의 수행 순서는 다음과 같다.

입력된 자료 리스트에서 하나의 원소를 고른다. 이 원소를 피벗이라고 부른다.
피벗을 기준으로 리스트를 둘로 분할한다.
피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮긴다
피벗을 기준으로 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮긴다

function quickSort(arr, left, right) {
  if (left < right) {
    //기준점을 찾고 기준점을 중심으로 더 작은수, 더 큰수 분류
    const i =  position(arr, left, right);
    //기준점 기준 좌측 정렬
    quicksort(arr, left, i - 1);
    //기준점 기준 우측 정렬
    quicksort(arr, i + 1, right);
  }
  return arr;
}
function position (arr, left, right) {
  let i = left;
  let j = right;
  const pivot = arr[left];

  //제자리 더 큰수/더 작은 수 좌우 배치.
  while (i < j) {
    while (arr[j] > pivot) j--;
    while (i < j && arr[i] <= pivot) i++;

    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  arr[left] = arr[j];
  arr[j] = pivot;

  return j;
}

이상으로 정렬 알고리즘 포스팅을 마친다.