알고리즘 이론 (퀵 정렬 ~ 기수정렬)

퀵 정렬

• 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘
• 기준값, 투 포인터 사용
• 시간 복잡도 O(nlogn)
• worst case = n^2

 

병합 정렬(merge sort)

• 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합함
• 시간 복잡도 O(nlogn)
• 한 섹션 안에서 n개의 수를 정렬하는 횟수 = n
• 섹션 수 = n/2/2/2… → logn

 

기수 정렬(radix sort)

• 데이터의 자릿수를 비교함
• 시간 복잡도 O(kn) → 여기서 k는 데이터의 자릿수
• 10개의 큐를 이용 (10진수인 데이터에 의해)
• 시간 복잡도가 가장 좋지만 구현하기가 비교적 복잡함