주제분류
자료유형
등재정보
전체 선택해제
총 3건 검색
본문검색 결과만 보기
-
3-점 평균 피벗 퀵정렬
이상운, Lee. Sang-Un 한국인터넷방송통신학회 The journal of the institute of internet, broadcasting and communication 7 Pages
한국인터넷방송통신학회 The journal of the institute of internet, broadcasting and communication 2014, Vol.14 No.6 295-301 (7 pages)
데이터를 정렬하는 방법들 중 O(n log n)보다 빠른 방법은 알려져 있지 않고 있으며, 가장 빠른 방법으로 퀵정렬이 있다. n개의 데이터에 대해 퀵정렬은 최적의 경우 O(n log n), 최악의 경우 $O(n^2)$ 수행 복잡도를 갖고 있다. 본 논문에서는 퀵정렬보다 빠르게 정렬하는 방법으로, 분할된 리스트의 첫 번째 L=a[s], 마지막 H=a[e]과 중간 $M=[{lfloor}(s+e)/2{ floor}]$에 대해 P=(L+M+H)/3의 3-점 평균을 피벗값으로 결정하는 방법을 제안하였다. 실험 결과 제안된 3-점 평균 피벗 퀵정렬은 최적, 평균, 최악 모두 수행 복잡도가 O(n... -
Parallel Sorting Algorithm by Median-Median
민용식, Min. Yong-Sik 한국음향학회 The journal of the Acoustical Society of Korea 8 Pages
한국음향학회 The journal of the Acoustical Society of Korea 1995, Vol.14 14-21 (8 pages)
수행이 된다. 첫째, 비순서화된 데이타 집합을 p개의 프로세서로 할당시킨후에 순차적 quicksort로 분류한다. 그 다음으로, 분류된 각 프로세서의 중위수값을 구한다음 이 값에 위해서 각 프로세서에 데이타 값을 할당시킨다. 각 프로세서에 할당된 데이타가 정확하게 분배가 되도록 중위수와 중위수 값을 구해서 각 프로세서에 적합한 데이타를 다시 할당 시키게 된다. 이때 각 프로세서가 지닌 데이타의 수는 확률이론을 이 용하였다. 마지막으로, 각 프로세서에 할당된 데이타를 순차적 quicksort로 분류하면 된다. 여기서 분류될 데이... -
범위 피벗 퀵정렬
이상운, Lee. Sang-Un 한국컴퓨터정보학회 韓國컴퓨터情報學會論文誌 7 Pages
한국컴퓨터정보학회 韓國컴퓨터情報學會論文誌 2012, Vol.17 No.4 139-145 (7 pages)
퀵정렬은 피벗값을 최좌측, 최우측, 중간 값 또는 랜덤하게 결정하는 방법을 적용하고 있다. 본 논문은 범위 중간값을 $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]