CODEWITHSUNDEEP
javasortingquicksort
filiard
filiard

Reputation: 501

How to count comaprisons and swaps in Quicksort in Java?

I have a simple method to sort an array of int with Quicksort. I dont know how to properly count the number of swaps and comparisons, since the algorithm is recursive: 

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

Running it with small (10 ints) array returns this: 

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

How to do it properly?

Upvotes: 1

Views: 4542

Answers (2)

Jason
Jason

Reputation: 11822

You can use an AtomicInteger to pass your counters around by reference. As opposed to using a class variable, this approach is thread safe and will allow you to perform multiple sorts at the same time while keeping your stats separate.

Redefine your method signature:

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

... and increment the value each time you perform a swap or comparison. Change this:

swaps++;

... to this:

swaps.incrementAndGet();

... and change this:

comparisons++;

... to this:

comparisons.incrementAndGet();

Lastly, update your recursion calls:

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

Edit: When you want to call the 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()

Upvotes: 0

Robby Duke
Robby Duke

Reputation: 11

Define a class variable instead and on each run of the quick sort method update the class variable.

Example

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

Upvotes: 1

Related Questions