mergeSort(array)
array = merge(array)
merge(array)
if array.length < 2
return
length = array.length
midindex = length / 2
left = array[0~midindex-1]
right = array[midindex ~ length-1]
merge(left)
merge(right)
i = 0
j = 0
while i & j not at the left and right array
if left[i] <= right[j]
array[i+j] = left[i]
increment i
else
array[i+j] = right[j]
increment j
while i < left.length
array[i+j] = left[i]
increment i
while j < right.length
array[i+j] = right[j]
increment j
return array
Array를 1개의 데이터를 가진 subarray로 쪼개질 때까지 recursive stack을 쌓다가, 1개가 되면 반환을 시작함으로서 재귀함수의 아랫부분으로 넘어간다. 이때, left array와 right array의 값을 차례대로 비교하여, 작은 순서대로 둘을 합친 크기의 새 array에 넣어 반환한다. 최후에는, 기존 array의 반씩의 크기를 지닌 두 array의 데이터를 비교하며, 기존 array의 크기와 같은, 정렬된 array를 반환한다(실질적으로는, left측이 먼저 정렬된 후 right의 정렬을 시작한다).
가장 큰 특징으로는 stable하면서 O(n log n)의 시간복잡도를 가져, iterative보다 더 개선된 효율을 보인다. 하지만 adaptive하지 않고, 메모리도 더 많이 사용한다.
지금까지의 정렬 알고리즘들은 데이터들을 서로 비교하여 순서를 맞추는 원리를 따랐다. 하지만 두 데이터간의 비교를 이용하는 알고리즘은 근본적으로 O(n log n)의 시간복잡도 이상으로 효율적일 수 없다.
LSD-radix sort는 정수의 자리수를 기반으로 정렬하는 알고리즘으로, 오직 정수 형태의 데이터에만 적용할 수 있다는 단점은 있으나, 비교에 기반하지 않아 시간복잡도를 개선할 수 있다.
radix(array)
buckets = LinkedList[19] //최대 자리수에 따라 증감할 수 있음. 19는 -9~9자리까지.
for 0~k(longest number's digits)
for 0~array.length
calculate current digit of array[i]
add array[i] to bucket[digit+9]
idx = 0
for bucket in buckets
while bucket not empty
array[idx++] = value removed from bucket
첫번째로는, 데이터의 1의 자리 값에 따라 LinkedList에 위치시킨다. 그 이후, LinkedList에 존재하는 순서대로 값을 array에 넣는다. 다음에는 10의 자리 값에따라 LinkedList에 위치시킨 후, 또다시 순서대로 array에 넣는다. 최종적으로, 완전히 정렬이 된 array를 얻을 수 있다.
LSD-radix sort알고리즘은 adaptive하지는 않고 메모리도 더 소모하지만, stable하면서 무엇보다도 O(kn)의 시간복잡도를 가져 시간 효율이 더 낫다.
정렬된 array는 binary search를 사용할 수 있다는 것을 금방 떠올릴 수 있다. 일반 탐색은 O(n)이지만, binary search는 O(log n)이기 떄문이다.
하지만, 기존에 존재하는 array에 일반 탐색을 사용하면 O(n)으로 끝난다. 그러나, 정렬 이후 binary search를 사용하면, 정렬에 필요한 O(?) * O(log n)이 필요하므로, 오히려 더 비효율적일 수 있다.
물론, 탐색이 한번으로 끝나는 것이 아니라, 이후에도 계속 수행해야한다면, 어떻게든 한번은 정렬을 수행하고, 이후에 계속 binary search를 사용하는 것이 나을 것이다.
즉, 상황에 따라 정렬을 사용할지, 그렇지 않을지 먼저 판단을 해주는 것이 필요하다.
이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.