Quicksort

Note: Github link for below code is here

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 is compared to each of the other m−1 elements in the subarray in this recursive call.)

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

  2. Compute the number of comparisons (as in Problem 1), always using the final element of the given array as the pivot element.

  3. Compute the number of comparisons (as in Problem 1), using the “median-of-three” pivot rule. [The primary motivation behind this rule is to do a little bit of extra work to get much better performance on input arrays that are nearly sorted or reverse sorted.] In more detail, you should choose the pivot as follows. Consider the first, middle, and final elements of the given array. (If the array has odd length it should be clear what the “middle” element is; for an array with even length 2k, use the kth element as the “middle” element. So for the array 4 5 6 7, the “middle” element is the second one —- 5 and not 6!) Identify which of these three elements is the median (i.e., the one whose value is in between the other two), and use this as your pivot.
    SUBTLE POINT: A careful analysis would keep track of the comparisons made in identifying the median of the three candidate elements. You should NOT do this. That is, as in the previous two problems, you should simply add m−1 to your running total of comparisons every time you recurse on a subarray with length m.

Quicksort.java

package quicksort;

public class Quicksort {

public static int sort(int[] numbers, int startIndex, int endIndex) {

int numOfComparisons = sort(numbers, startIndex, endIndex, 0);
return numOfComparisons;
}

public static int sort(int[] numbers, int startIndex, int endIndex, int numOfComparisons) {

if (startIndex < endIndex) {
int pivotIndex = partition(numbers, startIndex, endIndex);
numOfComparisons = numOfComparisons + (endIndex - startIndex - 1);
numOfComparisons = +sort(numbers, startIndex, pivotIndex, numOfComparisons);
numOfComparisons = +sort(numbers, pivotIndex + 1, endIndex, numOfComparisons);
}
// System.out.println("numOfComparisons***: " + numOfComparisons);
return numOfComparisons;
}

private static int partition(int[] numbers, int startIndex, int endIndex) {
/*
* Case1.if pivot is first element of subarray then pivot =
* numbers[startIndex] Case2.if pivot is last element of subarray then
* pivot = numbers[endIndex], then exchange pivot element(i.e last
* element) with first element
*
*/

/*
* Case1:(Base Case) int pivot = numbers[startIndex];
*/
/*
* Case 2: int pivot = numbers[endIndex-1];
*
* swap(numbers,startIndex,endIndex-1);
*
*
*/
int middleIndex = (startIndex + endIndex) / 2;
System.out.println("middleIndex: " + middleIndex);
int pivot = medianOfThree(numbers[startIndex], numbers[endIndex - 1], numbers[middleIndex]);
//Swap medianOfThree i.e pivot with first element of array
if(pivot == numbers[endIndex-1]){
swap(numbers,startIndex, endIndex-1);
}
else if(pivot == numbers[middleIndex]){
swap(numbers,startIndex,middleIndex);
}
else pivot = numbers[startIndex];

int i = startIndex + 1;
for (int j = startIndex + 1; j < endIndex; j++) {
if (numbers[j] < pivot) {// else numbers[j]>pivot so just increment
// j // j
// swap numbers[j] with leftmost element of right(greater than
// pivot) array
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
}
}
// swap numbers[startIndex
// wihttp://community.jaspersoft.com/project/jaspersoft-dockerth
// rightmost element of left(less than
// pivot) array
int temp = pivot;
numbers[startIndex] = numbers[i - 1];
numbers[i - 1] = temp;
return i - 1;
}

private static void swap(int[] numbers, int firstIndex, int secondIndex){
int temp = numbers[firstIndex];
numbers[firstIndex] = numbers[secondIndex];
numbers[secondIndex] = temp;
}

private static int medianOfThree(int n1, int n2, int n3){

if(n1 > n2){
if(n1 > n3){
return n2>n3?n2:n3;
}
else if(n2<n3){ return n1>n2?n1:n2;
}
else{ return n1>n3?n1:n3;}}

else{
if(n2 < n3){ return n1>n2? n1:n2;
}
else{
return n1>n3?n1:n3;
}
}

}
}

[/language]

Main.java


package quicksort;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.Arrays;

public class Main {

public static void main(String args[]){

//int[] inputArray = {1, 2, 3, 4, 5, 6, 7 , 8};
Path path = Paths.get(args[0]);
int n = 10000;
int inputArray[] = new int[n];
int i = 0;
try {
BufferedReader reader = Files.newBufferedReader(path);
String line = null;
while((line = reader.readLine()) != null){
inputArray[i++] = Integer.parseInt(line);
}
} catch (IOException e) {

e.printStackTrace();
}

int numComparisons= Quicksort.sort(inputArray,0,inputArray.length);
System.out.println("Sorted Array is: " + Arrays.toString(inputArray));
System.out.println("numComparisons: " + numComparisons);
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s