В каких ситуациях Quicksort быстрее, чем Bubblesort? Зачем?

Question

Quicksort:

void Quicksort(int array[], int left, int right){ 
    int pivot = left, i,ch,j; 
    for(i=left+1;i<=right;i++){ 
     j = i; 
     if(array[j] < array[pivot]){ 
      ch = array[j]; 
      while(j > pivot){ 
      array[j] = array[j-1]; 
      j--; 
      } 
      array[j] = ch; 
      pivot++; 
     } 
    } 
    if(pivot-1 >= left){ 
     quick(array,left,pivot-1); 
    } 
    if(pivot+1 <= right){ 
     quick(array,pivot+1,right); 
    } 
    } 

BubbleSort:

void Bubblesort(int array[]) 
{ 
    int length = array.length; 
    int i,j,r,aux; 
    for(i=length-1; i >= 1; i--) 
    { 
     for(j=0; j < i ; j++) 
     { 
      if(array[j]>array[j+1]) 
      { 
       aux = array[j]; 
       array[j] = array[j+1]; 
       array[j+1] = aux; 
      } 
     } 
    } 

    for(k = 0; k < length; ++k) 
    { 
     printf("%d\n",array[k]); 
    } 
} 

Наихудший:

Quicksort: n²

BubbleSort: n²

Средний случай:

Quicksort: Nlog (п)

BubbleSort: n²

Так обычно это означает, что Quicksort будет, как правило, быстрее, чем BubbleSort.

Но в каких ситуациях Quicksort быстрее, чем Bubblesort?

Помнят, что, когда список уже находится в почти упорядоченном порядке, Quicksort будет продолжать рекурсию, а для очень маленьких коллекций bubblesort может быть быстрее.

Answer 1

Как правило, это означает, что Quicksort будет быстрее, чем Bubblesort?

Да. Много, намного быстрее.

Помнят, что, когда список уже находится в почти упорядоченном порядке, Quicksort будет продолжать рекурсию.

Право. Худший случай Quicksort - большая проблема, поэтому без модификации обычно это не алгоритм выбора для использования в реальном мире.