정렬 방법 중 가장 빠른 정렬 방법은 무엇일까요?

[Seobway23]

일반적으로 가장 빠른 정렬 방법은 퀵정렬입니다.

퀵 정렬

• 퀵 정렬은 분할 정복(divide and conquer) 전략을 사용하여 배열을 정렬
• 배열을 피봇(pivot)을 기준으로 두 부분으로 나눈 다음, 각 부분을 재귀적으로 정렬하는 방식

시간 복잡도

• 평균 O( nlogn)

• 최악의 경우 O(n^2)

  • 피봇이 항상 최솟값 or 최댓값으로 선택될 때

[kimmainsain]

답변

• 가장 빠른 정렬 방법은, 이름처럼 퀵 소트(quick sort)가 일반적으로 제일 빠른 방법인 것으로 알고 있습니다. O(nlogN)

• 피벗을 기준으로, 배열을 분할하며 정렬하는 방식입니다.

• 그러나 최악의 경우, O(n^2)일 수 있기 때문에 사용할 때 주의가 필요합니다.

• Arrays.sort : 듀얼피봇 퀵정렬(Dual-Pivot QuickSort), 피봇을 2개를 두어 더 나은 퀵소트 O(nlogN)

• Collections.sort : 팀 소트(Tim sort)를 사용한다. 머지소트 + 삽입소트 O(nlogN)

[freakFlow]

답변

가장 빠른 정렬 방법은 퀵정렬로 대부분의 경우 O(NlogN)의 시간 복잡도를 가지고 있습니다. 다만 불균형하게 분할되는 경우, O(N^2)의 시간 복잡도를 보일 수 있습니다.