如何在Java的快速排序中计算comaprisons和swaps？

Question

我有一个用Quicksort对int数组进行排序的简单方法。我不知道如何正确计算交换和比较的数量，因为算法是递归的：

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

如何正确地做到这一点？

Answer 1

改为定义一个类变量，并在每次运行快速排序方法时更新类变量。

示例

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

Answer 2

您可以使用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);

编辑：当您要调用quicksort时：

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()