3 방향 파티션이있는 Quicksort

Question

3 방향 파티션이있는 QuickSort 란 무엇입니까?

Answer 1

사진 배열 ... are there four partition versions of quicksort, 요청 다른쪽에는 4보다 적은 모든 요소가 있습니다. 그래서 같이 :

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5 

세 파티션은 빠른 정렬는에 분할 두 개의 값을 선택하고 그 길 배열을 분할한다. 4 및 7을 선택할 수 있습니다.

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9 

일반 퀵 정렬에는 약간의 변형이 있습니다.

배열을 정렬 할 때까지 각 분할 영역을 계속 분할합니다. 런타임은 기술적으로 nlog (n)이며 일반 quicksort의 nlog (n)과 약간 다릅니다.

Answer 2

http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

은 참조 :

http://www.sorting-algorithms.com/quick-sort-3-way

나는 면접 질문 버전은 흥미로운 생각했다.

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0 

두 개의 파티션이 빠른 정렬 4 말, 값을 선택하고 배열의 한면에 4보다 큰 모든 요소를 ​​넣어 것입니다 : 그것은

Answer 3

Akra-Bazzi formula을 사용하여 파티션 수를 매개 변수로두고 그 매개 변수를 최적화하면 e (= 2.718 ...) 파티션이 가장 빠른 성능을 제공합니다. 실제로, 우리의 언어 구조, CPU 등은 모두 바이너리 연산에 최적화되어 있으므로 표준 파티션을 두 세트로 분할하는 것이 가장 빠릅니다.

Answer 4

3 방향 파티션은 Djstrka가 사용합니다.

같음,

기본적으로는 이하 3 개 분할을 설정 {17, 3, 9, 4, 1, 2, 3, 15, 17, 25}을 요소로하는 배열 생각해 더 큰 보다. 파티션 피벗, 피벗보다 작은 모든 요소 및 피벗보다 큰 모든 요소. 피벗과 동일한 모든 요소를 ​​제자리에서 이동합니다.

Answer 5

//code to implement Dijkstra 3-way partitioning 

    package Sorting; 

    public class QuickSortUsing3WayPartitioning { 

private int[]original; 
private int length; 
private int lt; 
private int gt; 

public QuickSortUsing3WayPartitioning(int len){ 
    length = len; 
    //original = new int[length]; 

    original = {0,7,8,1,8,9,3,8,8,8,0,7,8,1,8,9,3,8,8,8}; 

} 

public void swap(int a, int b){ //here indexes are passed 
    int temp = original[a]; 
    original[a] = original[b]; 
    original[b] = temp; 
} 

public int random(int start,int end){ 
    return (start + (int)(Math.random()*(end-start+1))); 
} 

public void partition(int pivot, int start, int end){ 
    swap(pivot,start); // swapping pivot and starting element in that subarray 

    int pivot_value = original[start]; 
    lt = start; 
    gt = end; 

    int i = start; 
    while(i <= gt) { 

     if(original[i] < pivot_value) { 
      swap(lt, i); 
      lt++; 
      i++; 
     } 

     if(original[i] > pivot_value) { 
      swap(gt, i); 
      gt--; 
     } 
     if(original[i] == pivot_value) 
      i++; 
    } 
} 

public void Sort(int start, int end){ 
    if(start < end) { 

     int pivot = random(start,end); // choose the index for pivot randomly 
     partition(pivot, start, end); // about index the array is partitioned 

     Sort(start, lt-1); 
     Sort(gt+1, end); 

    } 
} 

public void Sort(){ 
    Sort(0,length-1); 
} 

public void disp(){ 
    for(int i=0; i<length;++i){ 
     System.out.print(original[i]+" "); 
    } 
    System.out.println(); 
} 

public static void main(String[] args) { 

    QuickSortUsing3WayPartitioning qs = new QuickSortUsing3WayPartitioning(20); 
    qs.disp(); 

    qs.Sort(); 
    qs.disp(); 

} 

} 

Answer 6

난이 파티션 elemnts의 피봇보다 작은 동일하고 큰 분할 익스트라 방법에 관한 것이다 생각한다. 더 작고 큰 파티션 만 재귀 적으로 정렬해야합니다. 대화식 시각화를보고 the walnut으로 게임을 할 수 있습니다. 파티셔닝 방법이 일반적으로 "네덜란드 깃발 문제"라고 불리기 때문에 내가 사용한 색상은 빨간색/흰색/파란색입니다.