earticle

영어

Generally, there is no sorting algorithm much faster than . The quicksort has a best performance in best and average-case, and in worst-case. This paper suggests virtual radix counting bucket sort such that counting the frequency of numbers in each radix digit, and moves the arbitrary number to proper virtual bucket in the array, and divides the array into radix digit numbers virtually. Also, this algorithm moves the data to proper location within an array for using the minimum auxiliary memory. This algorithm performs -times such that the number of digits in given data and the time complexity is . Therefore, this algorithm has a time complexity.

한국어

데이터를 정렬하는 방법들 중 보다 빠른 방법은 알려져 있지 않고 있으며, 가장 빠른 방법으로 퀵정렬이 있으며, 이 정렬법은 개의 데이터에 대해 최적과 평균의 경우 , 최악의 경우 수행 복잡도를 갖고 있다. 본 논문에서는 리스트를 기수 숫자별로 빈도수를 계수하여 해당 가상 버킷에 저장하는 가상분할방법을 적용하였다. 또한 추가적인 메모리를 최소화시키기 위해 리스트 상에서 해당 버킷에 데이터들을 이동시키는 방법을 적용하였다. 제안된 알고리즘은 주어진 숫자의 자리수 만큼 분할되며, 각 자리수에 대해 수행복잡도가 으로 알고리즘이다.