earticle

영어

Among comparison sorts, no algorithm excels a current set lower bound of O(n`log`n) in operation. Quicksort, the fastest of its kind, has a complexity of O(n`log`n) at its best and on average and O(n ^{2} ) at worst. This paper thus presents two methods: first is an O(n+k) simple counting sort which operates much more speedily than an O(n+k), (k=maximum`value)counting sort, and second is an O(l`n) radix counting sort which counts the frequency of numbers in the digit of a data and saves it in a corresponding virtual bucket in an array, only to virtually divide the array into radix digit numbers. For the 6 experimental data, the proposed algorithm makes O(n`log`n) or O(n ^{2} ) of Quicksort simple into O(n+k) or O(l`n). After all, the proposed sorting algorithm has proved to be much faster than the counting sort and Quicksort.

한국어

데이터를 비교 정렬하는 방법들 중 O(n`log`n)보다 빠른 방법은 알려져 있지 않고 있으며, 가장 빠른 퀵 정렬법은 최적과 평균의 경우 O(n`log`n), 최악의 경우 O(n ^{2} )수행 복잡도를 갖고 있다. 본 논문은 비교 정렬법이 아닌 O(n+k),`(k=최대치)의 계수 정렬법을 보다 빠르게 수행하는 O(n+k)의 단순 계수정렬법과 데이터의 자리 수 의 숫자별 빈도수를 계수하여 해당 가상 버킷에 저장하는 O(l`n)의 기수 계수 정렬법을 제안하였다. 6개의 실험 데이터에 제안된 알고리즘을 적용한 결과, 퀵 정렬의 O(n`log`n) 또는 O(n ^{2} )을 O(n+k) 또는 O(l`n)으로 단순화 시킬 수 있었다. 결론적으로 제안된 방법은 계수정렬법과 퀵 정렬법에 비해 보다 빠른 방법이다.