저번에 살펴봤던 기본적인 정렬 알고리즘에 이어 이번에는 조금 어려운 정렬 알고리즘을 살펴보자. 물론 이번 것도 어려운 것은 아니지만 상대적으로 비교해봤을 때 저번 정렬 알고리즘들보다 어렵다!

# 쉘 정렬

  • 삽입 정렬을 보완한 알고리즘이다.
  • 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠르다는 것에 착안한 것이다.
    • 삽입 정렬의 최대 문제점 : 요소들이 삽입될 때, 이웃한 위치로만 이동한다.
    • 다시 말해서 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야 제자리로 갈 수 있다.
    • 삽입 정렬과 다르게 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 그래서 요소들이 멀리 떨어진 위치로 이동할 수 있다.

기본 로직은 아래와 같다.

  1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류한다.
  2. 연속적이지 않은 여러 개의 부분 리스트를 생성한다.
    (실제로 여러 개의 부분 리스트가 생기고 이것들을 병합하는 것이 아니라, 단순히 gap 값으로 간격을 주어 부분 리스트가 만들어진 것처럼 구현한다. )
  3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.
  4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복한다.
  5. 위의 1~4번까지의 과정을 리스트의 개수가 1이 될 때까지 반복한다.

기본 로직은 이렇지만 사실 잘 와닿지 않는다. 한 번 더 살펴보자.

  • 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때, k를 간격(gap)이라고 한다.
    • 간격(gap) 즉 k의 초기값 : (정렬할 값의 개수) / 2
    • 생성된 부분 리스트의 개수는 gap과 같다.
  • 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
    • 간격은 홀수로 하는 것이 좋다. (간격을 정하는 방법은 여러가지다.)
    • 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만든다.
  • 간격 k(gap)가 1이 될 때까지 반복한다.

장점

  • 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다.
  • 부분 리스트는 어느 정도 정렬된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 쉘 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 정렬된 상태이므로 삽입 정렬보다 더욱 빠르게 수행된다.
  • 알고리즘이 간단해서 쉽게 구현이 가능하다.

시간 복잡도

  • 평균 : O(N^1.5)
  • 최악의 경우 : O(N^2)

장점

  • 연속적이지 않은 부분 리스트에서 자료의 교환을 진행하여 더 큰 거리를 이동한다. 기존의 삽입 정렬에서는 한 칸씩 이동하며 비교를 하여 key 값의 자리를 찾았기 때문에 먼 거리를 이동할 경우 그만큼 반복 비교 연산이 많이 일어나는 단점이 있었다. 더 큰 거리를 이동함으로써 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
  • 최종 자리를 더 빨리 찾아감으로써 연산의 횟수를 줄이는데 기여할 수 있다.
  • 삽입 정렬은 어느 정도 정렬이 된 배열에서 더 빠르게 동작한다는 것을 앞의 포스팅에서 살펴봤다. 이 점을 토대로 한 번에 정렬을 끝내는 것이 아니라 부분 리스트를 구성해 조금씩 정렬된 상태를 만들어가는 것이므로 삽입 정렬에 비해 속도가 점점 더 빠르게 수행된다.

# 합병 정렬

  • 존 폰 노이만 선생님이 제안한 방법.
  • 일반적인 방법으로 구현했을 때 이 정렬은 안정 (stable) 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
  • 분할 정복(divide and conquer) 방법
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
  • 오름 차순을 기준으로 정렬한다.

기본 로직은 다음과 같다.

  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.(리스트의 길이가 1이 될때까지 반으로 잘게 나눈다.) 그렇지 않은 경우에는
  2. 정렬되지 않은 리스트를 절반으로 나눠 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

구체적으로 다시 설명해보면 다음과 같다.

  • 최종 목표는 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 것이다.
  • 합병 정렬은 다음의 단계들로 이루어진다.
    • 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
    • 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀 호출)을 이용하여 다시 분할 정복 방법을 적용한다.
    • 결합(Combine) : 정렬된 부분 배열을 하나의 배열에 합병한다.
  • 합병 정렬의 과정
    • 추가적인 리스트가 필요하다.
    • 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.(재귀 호출)
    • 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(Merge)하는 단계이다.

장점

  • 안정적인 정렬 방법이다. stable하다.
  • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. -> O(n logn)으로 동일.
  • 만약 레코드를 연결 리스트(LinkedList)로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 제자리 정렬(in-place sorting)을 구현할 수 있다.
  • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

단점

  • 만약 레코드를 배열로 구성하면, 임시 배열이 필요하다.
    • 메모리 낭비를 초래할 수 있다.
    • 제자리 정렬(in-place sorting)이 아니다.
  • 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

시간 복잡도
크기가 N인 배열을 반으로 쪼개면서 분할한다.
한 번 분할하면 N/2, N/2 -> 2개가 생기고,
그 다음 분할하면 N/4, N/4, N/4, N/4 ->4개

이처럼 분할 과정은 매번 반씩 감소하므로 밑이 2인 log N만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.

각 분할별로 합병을 진행하므로 합병 정렬의 시간 복잡도는 O(NlogN)이다.

  • 평균 : NlogN
  • 최악 : NlogN
  • 최상 : NlogN

다음의 글을 참고하자. -> 병합 정렬의 시간복잡도

# 퀵 정렬

  • 오름차순을 기준으로 정렬한다.
  • '찰스 앤터니 리처드 호어’가 개발한 정렬 알고리즘이다.
  • 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
  • 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 갖는다.
    • Merge Sort와 달리 퀵 정렬은 리스트를 비균등하게 나눈다.
  • 분할 정복 방법(Divide and Conquer)
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
    • 분할 정복 방법은 순환 호출(재귀 호출)을 이용하여 구현한다.

기본 로직은 다음과 같다.

  1. 리스트 안에서 하나의 원소를 선택한다. 이 원소를 피봇이라고 한다.
  2. 피봇을 기준으로 왼쪽에는 피봇보다 작은 원소들을 옮기고 오른쪽에는 피봇보다 큰 원소들을 옮긴다.
  3. 피봇을 제외한 왼쪽 부분 집합과 오른쪽 부분 집합을 다시 정렬한다.
    • 분할된 부분 집합에 대해 순환 호출을 이용하여 정렬을 반복한다.
    • 부분 집합에 대해서도 다시 피봇을 정하고 피봇 기준으로 2개의 부분 집합으로 나누는 과정을 반복한다.
  4. 부분 집합이 더 이상 분할이 불가능할 때까지 반복한다.
    • 리스트의 크기가 0이나 1이 될 때까지 반복한다.

퀵 정렬에서 알아야 할 개념

  • 분할(Divide) : 정렬할 자료들을 피봇을 중심으로 좌, 우 2개의 부분집합으로 나누는 것을 말한다.
  • 정복(Conquer) : 부분집합의 원소들 중에서 피봇보다 작은 원소들은 왼쪽, 큰 원소들을 오른쪽 부분집합으로 정렬하는 과정이다.
  • 부분 집합의 크기가 더 이상 나눌 수 없을 때까지(부분 집합의 원소가 1개 이하) 분할, 정복 과정이 반복된다.
  • 피봇 : 기준 값(일반적으로 전체 원소 중 가운데에 위치한 원소)
  • L : 왼쪽에서 오른쪽으로 움직이며 피봇보다 큰 원소를 찾아 L로 지정.
  • R : 오른쪽에서 왼쪽으로 움직이며 피봇보다 작은 원소를 찾아 R로 지정.

장점

  • 속도가 빠르다.
    • 시간 복잡도가 O(NlogN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
    • 퀵 정렬은 O(NlogN) 만큼의 메모리를 필요로 한다.

단점

  • 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
    • 퀵 정렬의 불균형 분할을 방지하기 위해 피봇을 선택할 때 리스트를 더욱 균등하게 분할할 수 있는 데이터를 선택한다.
    • Ex) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값을 피봇으로 선택한다.

시간 복잡도

  • 평균, 최선 : O(NlogN)
  • 최악 : O(N^2)

일반적으로는 O(NlogN)의 성능을 나타내지만,
피봇이 항상 최솟값이나 최댓값으로 잡힙다면 최악의 성능인 O(N^2) 나온다.
이미 정렬된 리스트에 대해서 첫 번째 원소 혹은 마지막 원소를 피봇으로 선택할 경우 최악의 성능을 맛 볼 수 있다.

그래서 중간 값을 피봇으로 선택하는 것이 시간 복잡도가 최악의 경우인 O(N^2)을 피할 수 있는 방법이기도 하다.

느낀 점

정렬 알고리즘은 크게 보면 두 가지 분류로 나눌 수 있을 것 같다.

  • 단순(구현이 간단)하지만 비효율적인 방법
    • 삽입 정렬, 선택 정렬, 버블 정렬
  • 복잡하지만 효율적인 방법
    • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

이 중에서 퀵 정렬이 가장 어려웠다. 개념을 이해하고 코드를 보는데 이해가 되지 않았다. 여러 사람들이 정리한 블로그를 참고해서 코드를 보니까 조금씩 구현이 달라서 방향을 잡지 못했다.

그래서 2개의 블로그를 참고해서 코드를 돌려보면서 실제로 디버깅을 해보니까 이해가 확실히 갔다. 생각보다 정렬 알고리즘이 재미있었다. 기억력이 오래 갔으면 좋겠지만 아닐 수도 있으니 빠른 시일 내에 복습을 해야겠다.

참고