如何計算Java中的Quicksort中的comaprisons和swaps？

我有一個簡單的方法來用Quicksort對int數組進行排序。我不知道如何正確計算互換和比較的次數，因爲算法是遞歸的：如何計算Java中的Quicksort中的comaprisons和swaps？

public void quicksort(int tablica[], int x, int y) { 
    int i,j,v,temp; 
    i=x; 
    j=y; 
    int swaps=0; 
    int comparisons=0; 
    v=tablica[(x+y)/2]; 
    while (i<=j) 
    { 
     while (tablica [i] <v) 
     { 
      i++; 
     } 
     while (tablica [j] >v) 
     { 
      j--; 
     } 
     if (i<=j){ 
      temp = tablica [i]; 
      tablica [i]=tablica[j]; 
      tablica [j] = temp; 
      i++; 
      j--; 
      swaps++; 
     } 
     comparisons++; 
    } 
    if (x<j) 
     quicksort(tablica,x,j); 
    if (i<y) 
     quicksort(tablica,i,y); 
    System.out.println("Comparisons: " + comparisons); 
    System.out.println("Swaps: " + swaps); 
}

小（10個整數）陣列運行它返回：

Comparisons: 1 
Swaps: 1 
Comparisons: 1 
Swaps: 1 
Comparisons: 2 
Swaps: 2 
Comparisons: 1 
Swaps: 1 
Comparisons: 1 
Swaps: 1 
Comparisons: 1 
Swaps: 1 
Comparisons: 2 
Swaps: 1 
Comparisons: 4 
Swaps: 4

怎麼做正常嗎？

來源

2017-04-11 filiard

例如，您可以將變量定義爲字段。 – Koekje

定義一個類變量，並在快速排序方法的每次運行中更新類變量。

例

public class example { 
    private int swaps=0; 
    private int comparisons=0; 

    public void quicksort(int tablica[], int x, int y) { 
    int i,j,v,temp; 
    i=x; 
    j=y; 

    v=tablica[(x+y)/2]; 
    while (i<=j) 
    { 
     while (tablica [i] <v) 
     { 
      i++; 
     } 
     while (tablica [j] >v) 
     { 
      j--; 
     } 
     if (i<=j){ 
      temp = tablica [i]; 
      tablica [i]=tablica[j]; 
      tablica [j] = temp; 
      i++; 
      j--; 
      swaps++; 
     } 
     comparisons++; 
    } 
    if (x<j) 
     quicksort(tablica,x,j); 
    if (i<y) 
     quicksort(tablica,i,y); 
    System.out.println("Comparisons: " + comparisons); 
    System.out.println("Swaps: " + swaps); 
    } 
}

來源

2017-04-11 22:18:08

我得到了正確的（我認爲）結果，但是「比較：21 交換：18」仍然被多次打印 – filiard

在您調用快速排序方法後，將打印語句移動到。 –

只需在quicksort方法之外移動最後兩行打印，然後進入'main'（就在您調用quicksort之後），然後您將打印一張最終結果。 @filiard – alfasin

您可以使用的AtomicInteger通過傳遞引用您的計數器。與使用類變量相反，此方法是線程安全的，並且允許您在保持統計信息分離的同時執行多種排序。

重新定義你的方法簽名：

public void quicksort(int tablica[], int x, int y, AtomicInteger comparisons, AtomicInteger swaps) {

...並在每次執行交換或比較時間增加值。更改此：

swaps++;

...這樣的：

swaps.incrementAndGet();

...並改變這種：

comparisons++;

...這樣的：

comparisons.incrementAndGet();

最後，更新您的遞歸調用：

if (x<j) 
    quicksort(tablica,x,j, comparisons, swaps); 
if (i<y) 
    quicksort(tablica,i,y, comparisons, swaps);

編輯：當你要撥打的快速排序：

AtomicInteger comparisonCounter = new AtomicInteger(0); 
AtomicInteger swapCounter = new AtomicInteger(0); 
quicksort(tablica, x, y, comparisonCounter, swapCounter); 

// now you can print out the total number of swaps and comparisons 
// using swapCounter.get() and comparisonCounter.get()

來源

2017-04-11 22:26:06 Jason

如何使用兩個AtomicIntegers現在調用此方法？它曾經是這樣的： quicksort（tablica，0，tablica.length-1，）; 但現在我必須添加AtomicIntegers，我沒有。 – filiard

編輯以演示調用快速排序。 – Jason

public class QuickSort{ 
public static int swaps = 0; 
public static int comparisons=0; 
public static void main(String[] args) { 
    QuickSort test = new QuickSort(); 
    int[] s = {2,51,8,342,65,72,22,10,324,1}; 
    test.sort(s,0,s.length - 1); 
    System.out.println(swaps); 
    System.out.println(comparisons); 
} 
public void sort(int s[], int a, int b){ 
    if(a >= b){return;} 
    int left = a; 
    int right = b - 1; 
    int pivot = s[b]; 
    while(left <= right){ 
     while(left <= right && s[left] < pivot){ 
      left ++; 
     } 
     while(left <= right && s[right] > pivot){ 
      right--; 
     } 
     if(left <= right){ 
     swap(s, left, right); 
     left++; 
     right--;} 
    } 
    comparisons++; 
    swap(s,left, b); 
    sort(s, a, left - 1); 
    sort(s, left + 1, b); 
} 

public void swap(int s[], int a, int b){ 
    int tmp = s[a]; 
    s[a] = s[b]; 
    s[b] = tmp; 
    swaps++; 
} 
}

可以幫助它，這是我對你的問題的回答quicksort.the版本的使用類別字段。靜態或不靜態都可以。

來源

2017-04-13 00:57:36 obgnaw

如何計算Java中的Quicksort中的comaprisons和swaps？

回答

相關問題