[CS기초] 정렬(Sort)

정렬 알고리즘 개요

정렬 알고리즘은 데이터를 특정 기준에 따라 순서대로 정렬하는 방법을 의미합니다. 정렬 알고리즘에는 다양한 정렬 방식이 존재하는데요. 시간 복잡도와 공간 복잡도, 사용 목적에 따라 각각의 알고리즘을 적절히 선택해야 합니다.

 

기본 정렬 알고리즘

기본적인 정렬 알고리즘에는 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있는데요. 비교적 단순한 로직을 사용하며, 주로 작은 데이터 집합에서 사용됩니다. 세 방식 모두 시간 복잡도가 O(N²)인 정렬 방법입니다.

버블 정렬 (Bubble Sort)

• 인접한 두 요소를 비교해 더 큰 값을 오른쪽으로 이동시키며 정렬
• 데이터가 거의 정렬된 경우 비교적 빠르게 동작하지만, 최악의 경우 O(N²)의 시간 복잡도를 가짐

선택 정렬 (Selection Sort)

• 주어진 리스트에서 가장 작은 요소를 선택해 앞쪽으로 이동시키며 정렬
• 불필요한 비교 연산이 많아 비효율적이며, O(N²)의 시간 복잡도를 가짐

삽입 정렬 (Insertion Sort)

• 현재 요소를 정렬된 이미 부분(좌측)의 알맞은 위치에 삽입하며 정렬
• 대부분의 경우 O(N2)이지만, 데이터가 거의 정렬된 경우 O(N)에 가깝게 동작할 수 있음

 

효율적인 정렬 알고리즘

데이터의 크기가 커질수록 O(N²) 정렬 알고리즘은 비효율적으로 동작하게 되는데요. 이때에는 병합 정렬과 퀵 정렬 같은 보다 효율적인 정렬 알고리즘을 사용해야 합니다.

병합 정렬 (Merge Sort)

• 재귀적으로 리스트를 반으로 나누고, 각각을 정렬한 후 합쳐서 정렬하는 방식
• 나누는 과정에 O(N), 합치는 과정에 O(NlogN)이 소요되기 때문에 총 시간 복잡도가 O(NlogN)이 됨
• 같은 키 값을 가진 원소들의 원래 순서를 보장하는 안정적인 정렬 방식이지만, 추가적인 메모리 공간이 필요
  • 같은 5라는 데이터 두 개(5-1, 5-2)가 있을 경우, 정렬 이후 5-2, 5-1이 되지 않고 항상 원래 순서를 유지한다.

퀵 정렬 (Quick Sort)

• 특정 값을 피벗으로 선택하고, 피벗보다 작은 값과 큰 값으로 리스트를 나눈 후 정렬하는 방식
• 평균적으로 O(NlogN)에 동작하지만, 최악의 경우 O(N²)로 성능이 저하될 수 있음
• 데이터 분포에 따라 성능이 달라지기 때문에, 직접 구현 시 최악의 경우를 방지하는 전략이 필요
  • 정렬을 직접 구현해서 사용해야 할 경우 다른 정렬 알고리즘을 선택하는 것이 좋음

퀵 정렬이 최악의 경우 O(N^2)임에도 정렬 라이브러리 등에서 각광받는 이유

대부분의 정렬 라이브러리는 퀵 정렬을 기반으로 만들어져 있습니다. 여기에 다양한 최적화(하이브리드 알고리즘 등)를 추가해 여러 상황에서도 안정적으로 동작하도록 설계되었죠. 그런데 퀵 정렬은 최악의 경우 O(N²)의 시간 복잡도를 가지는데도 불구하고, 왜 이렇게 널리 쓰일까요?

 

무엇보다도 퀵 정렬은 평균적으로 매우 빠르게 동작합니다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)인데요. 비교 연산과 스왑 횟수가 적어 병합 정렬 등 다른 알고리즘보다 실제 실행 속도가 훨씬 빠릅니다. 게다가, 실제 데이터에서는 최악의 경우가 거의 발생하지 않기 때문에 퀵 정렬이 굉장히 합리적인 선택이라고 볼 수 있습니다.

 

그래도 '최악의 경우는 어떻게 하나요?'라는 의문이 들 수 있습니다. 이 또한 피벗을 랜덤하게 선택하거나 Median-of-Three 기법 등을 사용하는 등 빠른 정렬 방식을 선택함으로써 최악의 경우를 피할 수 있습니다. 우리가 흔히 구현하는 기본적인 퀵 정렬 코드에는 이러한 최적화가 없지만, 라이브러리에서는 정교한 방식으로 이를 처리하는 것이죠.

 

또한 퀵 정렬은 뛰어난 캐시 효율성을 가지고 있습니다. 동작 과정에서 메모리에 연속적으로 접근하기 때문에 CPU 캐시 히트율이 높아지는데요. 이는 곧 더 빠른 처리를 가능하게 합니다.

 

그리고 추가적인 메모리 공간을 사용하지 않고 입력된 데이터 구조에서 직접 정렬하는 인플레이스 정렬 방식이기 때문에 공간 복잡도 면에서도 훨씬 우수합니다.

 

결론적으로 빠른 성능과 뛰어난 캐시 효율성, 그리고 적은 메모리 사용 덕분에 퀵 정렬은 정렬 라이브러리의 핵심 알고리즘으로 자리잡게 되었습니다.