서론

  • 자바의 정렬 함수를 자주 사용하는데, 내부적으로 어떤 알고리즘이 사용되는지 궁금해서 작성하게 되었다.
  • 참고로 이번 글은 정렬 알고리즘을 설명하는 게 아닌 어떤 알고리즘이 쓰이는지를 정리하는 글이다.

본론

  • Java나 Android에서 Arrays.sort()는 Primitive Type이나 Object Type의 Array를 정렬할 때 사용한다.
  • Collections.sort()는 Collection의 List를 정렬할 때 사용한다.
  • 기본적으로 둘 다 오름차순 정렬이고, 인자로서 Array 또는 List를 넣어주면 인자로 넘겨진 객체의 내용 자체가 바뀐다. 또한, 둘 다 static method이므로 객체를 생성하지 않고 호출이 가능하다.

핵심

  • Arrays는 하나의 알고리즘만을 쓰는 것이 아니다.
  • 기본적으로 Insertion Sort, Merge Sort, Quick Sort 3가지를 사용한다.
  • 예전에는 3가지 Sorting이 구분되어 사용되었다.
  • 하지만, 현재는 이를 변형한 Tim Sort, Dual-Pivot Quick Sort를 쓴다고 한다.

<예전 기준>
1. 배열의 크기가 아주 작을 때(7개 미만) -> Insertion Sort

  • 왜 7개 미만일 때, Insertion Sort를 사용하는지는 수학적으로, 빅오 표기법의 맹점에 대해 접근할 수 있다.
  • Insertion Sort는 대상의 갯수에 따라 비교 횟수가 다르다.
    • 2개의 대상일 때는 1번 비교
    • 3개의 대상일 때는 2번 비교
    • 4개의 대상일 때는 3번 비교
  • 즉, n개일 때 (n-1)번 비교한다. 이는 1+2+…+n-1+n이고 n(n-1)/2라는 공식이 도출된다. n^2이 영향이 가장 크므로 빅오 표기법으로는 O(N^2)이 되지만 정확히는 n(n-1)
    /2이다.
  • n=6일 때, 6x5 / 2 = 15가 나오며, n=7일 때, 7x6 / 2 = 21이 나온다.
  • [Merge Sort]
    • Merge Sort의 시간 복잡도는 O(N logN)이다.
    • n=6일 때, 대략 15.509가 나오며, n=7일 때, 19.651이 나온다.
  • 따라서 n=6일 때는 일반적으로 Insertion Sort가 유리하며, n=7일 때는 Merge Sort가 유리하다.
  • n=6 이하일 때는 Insertion Sort를 사용하고, n=7 이상일 때는 Merge Sort를 사용하는 것이 빠른 경우이다.
  • Insertion Sort의 최악의 경우는 정렬할 데이터가 완전히 역순일 때이다. 하지만, 이러한 경우는 특별한 케이스이기 때문에 무시하고 평균적으로 n=6일 때, Insertion Sort가 더 빠르므로 사용하는 것이다.

2. Merge Sort와 Quick Sort를 사용하는 여부는 Sorting 알고리즘의 Stable과 관계가 있다.

  • Stable : 안전성을 의미하며, 정렬에서의 Stable은 같은 값을 비교했을 때 기존의 순서가 바뀌는지, 안바뀌는지를 의미한다.
  • Primitive Type의 Array를 정렬하는 것은 값의 대소를 비교하며, 같은 값을 가지는 2개의 숫자를 구분할 방법은 없다.
  • ex) [2 1 2 3] 배열을 오름차순 정렬하면 [1 2 2 3]이 된다. 이때 2와 2는 서로 같은 값을 가지지만, 정렬 과정에서 상대적인 위치가 바뀔 수 있다. 하지만, Primitive Type끼리는 이를 구분할 수 없고 별다른 영향도 없기에 구분할 필요도 없다.
  • 위와 같은 것을 Not Stable하다고 한다. Merge Sort를 써도 상관 없으나 일반적으로 Quick Sort가 더 빠르므로 Primitive Type은 Quick Sort를 사용하여 정렬한다.
  • Quick Sort가 Merge Sort보다 값에 대한 비교를 더 많이한다고 할지라도 Array에 대한 Access 횟수가 적기 때문에 크게 봤을 때, 더 빠르다.
  • Quick, Merge Sort 모두 분할 정복 방법에 기반하여 서브 리스트를 나누어 작은 배열을 정렬하는 방식을 사용한다.
  • 일반적으로 Quick Sort가 더 빠른 이유는 어느 정도 정렬을 하면서 서브 리스트로 분할하고 마지막에도 정렬을 한다. 하지만, Merge Sort는 쪼개질 수 없을 때까지 나눈 후 이를 합칠 때 부터서야 조금씩 정렬하기 때문에 Quick Sort보다 느리다.
  • [Object Array]
    • 이 경우에는 조금 달라진다. 객체는 주소를 가지고 있고 엄연히 구분될 수 있기 때문에 구분할 필요가 있다.
    • 따라서 이러한 Object Sorting은 Stable한 정렬 방법을 사용해야 한다. 특정 애플리케이션에서 값은 같은데 객체 자체가 다른 경우, 개발자가 생각한 것과 다른 결과물을 낼 수 있기 때문이다.
    • Stable한 정렬 방법 중 빠른 편에 속하는 것이 Merge Sort이다.

결론

  • Primitive Type Array -> Quick Sort
  • Object Type Array -> Merge Sort
  • Quick Sort : Not Stable
  • Merge Sort : Stable

<현재 기준>

  • 예전에는 3개의 알고리즘인 완전히 나뉘었지만, 지금은 Insertion Sort와 Merge Sort를 합친 Tim Sort라는 것을 사용하고 Quick Sort 역시 그냥 쓰는게 아니라 Dual-Pivot Quick Sort라는 것을 사용한다.
  • Tim Sort는 Stable하므로 Object에 사용한다.
  • Dual-Pivot Quick Sort는 Not Stable하므로 Primitive Type에 사용한다.
  • 마지막으로 Quickt Sort는 최악의 경우 O(N^2)으로 O(N logN)을 보장하지 않지만, Merge Sort는 최악의 경우일지라도 O(N log N)을 보장한다.

Reference