퀵정렬은 피벗값을 최좌측, 최우측, 중간 값 또는 랜덤하게 결정하는 방법을 적용하고 있다. 본 논문은 범위 중간값을 $P_0$피벗값으로 결정하고 계속적으로 양분하는 퀵정렬 방법을 제안하였다. 제안된 방법은 길이가 $n$인 리스트 $A$의 $i$=1, $j$=$n$에서 최소값 $L$과 최대값 $H$를 탐색하여 초기 피벗 키 값으로 $P_0=(H+L)/2$로 설정하고 $i$=$j$ 또는 $i$>$j$가 될 때까지 $a[i]{\geq}P_0$, $a[j]<P_0$를 교환하는 방식을 적용하였다. 피벗값에 따라 값의 교환이 완료되면 리스트 $A_0$는2개의 부분리스트 $a[1]{\leq}A_1{\leq}a[j]$과 $a[i]{\leq}A_2{\leq}a[n]$으로 분할되며 이 경우 피벗 키는 $P_1=P_0/2$, $P_2=P_0+P_1$으로 설정된다. 이러한 과정을 분할된 리스트의 길이가2일 때까지 수행되며, 리스트 길이가 2이고, $a$[1]>$a$[2]이면 $a[1]{\leftrightarrow}a[2]$로 교환한다. 제안된 방법은 퀵정렬에 비해 빠르며, 최악의 경우 수행 복잡도 $O(n^2)$을 $O(n{\log}n)$으로 향상시켰다.
퀵정렬은 피벗값을 최좌측, 최우측, 중간 값 또는 랜덤하게 결정하는 방법을 적용하고 있다. 본 논문은 범위 중간값을 $P_0$피벗값으로 결정하고 계속적으로 양분하는 퀵정렬 방법을 제안하였다. 제안된 방법은 길이가 $n$인 리스트 $A$의 $i$=1, $j$=$n$에서 최소값 $L$과 최대값 $H$를 탐색하여 초기 피벗 키 값으로 $P_0=(H+L)/2$로 설정하고 $i$=$j$ 또는 $i$>$j$가 될 때까지 $a[i]{\geq}P_0$, $a[j]<P_0$를 교환하는 방식을 적용하였다. 피벗값에 따라 값의 교환이 완료되면 리스트 $A_0$는2개의 부분리스트 $a[1]{\leq}A_1{\leq}a[j]$과 $a[i]{\leq}A_2{\leq}a[n]$으로 분할되며 이 경우 피벗 키는 $P_1=P_0/2$, $P_2=P_0+P_1$으로 설정된다. 이러한 과정을 분할된 리스트의 길이가2일 때까지 수행되며, 리스트 길이가 2이고, $a$[1]>$a$[2]이면 $a[1]{\leftrightarrow}a[2]$로 교환한다. 제안된 방법은 퀵정렬에 비해 빠르며, 최악의 경우 수행 복잡도 $O(n^2)$을 $O(n{\log}n)$으로 향상시켰다.
Generally, Quicksort selects the pivot from leftmost, rightmost, middle, or random location in the array. This paper suggests Quicksort using middle range pivot $P_0$ and continually divides into 2. This method searches the minimum value $L$ and maximum value $H$ in ...
Generally, Quicksort selects the pivot from leftmost, rightmost, middle, or random location in the array. This paper suggests Quicksort using middle range pivot $P_0$ and continually divides into 2. This method searches the minimum value $L$ and maximum value $H$ in the length n of list $A$. Then compute the initial pivot key $P_0=(H+L)/2$ and swaps $a[i]{\geq}P_0$,$a[j]<P_0$ until $i$=$j$ or $i$>$j$. After the swap, the length of list $A_0$ separates in two lists $a[1]{\leq}A_1{\leq}a[j]$ and $a[i]{\leq}A_2{\leq}a[n]$ and the pivot values are selected by $P_1=P_0/2$, $P_2=P_0+P_1$. This process repeated until the length of partial list is two. At the length of list is two and $a$[1]>$a$[2], swaps as $a[1]{\leftrightarrow}a[2]$. This method is simpler pivot key process than Quicksort and improved the worst-case computational complexity $O(n^2)$ to $O(n{\log}n)$.
Generally, Quicksort selects the pivot from leftmost, rightmost, middle, or random location in the array. This paper suggests Quicksort using middle range pivot $P_0$ and continually divides into 2. This method searches the minimum value $L$ and maximum value $H$ in the length n of list $A$. Then compute the initial pivot key $P_0=(H+L)/2$ and swaps $a[i]{\geq}P_0$,$a[j]<P_0$ until $i$=$j$ or $i$>$j$. After the swap, the length of list $A_0$ separates in two lists $a[1]{\leq}A_1{\leq}a[j]$ and $a[i]{\leq}A_2{\leq}a[n]$ and the pivot values are selected by $P_1=P_0/2$, $P_2=P_0+P_1$. This process repeated until the length of partial list is two. At the length of list is two and $a$[1]>$a$[2], swaps as $a[1]{\leftrightarrow}a[2]$. This method is simpler pivot key process than Quicksort and improved the worst-case computational complexity $O(n^2)$ to $O(n{\log}n)$.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
퀵정렬은 피벗값을 최좌측, 최우측, 중앙값 또는 랜덤하게 선택한다[4]. 본 논문에서는 주어진 데이터 범위 (최대값-최소값)의 중간값을 피벗으로 활용하는 방법을 제안한다.
본 논문은 컴퓨터과학 분야에서 가장 오래 전부터, 가장 많은 관심을 가진 연구분야인 정렬방법에 대해 퀵정렬보다 간단하면서도 빠른 방법을 제안하였다.
가설 설정
만약, 주어진 데이터가 오름차순이나 내림차순 데이터가 존재하지 않고, 대부분 랜덤하게 저장된 데이터라 가정할 경우, Verify sorting()을 적용하지 않고 Range Pivot Quicksort()만을 적용한다고 가정하여 보자. 모든 값의 빈도수 (frequency)가 유사하다면 제안된 알고리즘은 균형있는 분할이 수행되어 최적의 경우와 최악의 경우 모두 수행복잡도가 O(nlogn)임을 알 수 있다.
본 실험에는 최좌측 피벗을 선택한다고 가정하였다. 퀵정렬은 주어진 데이터가 오름차순 또는 내림차순으로 정렬되어 있는지 사전에 검증하지 않고 알고리즘을 적용한다.
제안 방법
랜덤하게 저장된 리스트의 경우 피벗값 P1→P2→P3→P4→P5→P6→P7의 7개 순서로 O(n)을 수행하였다.
Step 1. 리스트에서 최좌측 (leftmost), 최우측 (rightmost), 중앙(middle), 중위 (median), 랜덤 등 다양한 방법을 적용하여 하나의 원소를 피벗 (pivot, P)으로 선택한다.
제안된 알고리즘은 초기 피벗 값 P0을 L+(H-L)/2 = (L+H)/2로 단 1회만 계산한다. 이후부터의 피벗값은 다음과 같이 계산된다.
성능/효과
(3) 기존의 킉정렬은 분할 리스트 길이가 1 또는 0인 경우 알고리즘이 종료되나 범위피벗 킉정렬은 2 이상의 길이에서도 오름차순으로 정렬되어 있으면 알고리즘이 종료되며, 최소 길이는 2이다. 따라서 이진트리의 레벨 수를 줄일 수 있다.
(4) 기존의 퀵정렬은 최악의 경우인 불균형 분할이 수행되는 경우 수행복잡도는 O(n2)이다. 반면에, 이러한 오름차순이나 내림차순 데이터의 경우 O(n)으로 알고리즘이 종료되며, 랜덤한 데이터에 대해서는 O(nlogn)의 복잡도를 갖고 있다.
결론적으로, 오름차순과 내림차순 데이터의 경우 최좌측 피벗 킉 정렬의 수행복잡도는 O(n2)인데 반해 범위피벗 퀵 정렬은 O(n)으로 향상시켰다. 랜덤하게 저장된 데이터에 대해서는 최좌측 피벗 퀵정렬과 수행복잡도가 O(nlogn)이나 피벗값 선택 횟수를 감소시켰다.
최좌측 또는 중간 값을 피벗값으로 적용하는 퀵정렬에서는 피벗값을 리스트의 끝부분으로 옮기는 과정이 필요하지만 제안된 방법은 이 과정이 불필요하며, 피벗값이 주어진 리스트에 없는 경우에도 전혀 상관없는 장점이 있다. 또한, 제안된 방법은 피벗 기준값 P0가 일단 결정되면 나머지 피벗값들은 계속적으로 양분하면서 계산되어 피벗값을 결정하는 방법이 간단하다.
)인데 반해 범위피벗 퀵 정렬은 O(n)으로 향상시켰다. 랜덤하게 저장된 데이터에 대해서는 최좌측 피벗 퀵정렬과 수행복잡도가 O(nlogn)이나 피벗값 선택 횟수를 감소시켰다.
만약, 주어진 데이터가 오름차순이나 내림차순 데이터가 존재하지 않고, 대부분 랜덤하게 저장된 데이터라 가정할 경우, Verify sorting()을 적용하지 않고 Range Pivot Quicksort()만을 적용한다고 가정하여 보자. 모든 값의 빈도수 (frequency)가 유사하다면 제안된 알고리즘은 균형있는 분할이 수행되어 최적의 경우와 최악의 경우 모두 수행복잡도가 O(nlogn)임을 알 수 있다. 이는 퀵정렬의 최악의 경우 수행 복잡도 O(n2)을 개선한 결과로 퀵정렬의 수행복잡도롤 항상 O(nlogn)로 할 수 있는 획기적인 방법이다.
제안된 방법은 퀵정렬 방법에 비해 피벗값 결정이 보다 간단하면서도 최악의 경우 수행복잡도 O(n2)을 O(nlogn)으로 향상시켰으며, 최적, 최악과 평균 수행복잡도는 모두 동일하게 O(nlogn)인 장점을 갖고 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
이진 탐색법의 장점은 무엇인가?
데이터베이스나 인터넷에서 원하는 데이터를 빠른 속도로 탐색 (search)하기 위해서는 저장된 데이터가 정렬 (sort)되어 있어야만 한다. 길이가 n인 리스트 (list)에서 임의의 값을 탐색하는 가장 빠른 방법은 이진 탐색법 (binary search)으로 O(logn)의 수행 복잡도를 갖고 있으나 이 방법을 적용하기 위해서는 반드시 데이터가 정렬되어 있어야만 한다. 정렬 방법에는 다양한 방법들이 존재하지만 퀵정렬 (Quicksort)이 최악의 경우 O(n2), 최적의 경우 O(nlogn)의 수행 복잡도로 가장 빠른 방법으로 알려져 있다[1-3].
평균적인 시간 복잡도가 O(nlogn)인 정렬 알고리즘에는 무엇이 있는가?
데이터 정렬에 있어서 수행 복잡도 O(nlogn)보다 빠른 방법은 일반적으로 존재하지 않는 것으로 알려져 있다. 평균적인 시간 복잡도가 O(nlogn)인 정렬 알고리즘으로는 퀵정렬 이외에 병합정렬 (Merge sort), 힙정렬 (Heap sort), 팀정렬 (Timsort), 이진트리정렬 (Binary tree sort)과 평활정렬(Smoothsort)도 있다.
퀵정렬을 굳이 수행하지 않아도 되는 경우는 무엇인가?
정렬하고자 하는 데이터는 랜덤하게 저장된 데이터가 대부분이며, 이미 오름차순 또는 내림차순으로 정렬된 데이터는 거의 존재하지 않는다고 할 수 있다. 그러나 이러한 희박한 존재 가능성에 대해서는 굳이 퀵정렬을 수행하지 않아도 되며, 일반적인 랜덤하게 배열된 데이터에 대해서만 퀵정렬을 수행하면 수행시간이 보다 빠를 수 있다.
참고문헌 (5)
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, 2000.
R. Sedgewick, "Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching", 3rd Ed., Addison-Wesley, 1998.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.