요즘이라고 적었지만 내 기준으로 학교에서 배우지 못한 sorting 을 정리한다.
Bitonic sorter(https://en.wikipedia.org/wiki/Bitonic_sorter)
* 우선 이 sort 는 병렬 처리에 최적화된 sort 이다. 이 sort 에 대해 이해하려면 Sorting network(https://en.wikipedia.org/wiki/Sorting_network) 을 이해해야한다. Sorting Network 는 N개의 항목에 대해 비교연산을 최적화해서 sorting 하는 방법이다.
왼쪽은 input 된 인자의 array 이고 오른쪽은 output의 array 라고 생각하면된다. sorting network 에서 위에서 위, 아래를 잇는 수직선은 두 element 끼리 비교연산을 해서 위치를 유지하거나 swap 한다고 생각하면된다. 대충 함수로 나타나면 아래와 같다. (함수에 오류가 있을 수 있다. 대충 작성했다.)
def cmp_swap(arr, idx_0, idx_1):
if arr[idx_0] < arr[idx_1]:
temp = arr[idx_0]
arr[idx_1] = temp
return arr
return arr
def sortnetwork_desc(a): // 내림차순
a = cmp_swap(a, 0, 2)
a = cmp_swap(a, 1, 3)
a = cmp_swap(a, 0, 1)
a = cmp_swap(a, 1, 2)
return a증명은 [1,2,3,4], [1,3,2,4], .... [4, 3, 2, 1] ( 24개: 4*3*2*1 : 4! ) 같은 데이터 조합에 대해 모두 정렬이 된다면 잘 동작한다고 생각 할 수 있다. 좀 많이 무식하게 구현하면 프로스포츠 경기의 리그전 같이 하나의 element 가 모든 다른 element 와 비교하게 할 수도 있다. (아래에 position-counting-sort 이라고 정말 리그전 같은 알고리즘도 설명해 두었다.) 물론 sorting network 는 그 것보다는 좀 더 비교 연산이 적게 되어 있다.
이 sorting network 를 예쁘게 만들면 아래처럼 된다.
위 그림을 보면 4개의 비교 연산을 한 번에 하면 빠르게 동작 할 수 있겠다고 보여진다.
1회 (a0,a1), (a2,a3), (a4, a5), (a6, a7)
2회 (a0, a3), (a2, a3), (a4, a7), (a5, a6)
.....
6회 (a0,a1), (a2,a3), (a4, a5), (a6, a7)
로 계산할 수도 있다.
그래픽 카드를 이용해서 병렬계산하거나 Simd(https://ko.wikipedia.org/wiki/SIMD) 명령어를 이용하면 고정적인 횟수로 빠르게 정렬을 할 수 있다.
Timsort( https://en.wikipedia.org/wiki/Timsort )
* 기본 아이디어는 Insertion sort와 Merge sort를 결합한 알고리즘이다. https://d2.naver.com/helloworld/0315536 여기에 너무 설명이 잘 되어 있다. 추가 설명이 필요 없을 것 같다.
pdqsort(https://github.com/orlp/pdqsort)
* golang 에서 이 sort 을 기본으로 사용 하겠다고 한다. (https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257 )
딱히 이 sort 에 대해 쉽게 설명이 잘 되어있는 곳을 찾지 못했다. 의도는 quick sort 와 quick sort 의 worst case 에 heap sort 를 하겠다는 발상이다.
position-counting-sort(https://github.com/stgatilov/position-counting-sort)
* 딱히 유명한 sort 방법은 아닌데, 요즘 개인적으로 관심을 가지는 방법이다. 위에서 설명한 Bitonic sorter 보다 더 무식하게 비교 연산을 한다. a0, a1, a2, a3 이렇게 데이터가 있을 때, a0 정렬 순위(정렬을 했을 때의 순위)계산하기 위해 싹 다 비교 연산을 한다. (마치 스포츠경기의 리그전 같이 한 팀이 나머지 팀을 모두 경기를 갖는 것이다. 거기에 따라서 순서가 정해진다. )
def position_counting_sort(a): # 내림차순(높은 값에서 낮은 값으로)으로 정렬한다.
ranks = [0] * len(a)
for i in range(len(a)):
ranking = 0
for j in range(len(a)):
# 무식하게 a[i] 보다 작은 것들의 개수를 센다. (구현이 귀찮아 자신도 포함해서 계산했다.)
# 그 수 만큼 순위가 결정된다.
# a[i] 보다 큰 값이 하나도 없으면 ranking 은 0이다.
if a[i] < a[j]:
ranking +=1
# rank에 저장되는 값은 정렬된 순서가 아니라 각 위치별 순위이다.
ranks[i] = ranking
# rank 배열에 저장된 값에 따라 다시 한 번 여기서 순서대로 배열한다.
out = [0] * len(a)
for i in range(len(a)):
out[ranks[i]] = a[i]
return out각 원소 하나에 대해 다른 원소들을 모두 비교한다. 일반적인 경우라면 당연히 매우 느릴 것이다. 그런데 simd 같이 한 번에 여러 비교 연산을 할 수 있다면 정렬 속도가 고정적인 괜찮은 알고리즘이 될 수 있다. 실용적인 관점에서 본다면 simd 같은 병렬처리를 사용하고 작은 그룹을 지어서 position-counting-sort 한 다음에 이 그룹끼리 merge 연산을 사용하는 hybrid 방식을 추구 해 볼 수 있다.
물론 Bitonic sorter 보다 비교 연산이 많아서 불리 한 것 같지만 배열간의 이동이 거의 없다. 그리고 결과값으로 정렬된 데이터 뿐만 아니라 정렬순서표(위 소스에서 ranks 변수) 를 얻을 수 있다. 보통 key, value 가 하나의 set 로 정렬되는 경우도 많인데, 이 때 value 값에 정렬하면서 key 값을 얻을 수 있는 장점도 있다.