悪いコードはありますか？ （Cでの時間の複雑なクイックソート）

Question

void QuickSort(int* x, int first, int last) { 
    if (first >= last) 
     ; 
    else { 
     int pivotindex = Partition(x, first, last); 

     QuickSort(x, first, pivotindex - 1); 
     QuickSort(x, pivotindex + 1, last); 
    } 
} 

int Partition(int* x, int first, int last) { 
    int isbig = first + 1, issmall = last, tmp; 

    while (1) { 
     while (x[isbig++] < x[first] && isbig != last + 1);  // 

     while (x[issmall--] > x[first] && issmall != first); // 

     if (isbig < issmall) { //   tmp = x[issmall]; 
      x[issmall] = x[isbig]; 
      x[isbig] = tmp; 
     } 
     else { //   tmp = x[first]; 
      x[first] = x[issmall]; 
      x[issmall] = tmp; 

      break; // 
     } 
    } 

    return issmall; // 
} 

私はこのコードに問題があります。私は自分でコードする。 これは機能しています。しかし、問題は私が作ったマージソートアルゴリズムよりも比較的遅いです。 問題が何かを見つけることができません。 （マージソートとクイックソートの時間の複雑さは、ソートされていないデータでは同じだが、10,000のデータソートの場合はtime comparison ignore korean）

マージソートの10倍です。コードが悪いということだと思います。 しかし、どこにあるのかわかりません。 時間の複雑さを大きくするコードの悪い部分はありますか？

Answer 1

最悪の場合はO(n^2)です。ここに表示されています。これは、配列の最初の要素をピボットとして使用し、ソートされたデータをソートするので、配列が1つの要素とn-1要素に分割されるためです。

比較のため、mergesortは常にO(n log n)です。

x[first]を使用する代わりに、x[(first + last)/2]をピボットとして使用できます。

参照：https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot