데이터를 정렬하는 방법들 중 O(n log n)보다 빠른 방법은 알려져 있지 않고 있으며, 가장 빠른 방법으로 퀵정렬이 있다. n개의 데이터에 대해 퀵정렬은 최적의 경우 O(n log n), 최악의 경우 $O(n^2)$ 수행 복잡도를 갖고 있다. 본 논문에서는 퀵정렬보다 빠르게 정렬하는 방법으로, 분할된 리스트의 첫 번째 L=a[s], 마지막 H=a[e]과 중간 $M=[{\lfloor}(s+e)/2{\rfloor}]$에 대해 P=(L+M+H)/3의 3-점 평균을 피벗값으로 결정하는 방법을 제안하였다. 실험 결과 제안된 3-점 평균 피벗 퀵정렬은 최적, 평균, 최악 모두 수행 복잡도가 O(n log n)으로 퀵정렬의 $O(n^2)$ 정렬 시간을 단축시킬 수 있었다.
데이터를 정렬하는 방법들 중 O(n log n)보다 빠른 방법은 알려져 있지 않고 있으며, 가장 빠른 방법으로 퀵정렬이 있다. n개의 데이터에 대해 퀵정렬은 최적의 경우 O(n log n), 최악의 경우 $O(n^2)$ 수행 복잡도를 갖고 있다. 본 논문에서는 퀵정렬보다 빠르게 정렬하는 방법으로, 분할된 리스트의 첫 번째 L=a[s], 마지막 H=a[e]과 중간 $M=[{\lfloor}(s+e)/2{\rfloor}]$에 대해 P=(L+M+H)/3의 3-점 평균을 피벗값으로 결정하는 방법을 제안하였다. 실험 결과 제안된 3-점 평균 피벗 퀵정렬은 최적, 평균, 최악 모두 수행 복잡도가 O(n log n)으로 퀵정렬의 $O(n^2)$ 정렬 시간을 단축시킬 수 있었다.
In the absence of a sorting algorithm faster than O(n log n), Quicksort remains the best and fastest of its kind in practice. For given n data, Quicksort records running in O(n log n) at best and $O(n^2)$ at its worst. In this paper, I propose an algorithm by which 3-points average P=(L+M...
In the absence of a sorting algorithm faster than O(n log n), Quicksort remains the best and fastest of its kind in practice. For given n data, Quicksort records running in O(n log n) at best and $O(n^2)$ at its worst. In this paper, I propose an algorithm by which 3-points average P=(L+M+H)/3 is set as a pivot for first array L=a[s], last array H=a[e], and middle array $M=a[{\lfloor}(s+e)/2{\rfloor}]$ in order to find the more fast than Quicksort. Test results prove that the proposed 3-points average pivot Quicksort has the time complexity of O(n log n) at its best, average, and worst cases. And the proposed algorithm can be reduce the $O(n^2)$ time of Quicksort to O(n log n).
In the absence of a sorting algorithm faster than O(n log n), Quicksort remains the best and fastest of its kind in practice. For given n data, Quicksort records running in O(n log n) at best and $O(n^2)$ at its worst. In this paper, I propose an algorithm by which 3-points average P=(L+M+H)/3 is set as a pivot for first array L=a[s], last array H=a[e], and middle array $M=a[{\lfloor}(s+e)/2{\rfloor}]$ in order to find the more fast than Quicksort. Test results prove that the proposed 3-points average pivot Quicksort has the time complexity of O(n log n) at its best, average, and worst cases. And the proposed algorithm can be reduce the $O(n^2)$ time of Quicksort to O(n log n).
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 퀵정렬을 보다 효율적으로 수행하는 3-점 평균 피벗 퀵정렬을 제안한다. 2장에서는 퀵정렬 방법을 고찰해 본다.
본 논문은 가장 빠른 방법으로 알려진 퀵정렬을 보다 효율적으로 수행하는 3점 평균 피벗 퀵정렬을 제안하였다. 기존의 퀵 정렬은 리스트가 비교적 균형되게 분할되는 최적 또는 평균의 경우 수행 복잡도가 O(nlogn)이다.
제안 방법
(e)는 기존에 오름차순으로 정렬된 데이터에 일부 데이터가 추가된 형태이다. 5가지 형태의 데이터에 대해 최우측 피벗 퀵정렬과 3-점 평균 피벗 퀵정렬을 수행하여 수행 복잡도를 비교하여 본다.
본 장에서는 사전에 정렬을 시키지 않고도 거의 균형된 분할 효과를 얻을 수 있도록 그림 3의 알고리즘을 제안한다.
제안된 방법은 분할된 리스트의 첫 번째 a[s], 마지막 a[e]와 중간 a[⌊(s+e)/2⌋의 3 지점의 평균값을 피벗값으로 결정하는 방법이다.
성능/효과
만약, 2 ≤ l ≤ 4에 대해서는 상호 비교를 통해 교환된다. 이 방법을 적용하면 리스트를 대부분 균형되게 분할할 수 있어 최적, 최악과 평균 모두 수행 복잡도가 O(nlogn)이다.
그러나 리스트가 불균형적으로 분할되는 최악의 경우 수행 복잡도가 O(n2 )인 단점이 있다. 이러한 단점을 보완하기 위해 제안된 3-점 평균 피벗 방법은 대부분의 리스트가 균형되게 분할되어 최적, 평균, 최악 모두 수행 복잡도가 O(nlogn)을 나타내었다.
질의응답
핵심어
질문
논문에서 추출한 답변
3점 평균 피벗 퀵정렬은 일반 퀵정렬보다 어떤 점이 좋게 나타났는가?
그러나 리스트가 불균형적으로 분할되는 최악의 경우 수행 복잡도가 O(n2 )인 단점이 있다. 이러한 단점을 보완하기 위해 제안된 3-점 평균 피벗 방법은 대부분의 리스트가 균형되게 분할되어 최적, 평균, 최악 모두 수행 복잡도가 O(nlogn)을 나타내었다.
퀵정렬은 무엇인가?
다양한 데이터 정렬 방법들 중에서 퀵정렬 (quicksort)이 가장 빠른 방법으로 알려져 있다. 퀵정렬은 하나의 리스트를 피벗 (pivot)값을 기준으로 계속적으로 양분하는 방법으로, 리스트가 균형된 분할 (balanced partition)이 수행되는 최적과 평균의 경우 O(nlogn)의 수행 복잡도를, 불균형적으로 분할 (unbalanced partition)되는 최악의 경우 O(n2 )의 수행 복잡도를 갖고 있다[1-3].
평균적인 시간 복잡도가 O(nlogn)인 정렬 알고리즘에는 무엇이 있는가?
데이터 정렬에 있어서 지금까지는 수행 복잡도 O(nlogn)보다 빠른 방법은 일반적으로 존재하지 않는 것으로 알려져 있다. 평균적인 시간 복잡도가 O(nlogn) 인 정렬 알고리즘으로는 Quicksort, Merge sort, Heap sort, Timsort, Binary tree sort와 Smoothsort가 있다[4].
참고문헌 (9)
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms, Chapter 7. Quicksort", 2nd Ed., pp. 145-164, MIT Press, 2005.
D. B. Ring, "A Comparison of Sorting Algorithms", http://www.devx.com/vb2themax/Article/19900, 2003.
S. Nilson, "The Fastest Sorting Algorithm?", http://drdobs.com/architecture-and-design/184404062, Dr. Dobb's Journal, Vol. 311, pp. 38-45, Apr. 2000.
R. Sedgewick, "Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching", 3rd Ed., Addison-Wesley, 1998.
H. W. Lang, "Sequential and Parallel Sorting Algorithms, Quicksort", FH Flensberg, http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm, 2011.
C. A. R. Hoare, "Quicksort", The Computer Journal, Vol. 5, No. 1, pp. 10-16, Mar. 1962.
J. W. J. Williams, "Algorithm 232-Heapsort", Communications of the ACM, Vol. 7, No. 6, pp: 347-348, Jun. 1964.
D. Carlson and I. Minerd, "Software Design Using C++: Heap and Heapsort", http://cis. stvincent.edu/html/tutorials/swd/heaps/heaps.html, Computing & Information Science Department, Saint Vincent College, 2011.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.