Counting Comparisons in QuickSort [Java]

Compute the total number of comparisons used to sort the given input file by QuickSort.

(Programming Question from coursera.org)

Download Input Text File here -> QuickSort

The file contains all of the integers between 1 and 10,000 (inclusive) in unsorted order (with no integer repeated). The integer in the ith row of the file gives you the ith entry of an input array.

Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we’ll ask you to explore three different pivoting rules.
You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add m−1 to your running total of comparisons. (This is because the pivot element will be compared to each of the other m−1 elements in the subarray in this recursive call.)

WARNING: The Partition subroutine can be implemented in several different ways, and different implementations can give you differing numbers of comparisons. For this problem, you should implement the Partition subroutine as it is described in the video lectures (otherwise you might get the wrong answer).

DIRECTIONS FOR THIS PROBLEM:

For the first part of the programming assignment, you should always use the first element of the array as the pivot element.

 

Code:-


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;


public class Comparisons {
	
	static long noOfComparisons;
	public static void main(String args[]) throws IOException {

		BufferedReader bfr = new BufferedReader(new FileReader("QuickSort.txt"));
		int n =10000;
		int[] A = new int[n];
		String str = bfr.readLine();
		int i = 0;
		while (str != null) {
			A[i] = Integer.parseInt(str);
			i++;
			str = bfr.readLine();
		}
		
		QuickSort(A,0,A.length-1);
		
		System.out.println(noOfComparisons);
		
	}

	private static void QuickSort(int[] a, int l, int r) {
		
		int pivot;
		if(r>l){
			add(r-l);
		pivot =Partition(a,l,r);
		
		QuickSort(a, l, pivot-1);
		QuickSort(a, pivot+1, r);
		}
	}

	private static void add(int i) {
		noOfComparisons+=i;
		
	}

	private static int Partition(int[] a, int l, int r) {

		
		int p=a[l];
		int i =l+1;
		
		for(int j=l+1;j<=r;j++){
			if(a[j]

Output: 162085

Problem2:
Use Last element as pivot .

Solve this problem using same Partition function by swapping first and last element and then using same first element as pivot.

.......
.......

private static int Partition(int[] a, int l, int r) {
		
		Swap(a,l,r);
		
		int p=a[l];
		int i =l+1;
.......
.......

Output: 164123

3 thoughts on “Counting Comparisons in QuickSort [Java]”

    1. It can be done as 2nd part (I dont remember the 3rd Part now but you can find the required element and swap in same way as done in 2nd part).

      The question was taken from earlier Design Algo course which has started again.
      The answer to 3rd part was138382 you can verify with your code.

  1. about the 3rd part#:

    int p = averageno( a[l], a[(l+r)/2] , a[r] );

    if( p==a[r] )

    Swap(a,l,r);

    else if( p==a[(l+r)/2] )

    Swap(a,l,(l+r)/2);

Leave a Reply

Your email address will not be published. Required fields are marked *