[정렬 알고리즘] 퀵 정렬(Quick sort), 기수 정렬(Radix sort) 알고리즘

퀵 정렬 알고리즘

퀵 정렬 알고리즘은 피봇이라는 기준 데이터를 다른 데이터와 비교하는 과정을 재귀적으로 반복하여 정렬한다. (분할 정복 알고리즘 중 하나)

 

퀵 정렬 알고리즘은 반복문 하나만 사용하는 대신 재귀 호출을 사용해 데이터를 두 그룹으로 분할해서 정렬한다.(피봇의 왼쪽그룹, 피봇의 오른쪽그룹)

quicksort.c

0.00MB

 

radixsort.c

0.00MB

 

퀵 정렬 알고리즘의 핵심이 되는 코드는 아래와 같다.

 

여기서 left는 정렬할 데이터의 가장 왼쪽 인덱스를, right는 가장 오른쪽 인덱스를 가리킨다. left가 right보다 클 때에만 QuickSort가 실행된다. 즉 left<=right인 경우에는 이미 정렬된 상황이기 때문에 더 이상 정렬할 필요가 없고 재귀호출이 종료된다.

재귀호출은 QuickSort(int data[], int left, int right)을 실행하면 pivot인 i를 기준으로 왼쪽 그룹인 QuickSort(data, left, i-1)과 오른쪽 그룹인 QuickSort(data, i+1, right) 로 분할된다.

 

퀵 정렬 알고리즘의 특징은 데이터가 적은 경우보다 많은 경우에 알고리즘의 성능이 급격히 좋아진다는 것이다. 이는 일반적인 데이터의 집합이라면 전체 데이터의 절반을 기준으로 나눈다는 것을 의미한다. 단, 이미 데이터가 정렬되어 있는 최선의 경우나 데이터가 역으로 정렬되어 있는 최악의 경우는 오히려 성능이 많이 나빠지기도 한다. 

퀵 정렬 알고리즘의 성능은 일반적인 경우 O(NlogN)이고, 최악의 경우에는 O(N^2)이다. (N=데이터의 개수)

 

 

기수 정렬 알고리즘

기수 정렬 알고리즘은 정렬할 데이터의 자릿수를 이용해 데이터를 정렬한다. 

자릿수를 기반으로 데이터들을 정렬하므로 데이터들을 비교하거나 이동하는 횟수가 거의 없다. 

1의 자릿수 데이터를 정렬하려면 MAX(10)로 나눈 나머지를 이용해 저장하고, 10의 자릿수 데이터를 정렬하려면 MAX(10)로 나눈 몫을 이용해 저장한다.

 

기수 정렬 알고리즘의 성능은 정렬할 데이터의 자릿수 그리고 각 자릿수에 따른 큐의 수에 따라 결정된다.

따라서 기수 정렬의 빅오 표기법은 데이터의 자릿수 D와 정렬할 데이터 수 N 그리고 그에 해당하는 큐의 수 Q가 있다고 가정할 때, 아래와 같이 나타낼 수 있다.

O(RadioSort) = O(D(N+Q))

즉 비교횟수, 이동횟수, 데이터 정렬 상태와 상관 없이 D,N,Q에만 영향을 받는다.

 

 

-- 모르겠는거

기수 정렬 알고리즘에서 데이터가 이진수라면 실제 다루는 자릿수가 급격히 증가한다. 이때는 알고리즘의 전체 성능이 급격히 나빠지기도 한다.

프로그래밍에서 이진수를 사용하는 것이 비효율적? 그렇지않다. 왜냐하면 이진수가 데이터처리를 원활하게 해주기 때문에 더 낫다.

이해가 안가는게 어차피 10진수를 써도 컴파일할때 2진수로 바뀌지않나?