정렬 알고리즘

1. 버블정렬 (Bubble sort)

매번 연속된 두 개의 인덱스의 크기를 비교한 뒤, 교환하여 순서대로 정렬하는 방법이다. 가장 쉬운 정렬 알고리즘이지만 시간 복잡도가 좋지 않아 실제로 잘 사용되지 않는다.

시간 복잡도는 O(n²)이며 공간 복잡도는 하나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)이다.

2. 선택정렬 (Selection sort)

순회를 하면서 가장 작은 수를 선택하고 위치에 맞게 교환하여 반복해 정렬하는 방법이다. 선택정렬은 시간복잡도가 O(n²)으로 버블정렬과 유사하다.

3. 삽입정렬 (Insertion sort)

인덱스를 하나 선택해서 왼쪽 인덱스와 비교했을때 본인보다 작은 값을 만날때까지 왼쪽으로 이동하다가 만나면 삽입하는 정렬 방법이다.
삽입정렬은 이미 정렬이 되어있다면 한번 순회하며 체크만 하기 때문에 O(n)의 시간복잡도를 가지게되며 Big-O 시간복잡도는 O(n²)이다.

4. 병합정렬 (Merge sort)

병합정렬은 분할 정복(Devide and Conquer)의 방식으로 이뤄진다.

• 분할 정복 (Devide and Conquer) 이란?
  여러 알고리즘의 기본이 되는 해결 방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵정렬이나 병합정렬이 있다.
• 분할 정복의 적용 방식
  분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄여가는 방식이다.

//예시
function F(x):
  if F(x)가 간단 then:
    return F(x)를 계산한 값
  else:
    x 를 x1, x2로 분할
    F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값

• 분할 정복의 장점
  문제를 나눔으로써 어려운 문제를 해결할 수 있다.
• 분할 정복의 단점
  함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하는 단점이 있다. 가장 중요한 것은 이 알고리즘의 핵심인 "F(x)가 간단"이 어떤 것이냐에 따라 알고리즘의 퍼포먼스가 차이가 심하다는 것이다. 즉 이 "F(x)가 간단"이라는 것을 정의하는 것의 난해함 역시 단점 중에서 중요하게 다뤄지고 있다.
• 분할 정복 알고리즘을 설계하는 요령
  1) Divide (분할) : 문제 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
  2) Conquer (정복) : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
  3) Combine (결합) : Conquer 한 문제들을 통합하여 원래 문제의 답을 얻는다.
  • 문제를 제대로 나누면 Conquer 하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.
  • 분할 정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복 알고리즘의 효율성을 깎아내릴 수 있다.
• 분할 정복을 사용하는 알고리즘의 구성 요소
  • 문제를 더 작은 문제로 분할하는 과정 (divide)
  • 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge)
  • 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

//예시, 1부터 n까지의 합을 구하는 분할 정복 알고리즘
int fatsum(int n)
{
  if (n==1)
  	return 1;
  if (n % 2 == 1)
  	return fatSum(n-1) + n;
  return 2 * fatSum(n/2) + (n/2) * (n/2);
}

병합정렬은 주어진 배열을 가운데에서 쪼개어 비슷한 크기의 배열 두개로 만든 뒤, 이들을 재귀 호출을 이용해 각각 정렬한 후 정렬된 배열들을 하나로 합치는 정렬 방법이다.

이 정렬 알고리즘은 2가지의 큰 틀로 구성이 된다.

1) 분할
분할하는 함수를 재귀호출하여 배열을 2로 계속 나누다 보면 언젠가는 하나의 원소를 갖게 되니까 그때 멈추면 된다.

2) 병합
마지막으로 분할하기 위해 호출된 함수에서부터 병합하는 함수 merge()를 호출하기 때문에 분할의 역순으로 병합이 된다.

인자로 배열 arr와 left, right를 받는 이 함수는 나누어진 배열의 왼쪽은 l로, 오른쪽은 r로 인덱싱한다. 왼쪽 배열의 인덱스 l은 left부터, 오른쪽 배열의 인덱스 r은 mid + 1부터 시작한다. temp라는 임시 배열은 j를 인덱스로 한다.

while문은 왼쪽 부분 배열을 다 돌거나, 오른쪽 부분 배열을 다 돌 때까지 반복한다. 그러니 l은 mid 이하까지 r은 right 이하까지 반복하는데 왼쪽 배열, 오른쪽 배열 하나라도 전부 반복이 되었다면 탈출한다.

왼쪽 부분 배열과 오른쪽 부분의 배열의 원소를 비교해서 더 작은 값이 temp로 복사가 된다. 같을 때는 아무거나 넣어도 상관없다. 그림에서는 현재 1과 2 중에서 1이 더 작으므로 temp에 1이 저장된다. 그리고 l과 j를 하나씩 증가시킨다. j는 temp에 값이 들어가니까 계속 증가한다.

그 후 arr[l]과 arr[r] 중 값이 작은 것을 또 선택한다. 3과 2 중 에서 2가 더 작으니 2를 temp에 넣는다. 이후 r과 j는 증가한다.

마찬가지로 arr[l]과 arr[r] 중에서 가장 값이 작은 3을 넣는다. 그 후 j와 l의 값이 하나 증가한다.

4까지 넣고 나면 한쪽 부분 배열(왼쪽)이 전부 temp에 저장되어서 while루프는 종료된다.

남은 5가 있는데 만약 l이 mid보다 크다면 왼쪽 부분 배열이 temp에 전부 복사된 것이므로 오른쪽에 있는 부분 배열의 값을 모조리 temp에 집어넣는다.

반대의 경우에도 같다. 오른쪽 부분의 배열이 전부 temp에 복사되었다면 r은 right보다 크게 될테니까 왼쪽 부분 배열의 남은 값을 전부 temp에 집어넣으면 된다.

이제 원본 배열에 값을 다시 저장해야한다. temp는 잠시 저장하는 용도로 쓰기 때문이다.

• 병합정렬의 장점

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

• 병합정렬의 단점

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

• 병합정렬의 시간복잡도
  병합정렬은 계속 둘로 쪼갠 횟수만큼 n번의 루프를 돌기 때문에 nlogn만큼의 시간복잡도를 가지며, 버블정렬이나 선택정렬, 삽입정렬보다 훨씬 빠르다는 것을 알 수 있다.

5. 퀵 정렬 (Quick sort)

퀵 정렬도 분할 정복(Devide and Conquer)의 방식으로 이뤄진다.

퀵 정렬은 pivot이라는 기준점을 가지고 시작한다. pivot을 기준으로 pivot보다 작은 값은 왼쪽으로, pivot보다 큰 값은 오른쪽으로 재배치를 한다. 이 과정을 분할한 뒤 재귀적으로 처리하여 합치면 퀵 정렬은 끝나게 된다.

퀵 정렬이 이뤄지는 과정은 위와 같이 처음에 pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮겨진다.

왼쪽	기준	오른쪽
pivot보다 작은 요소	pivot	pivot보다 큰 요소

다음으로는 pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 위와 같은 과정을 순환 호출을 이용해서 정렬을 반복한다. 부분 리스트에서도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.

이 반복을 부분 리스트들이 더 이상 분할이 불가능할 때(리스트의 크기가 0이나 1이 될 때)까지 반복한다.

이 정렬 알고리즘 또한 2가지의 큰 틀로 구성이 된다. 위에서 병합 정렬과 같이 하나의 리스트를 분할한 후 병합하는 방식이다. 병합 정렬과 다른 점이 있다면 pivot을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이라는 것이다.

1) 분할
입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.

2) 병합
부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다. 이후 정렬된 부분 배열들을 하나의 배열에 합병한다.

순환 호출이 한번 진행될 때마다 최소한 하나의 원소(pivot)는 최종적으로 위치가 정해지므로 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

• 퀵 정렬의 장점

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

• 퀵 정렬의 단점

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

• 퀵 정렬의 시간복잡도
  퀵 정렬은 최선의 경우, 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 이것을 일반화하면 n=2^k의 경우, k(k=log₂n)임을 알 수 있다.
  각 순환 호출 단계의 비교 연산의 경우 각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
  따라서 순환 호출의 깊이 * 각 순환 호출 단계의 비교연산 = nlog₂n으로, 최선의 경우 시간 복잡도는 O(nlog₂n)이다.

  반면 최악의 경우가 있는데 예를 들면 리스트가 계속 불균형하게 나누어 지는 경우(특히, 이미 정렬된 리스트에 대하여 퀵 정렬을 실행하는 경우)에는 시간 복잡도가 좋지 않다.
  이러한 경우, 레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, 순환 호출의 깊이는 n임을 알 수 있다.
  각 순환 호출 단계의 비교 연산의 경우 각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
  따라서 순환 호출의 깊이 * 각 순환 호출 단계의 비교연산 = n²으로, 최악의 경우 시간 복잡도는 O(n²)이다.

  평균적인 경우에는 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에 시간 복잡도는 O(nlog₂n)이다.
  

• 퀵 정렬 알고리즘 예시