QuickSort가 BubbleSort보다 속도가 훨씬 느린 이유는 무엇입니까?

Question

내 quickSort가 왜 그렇게 느린지 궁금합니다. 다음 배열을 정렬하는 데 10-20 초가 걸립니다. Bubblesort (아래 그림 참조)가 자동으로 수행됩니다.

public static void quickSort(int[] tab, int lowIndex, int highIndex) { 
if (tab == null || tab.length == 0) { 
    return; 
} 

int i = lowIndex; 
int j = highIndex; 

int pivot = tab[lowIndex + (highIndex - lowIndex)/2]; 

while (i <= j) { 
    while (tab[i] < pivot) { 
    i++; 
    } 
    while (tab[j] > pivot) { 
    j--; 
    } 

    if (i <= j) { 
    int c = tab[i]; 
    tab[i] = tab[j]; 
    tab[j] = c; 
    i++; 
    j--; 
    } 

    if (lowIndex < j) { 
    quickSort(tab, lowIndex, j); 
    } 
    if (i < highIndex) { 
    quickSort(tab, i, highIndex); 
    } 
} 

} 

public static void bubbleSort(int[] arr) { 
int n = arr.length - 1; 
while (n >= 1) { 
    for (int i = 0; i < n; i++) { 
    if (arr[i] > arr[i + 1]) { 
     int c = arr[i]; 
     arr[i] = arr[i + 1]; 
     arr[i + 1] = c; 
    } 
    } 
    n--; 
} 
} 

public static void main(String[] args) { 
int[] t = new int[] { 5, 1, 33, 13, 21, 2, 12, 4, 
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1, 
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56, 
    74, 5, 3, 5, 1, 33, 13, 21, 2, 12, 4, 
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1, 
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56, 
    74, 5, 3, 74, 5, 3, 5, 1, 33, 13, 21, 2, 12, 4, 
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1, 
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56, 
    74, 5, 3 }; 

Answer 1

은 기본적으로, 당신의 거품 정렬은 어떤 방법으로 고장 -, 내가 얻을 다음 번 대런 Engwirda가 http://www.mycstutorials.com/articles/sorting/quicksort에서 자신의 코멘트에 링크 된 구현을 사용하고 새로 만든 배열마다 종류의 실행 :

인프라는 세 가지 테스트를 실행하는

bash-3.1$ time java -cp bin Sort none 

real 0m0.079s 
user 0m0.000s 
sys  0m0.015s 
bash-3.1$ time java -cp bin Sort quick 

real 0m0.084s 
user 0m0.015s 
sys  0m0.015s 
bash-3.1$ time java -cp bin Sort bubble 

real 0m0.115s 
user 0m0.000s 
sys  0m0.000s 

은 다음과 같습니다

이

private static int[] data() { 
    return new int[] { ... the same data as in the OP ... }; 
} 

public static void main(String[] args) { 
    if (args.length == 0 || args [ 0 ].equals ("bubble")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
      bubbleSort (data); 
     } 
    } else if (args [ 0 ].equals ("none")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
     } 
    } else if (args [ 0 ].equals ("quick")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
      quickSort(data, 0, data.length-1); 
     } 
    } else if (args [ 0 ].equals ("quick_op")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
      quickSort_op(data, 0, data.length-1); 
     } 
    } 
} 

그래서 올바르게 구현 빠른 정렬이 소요 ~ 검찰을 정렬 할 지 5μs ta이고 버블 정렬은 36μs가 걸리므로 데이터를 정렬 할 수 있습니다. 빠른 정렬 알고리즘은이 데이터에 대해 버블 정렬보다 성능이 우수합니다.

bash-3.1$ time java -cp bin Sort op_quick 

real 0m0.108s 
user 0m0.015s 
sys  0m0.015s 

여전히 빠르다 : 루프 외부 재귀 호출을 이동

는

다음과 같은 결과로, (거기에 다른 결함이 있다면 내가 확인하지 않은하지만) 코드가 배열을 정렬 의미 버블 정렬보다 빠르지 만 다른 구현처럼 빠르지는 않습니다 - 저는 여러분이 j와 i를 겹쳐 배열의 여러 부분을 한 번 이상 방문 할 것 같아요.