Big O QuickSortアルゴリズムで反復をトレースする方法は？ C

Question

私は以下のCコードのクイックソートアルゴリズムを持っています。

#include <stdio.h> 
#include <stdbool.h> 

int list[] = {8, 1, 3, 4, 2, 10, 4, 6}; 
//int list[] = {2, 1, 10, 4, 5, 11, 12, 6}; 
//int list[] = {35, 33, 42, 10, 14, 19, 27, 44, 26, 31}; 
int main(int argc, char **argv) 
{ 

    printf("Unsorted list is: "); 
    printArray(list); 
    quickSort(0, 7); 
    printf("Sorted list is: "); 
    printArray(list); 

    return 0; 
} 

int partition(int left, int right, int pivot){ 

    int leftPointer = left -1; 
    int rightPointer = right; 
    while(true){ 

     while(list[++leftPointer] < pivot){ 
     //do nothing 
//  printf("proses index kiri %d\n", leftPointer); 

     } 

     while(rightPointer > 0 && list[--rightPointer] > pivot){ 
     //do nothing 
//  printf("proses index kanan %d\n", rightPointer); 
     } 

     if(leftPointer >= rightPointer){ 
      break; 
     }else{ 
      printf("item swapped :%d,%d\n", 
      list[leftPointer],list[rightPointer]); 

      swap(leftPointer, rightPointer); 
//   return; 
//   left++; 
//   right--; 
     } 

    } 
    printf("pivot swapped :%d,%d\n", list[leftPointer],list[right]); 
    swap(leftPointer, right); 
    printf("pivot index %d\n", leftPointer); 
    return leftPointer; 

} 

void quickSort(int left, int right){ 
    if(right - left <= 0){ 
     return; 
    }else{ 
     int pivot = list[right]; 
     int pIndex = partition(left, right, pivot); 
     quickSort(left, pIndex-1); 
     quickSort(pIndex+1, right); 
//  printf("aman lanjut proses"); 
    } 
} 

void printArray(int list[]){ 
    int i; 
    for(i = 0; i < 8; i++){ 
     printf(" %d ", list[i]); 
    } 
    printf("\n\n"); 
} 

void swap(int left, int right){ 
    //variabel sementara untuk menampung i 
    int temporary = list[left]; 

    //tukar posisi, sehingga yg kecil di kiri, yg besar di kanan. 
    list[left] = list[right]; 
    list[right] = temporary; 
} 

ここで、繰り返し（トレース）のステップを示すために「printf」を挿入する必要がありますか？

Big O表記の複雑さは、現在のデータでチェック/カウントしたいのですから。最高、平均、または最悪の場合を満たす。

Answer 1

comparison-based sorting algorithmsの場合、典型的には、実施された比較の数がカウントされる。理論的には、理論的には、単一ソート操作ごとに固定定数の他の演算を行うアルゴリズムを書くことは可能ですが、実際にはクイックソートやその他の正当な比較ベースのソートアルゴリズムではありません。また、ソートアルゴリズムは、比較時間が一定であるが、任意に大きな定数を有するオブジェクトをソートすることができる。

ます（この質問は、Cとしてタグ付けされていても）sort in cppreference.comの複雑さの定義を見てみると：（O（N・ログ（N））、N =のstd ::距離：

複雑最初、最後）、比較。

だから、あなたのコードでは、これはpartitionの行でなければなりません：

while(list[++leftPointer] < pivot) 

と

while(rightPointer > 0 && list[--rightPointer] > pivot){ 

Answer 2

ビッグOは、すべての "操作" は、同じコストを持っていることを言います。ポインタをインクリメントするのと同じくらい簡単です。したがって、グローバルカウンタを設定してから、すべての内部ループでインクリメントする必要があります。だから2つはleftpointerとrightpointerループの間に、while while trueループ。 \