大O如何在QuickSort算法中跟蹤迭代？ C

-1

#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」來指示迭代（跟蹤）的步驟？

因爲目標是我想檢查/計數當前的數據如何在大O符號中的複雜性？遇到最好的，平均的或最壞的情況。

來源

2016-10-06 Dark Cyber

對於comparison-based sorting algorithms，通常計數進行比較的次數。當然理論上可以編寫一種算法，該算法在每個排序操作中執行的操作不止是固定數量的其他操作，但實際上，既不是快速排序，也不是任何其他基於比較的排序算法。此外，排序算法可能會對比較時間恆定但是任意大的常量的對象進行排序。

如果你看看sort in cppreference.com（即使這個問題被標記爲C）的複雜性定義：

複雜度：O（N·日誌（N）），其中N =標準::距離（第一，最後），比較。

所以，在你的代碼，這應該是partition行：

while(list[++leftPointer] < pivot)

和

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

來源

2016-10-06 10:32:20

如果我把'printf（「trace」）;'在block 2內部，我計算的結果是9「trace」。所以複雜度是O（8 log 8）？ N =總項目。 –

@DarkCyber不，不完全。 O（8log8）只是一個常數。如果你要運行它的8個值，然後9個值，然後10個值等，併爲每一個你會計數打印的數量，你會得到一個函數，看起來像n logn（對於平均情況）。 –

大O說，每一個「操作」具有相同的成本。即使它像增加指針一樣微不足道。所以你需要建立一個全局計數器，然後用每個內部循環來增加它。所以，這兩個同時左側指針和右側指針循環，加上while循環。每個通過一個增量。\

來源

2016-10-06 12:47:16

大O如何在QuickSort算法中跟蹤迭代？ C

回答

相關問題