QuicksortがBubblesortよりも速いのはどのような状況ですか？どうして？

Question

クイックソート：

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); 
    } 
    } 

バブルソート：

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]); 
    } 
} 

最悪の場合：

クイックソート：n²

バブルソート：n²

平均ケース：

クイックソート：nlog（n）は

バブルソート：n²

だから通常、これはクイックソートがバブルソートよりも速くなる傾向があることを意味します。

しかし、Quicksortの方がBubblesortよりも速いのはどちらですか？

リストがほぼ並べ替え順になっている場合、Quicksortは再帰を続けることになり、非常に小さなコレクションではより早くなります。

Answer 1

通常、QuicksortはBubblesortよりも高速になる傾向がありますか？

はい。はるかに高速です。

すでにリストがほぼソートされている場合、Quicksortは再帰を続けます。

右。クイックソートの最悪の場合は大きな問題です。変更することなく、通常は実世界で使用するアルゴリズムではありません。