1. Divide & conquer sort

• 이 형태의 정렬 알고리즘들은 데이터의 모음을 더 작게 나누고 분리함을 통해, 데이터를 적게 참조할 수 있도록 하여 시간 복잡도를 개선한다.

2. Merge sort

• 주어진 array를 재귀를 이용해 최대한 분리했다가, 정렬한 array를 recursive stack으로 차곡차곡 반환하는 방법이다.

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하지 않고, 메모리도 더 많이 사용한다.

3. LSD-radix sort

• 지금까지의 정렬 알고리즘들은 데이터들을 서로 비교하여 순서를 맞추는 원리를 따랐다. 하지만 두 데이터간의 비교를 이용하는 알고리즘은 근본적으로 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)의 시간복잡도를 가져 시간 효율이 더 낫다.

4. 보론

• 정렬된 array는 binary search를 사용할 수 있다는 것을 금방 떠올릴 수 있다. 일반 탐색은 O(n)이지만, binary search는 O(log n)이기 떄문이다.

• 하지만, 기존에 존재하는 array에 일반 탐색을 사용하면 O(n)으로 끝난다. 그러나, 정렬 이후 binary search를 사용하면, 정렬에 필요한 O(?) * O(log n)이 필요하므로, 오히려 더 비효율적일 수 있다.

• 물론, 탐색이 한번으로 끝나는 것이 아니라, 이후에도 계속 수행해야한다면, 어떻게든 한번은 정렬을 수행하고, 이후에 계속 binary search를 사용하는 것이 나을 것이다.

• 즉, 상황에 따라 정렬을 사용할지, 그렇지 않을지 먼저 판단을 해주는 것이 필요하다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.