정렬(sort) 알고리즘

October 31, 2018 Computer Science

정렬 알고리즘

정렬 알고리즘이란, 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.

정렬 알고리즘은 명함을 어떤 순서로 정리할까?와 같은 문제이다.
1만장의 명함이 있고, 가나다 순으로 정리되어 있는데, 어느 날 새로운 명함을 받았다면, 그 명함을 가나다 순에 맞춰 끼워 넣어야 한다면 그 뒤에 명함들은 한 칸씩 뒤로 밀어야 하는 번거로움이 있다. 밀리는 명함이 1장일 수도 있고, 수천장일 수도 있다. 즉, 가나다 순으로 명함을 정리해두는 것이 머릿속에서는 편리하다고 생각되더라도 실제 관리하기에는 여간 불편한 것이 아니다.

정렬 알고리즘에서 중요한 점은 2가지다.

어떤 데이터를 사용하는가?
어떤 정렬 조건을 사용하는가?

데이터를 정렬할 때, 무조건 하나의 정렬 알고리즘을 사용하는 것은 바람직하지 않다. 데이터를 정렬할 여러 가지 조건(데이터의 개수, 사용할 수 있는 메모리의 양 등)을 분석해서 가장 합당한 정렬 알고리즘을 선택하는 지혜가 필요하다.

정렬 알고리즘 종류

퀵 정렬 알고리즘(Quick Sort)
병합 정렬 알고리즘(Merge Sort)
버블 정렬 알고리즘(Bubble Sort)
선택 정렬 알고리즘(Selection Sort)

퀵 정렬 알고리즘(Quick Sort)

퀵 정렬 알고리즘: 리스트의 한 요소를 피벗(Pivot: 기준값)으로 선정한 다음, 피벗보다 작은 요소를 하위(왼쪽) 리스트로, 피벗보다 큰 요소를 상위(오른쪽) 리스트로 이동시키는 알고리즘이다.

예를 들어, 배열 [3, 9, 4, 7, 5, 0, 1, 6, 8, 2] 있다고 해보자. 여기서 피벗을 5라고 정하고, 5보다 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 보내는 작동 방식에 대해 알아보자.

왼쪽 맨끝을 s(시작 포인트), 오른쪽 맨끝을 e(끝 포인트)라고 하자.
s부터 피벗과 비교해서, s가 피벗보다 작으면 s는 오른쪽으로 한칸 이동후, 피벗과 비교한다.
만약, s가 피벗보다 크면 잠깐 멈춰있고, e를 피벗과 비교하기 시작한다.
e가 피벗보다 크면 e는 왼쪽으로 한칸 이동후, 피벗과 다시 비교한다.
만약, e가 피벗보다 작으면 잠깐 멈춘후, 아까 멈춘 s의 값과 서로 바꾼다.(swap)
위 배열에서 s는 9가 되고, e는 2가 된다. 이 두 개의 숫자를 서로 바꾼다.
그럼, [3, 2, 4, 7, 5, 0, 1, 6, 8, 9] 배열이 된다.
그리고, 다시 s를 한칸 오른쪽으로 이동후, 피벗과 비교한다.
만약, s의 값이 피벗보다 클 경우, 잠깐 멈춰있고, e도 피벗과 비교하기 시작한다.
이런식으로 1바퀴를 돌게 되면 배열은 다음과 같다. [3, 2, 4, 1, 0, 5, 7, 6, 8, 9]
s와 e가 서로 정한 범위를 벗어나게 되면, 이 루프가 끝나게 된다.
그러면 총 2개의 partition(smaller/bigger)이 만들어진다.
그 다음에는, 양쪽 배열(partition)을 가지고 반복적으로 퀵 정렬 함수를 재귀적으로 호출하면, partition의 값이 1개가 될 때까지 계속적으로 반복해서 작은 값과 큰값의 위치를 바꾸게 된다.
이때, partition이 왼쪽/오른쪽에 1개면 더이상 재귀호출을 하지 않는다.

퀵 정렬 알고리즘은 큰 데이터 집합을 가장 빨리 정렬할 수 있는 알고리즘이다.

function qSort(arr) {
    if (arr.length == 0) {
        return [];
    }
    let left = [];
    let right = [];
    const pivot = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }
    return qSort(left).concat(pivot, qSort(right));
}
console.log(qSort([3, 9, 4, 7, 0, 1, 5, 8, 6, 2])); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]


// random input array for test
var a = [];
for (var i = 0; i < 10; ++i) {
   a[i] = Math.floor((Math.random()*100)+1);
}
console.log(a);
console.log(qSort(a));

위 코드의 시간복잡도를 계산하면 T(n) = nlogn 이다. 이것을 Big-O 표기법으로 나타내면 O(nlogn)이다. partion을 나누는 수가 n번인데, 이는 partion을 계속 나누다 보면, 결국 낱개가 될 때까지 나누기 때문이다. 그런데 1번 나누면, 2번째 나눌 때는 전체에서 2개로 나눈 결과를 가지고 또 나누는 것이기 때문에, 검색해야하는 데이터의 양이 줄어들었다. 마치, 이진 탐색 알고리즘과 같다. 그래서 logn번 검색하게 된다. 즉, n * logn = nlogn인 시간복잡도가 된다.

그러나, 예외도 있다. partion을 나누기 위한 pivot(기준값)이 전체 배열에서 최소값/최대값일 경우, 시간복잡도는 O(n^2)이 된다. 예를 들어, pivot(기준값)이 전체 배열에서 최소값일 경우, 제일 왼쪽으로 들어가고, 나머지 데이터에서 pivot(기준값)이 또 최소값이어서 이런식으로 된다면, 결국 모든 데이터를 모두 돌게 되어, 시간복잡도가 O(n^2)dl 된다. 하지만, 확률적으로 이런 경우는 거의 없기 때문에, 보통의 시간복잡도는 O(n^2)이 된다.

병합 정렬 알고리즘(Merge Sort)

병합 정렬 알고리즘: 함수가 호출 될때마다, 절반씩 잘라서 재귀적으로 함수를 호출하고 맨끝에 제일 작은 조각부터 두 개씩 병합해서 정렬된 배열을 병합해나가는 방식이 병합 정렬 알고리즘이다. 이미 정렬되어 있는 데이터들을 하나로 합해서 정렬하는 방법. 이러한 정렬 방법은 데이터들을 정렬하는 경우에도 사용되지만 파일에 정렬되어 있는 데이터들을 하나로 합쳐서 정렬하는 경우에도 종종 사용된다. 이미 정렬되어 있는 데이터 그룹들 혹은 묶음들을 하나로 합할 때 사용할 수 있다.

병합 정렬 알고리즘을 사용하는 경우 배열 하나에 저장된, 정렬되지 않은 데이터들을 어떤 방식으로 정렬하는 지 알아보자.

예)
정렬되지 않은 데이터가 있다고 해보자. 하나의 데이터 배열을 여러 개로 나누어서, 나중에 병합 하기 위해 묶는데, 이 묶은 데이터 그룹을 런(Run)이라고 한다. 2-way 방식은 2개씩 그룹으로 묶는다. 일단 2개씩 묶으면, 각 그룹별로 정렬을 한다. 예를 들어, 6과 1이 하나의 그룹으로 묶였다면, 1이 왼쪽에 오고, 6이 오른쪽에 오는 식으로 정렬을 한다. 그 다음으로는 2개의 런을 묶어서 하나의 런으로 합하도록 정렬한다. 만약 2, 3 런과 5, 7 런이 하나의 런으로 합쳐진 다음, 2, 3, 5, 7 사이에서 정렬이 된다. 이렇게 런(그룹)을 계속 합쳐나가면서 하나의 런으로 모두 합쳐 정렬하는 방식을 병합 정렬 알고리즘이라고 한다.

병합 정렬의 핵심은 1부터 하나의 런에 들어가는 데이터의 수를 2의 배수 기준으로 늘려서 병합하는 과정을 반복하는 것이다. 이와 같이 반복해서 병합하게 되면 결국 전체 데이터를 모두 정렬하게 되는 결과를 얻을 수 있다.

병합 정렬 알고리즘의 성능은 수치적으로만 보면 퀵 정렬 알고리즘과 비슷하다. 퀵 정렬 알고리즘이나 병합 정렬 알고리즘이나 데이터를 나눈 후에 재귀 호출을 사용하기 때문이다.

// 퀵정렬과 마찬가지로 분할 정복 알고리즘중 하나이다.
function MergeSort(arr) {
  const len = arr.length;
  if(len == 1) {
    return arr;
  }

  const middle = Math.floor(len / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, len);

  function merge(left, right) {
    let 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;
  }

  return merge(MergeSort(left), MergeSort(right));
}

위 코드의 시간복잡도를 계산하면 T(n) = nlogn 이다. 이것을 Big-O 표기법으로 나타내면 O(nlogn)이다. n개 만큼씩 logn번 돌기 때문에, 병합 정렬 알고리즘의 시간복잡도는 O(nlogn)이 된다. partition이 낱개가 될 때까지 쪼개지니까 n번 호출에, 1번 호출당 검색해야하는 데이터의 양이 절반씩 줄어드니까 logn이다. 따라서 n * logn = nlogn 시간복잡도가 된다. nlogn 시간복잡도는 이진 탐색 알고리즘에서 한 번 돌 때마다 검색 영역에 절반씩 떨어지는 것과 같은 원리이다.

병합 정렬 알고리즘은 물리적으로 배열의 가운데 값으로 partition을 나누기 때문에 최악의 경우에도 시간복잡도는 O(nlogn)이다. 퀵 정렬 알고리즘으로 따지면, pivot(기준값)을 잘 골랐을 때랑 비슷하다. 퀵 정렬 알고리즘도 최악의 경우가 아니라면, 병합 정렬 알고리즘과 같은 시간복잡도는 O(nlogn)이다.

하지만, 병합 정렬 알고리즘은 실행시에 별도의 저장공간을 필요로 하기 때문에, 공간을 사용할 수 없는 경우에는 퀵 정렬 알고리즘을 사용해야 한다.

버블 정렬 알고리즘(Bubble Sort)

버블 정렬 알고리즘: 순차적으로 바로 옆에 있는 데이터와 비교해서 옆의 데이터가 크면 자신과 위치를 바꾼다. 즉, 첫 번째 데이터가 가장 크다면 계속 옆에 있는 데이터와 자리를 바꾸면서 해당 데이터는 결국 맨 끝으로 이동하게 된다. 그리고 두 번째 위치에 있는 데이터를 또다시 옆에 있는 데이터와 비교한다. 이와 같은 과정을 마지막 데이터의 바로 전 데이터까지 반복해서 실행한다. 이 형태가 마치 버블이 부글부글 올라가는 것과 같다고 하여 버블 정렬 알고리즘이라고 한다.

예를 들어, [3, 5, 4, 2, 1] 배열이 있으면, 먼저 3과 5를 비교해서 3이 5보다 크면 둘을 바꾼다. 그런데 여기서는 5가 크므로 그대로 둔다. 그 다음은 5와 4를 비교한다. 이때, 5가 4보다 크므로 그 둘을 바꾼다. 그럼 [3, 4, 5, 2, 1] 배열이 이렇게 바뀐다. 이런식으로 비교하면 결국 5가 제일 마지막으로 이동하게 된다. 즉, [3, 4, 2, 1, 5] 배열이 된다. 그럼 가장 큰 수인 5가 배열에 제일 오른쪽으로 이동하게 되고, 다시 맨 처음부터 이웃 숫자끼리 비교한다. 이런식으로 가장 큰 수를 오른쪽으로 이동시켜 정렬하는 방식을 버블 정렬 알고리즘이라고 한다.

성능이 좋은 편이 아니라, 자주 사용되지는 않는다.

// 스왑 헬퍼 => 배열의 위치를 바꾼다.
function swap(arr, index1, index2) {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

// 버블 정렬은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식
function BubbleSort(arr) {
  let len = arr.length;
  for(let outer = len; outer > 1; outer--) {
    for(let inner = 0; inner < outer; inner++) {
      if( arr[inner] > arr[inner + 1]) {
        swap(arr, inner, inner+1);
      }
    }
  }
  return arr;
};

위 코드의 시간복잡도를 계산하면 T(n) = n^2 이다. 이것을 Big-O 표기법으로 나타내면 O(n^2)이다. 앞에서부터 한 개씩 뒤로 가면서 전체 배열 데이터를 돌기 때문에 n^2 만큼 시간이 걸린다.

선택 정렬 알고리즘(Selection Sort)

선택 정렬 알고리즘: 데이터의 처음부터 끝까지 쭉 훑어가면서 가장 작은 값을 찾아 그 값을 첫 번째 데이터와 자리를 바꾸고, 두 번째로 작은 데이터를 찾아 두 번째의 데이터와 자리를 바꾸는 방법으로 구현하는 정렬 알고리즘이다.

예를 들어, [3, 5, 4, 2, 1] 배열이 있으면, 변수 min = 3으로 할당하고, 그 다음 데이터인 5부터 하나씩 비교해 나간다. 이때, 가장 작은 값이 1 이므로 맨 앞에 있는 3과 1을 바꾼다. 그리고, 다시 두번째 요소인 5부터 오른쪽으로 하나씩 비교하면서 가장 작은 값을 찾아 5와 바꾼다. 이런식으로 정렬하는 방식이 선택 정렬 알고리즘이다.

// 스왑 헬퍼 => 배열의 위치를 바꾼다.
function swap(arr, index1, index2) {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

// 선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식
function SelectionSort(arr) {
  let min;
  for(let outer = 0; outer < arr.length -1; ++outer) {
    min = outer;
    for(let inner = outer + 1; inner < arr.length; ++inner) {
      if( arr[inner] < arr[min] ) {
        min = inner;
        }
      }
    swap(arr, outer, min);
  }
  return arr;
}

위 코드의 시간복잡도를 계산하면 T(n) = n^2 이다. 이것을 Big-O 표기법으로 나타내면 O(n^2)이다. 앞에서도 한칸씩 가면서 갈때마다 각 배열 요소를 한번씩 다시 돌기 때문에, n^2 만큼 시간이 걸린다.