Question

As code is given below, follow the instructions:

1. Count the number of comparisons and find where to put that counter in the code

2. Pick a random pivot, right pivot, left pivot, middle pivot for each smaller array /sub-array

import java.util.*;

import java.util.List;

public class QuickSort {

public static void main(String[] args) {

int[] values = { 6, 5, 4, 3, 1, 7, 8 };

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

IntQuickSorter.quickSort(values);

System.out.println("\nFirst Sorted order: ");

for (int element : values)

System.out.print(element + " "); }

public static void quickSort(int array[]) {

doQuickSort(array, 0, array.length - 1); }

private static void doQuickSort(int array[], int start, int end){

int pivotPoint;

pivotPoint = partition(array, start, end);

doQuickSort(array, start, pivotPoint - 1);

doQuickSort(array, pivotPoint + 1, end); }

private static int partition(int array[], int start, int end) {

int pivotValue = array[start];

int endOfLeftList = start;

int mid = (start + end) / 2;

int unsortedValue;

int scan;

swap(array, start, mid);

for (scan = start + 1; scan <= end; scan++) {

if (array[scan] < pivotValue) {

endOfLeftList++;

swap(array, endOfLeftList, scan); } }

swap(array, start, endOfLeftList);

  return endOfLeftList; }

private static void swap(int[] array, int a, int b) {

int temp;

temp = array[a];

array[a] = array[b];

array[b] = temp; } }

Answer 1

Code: (For pivot as middle element)

import java.util.*;

import java.util.List;

public class Main {
static int ctr=0; //static counter for counting comparisons
public static void main(String[] args) {

int[] values = { 6, 5, 4, 3, 1, 7, 8 };

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

quickSort(values);

System.out.println("\nFirst Sorted order: ");

for (int element : values)

System.out.print(element + " ");

System.out.println("\n Total number of comparisons: "+ctr);
  
}

public static void quickSort(int array[]) {
  

doQuickSort(array, 0, array.length - 1);
  
}

private static void doQuickSort(int array[], int start, int end){

int pivotPoint;
if(start<end){

pivotPoint = partition(array, start, end);

doQuickSort(array, start, pivotPoint - 1);

doQuickSort(array, pivotPoint + 1, end);
  
}
  
}

private static int partition(int array[], int start, int end) {
int mid = (start + end) / 2;

int pivotValue = array[mid]; //pivot as middle element

int endOfLeftList = start;

int unsortedValue;

int scan;

swap(array, start, mid);

for (scan = start + 1; scan <= end; scan++) {
ctr+=1; //incrementing comparisons

if (array[scan] < pivotValue) {

endOfLeftList++;

swap(array, endOfLeftList, scan); } }

swap(array, start, endOfLeftList);

return endOfLeftList; }

private static void swap(int[] array, int a, int b) {

int temp;

temp = array[a];

array[a] = array[b];

array[b] = temp; } }

Output:

Code: (For pivot as starting element)

import java.util.*;

import java.util.List;

public class Main {
static int ctr=0; //static counter for counting comparisons
public static void main(String[] args) {

int[] values = { 6, 5, 4, 3, 1, 7, 8 };

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

quickSort(values);

System.out.println("\nFirst Sorted order: ");

for (int element : values)

System.out.print(element + " ");

System.out.println("\n Total number of comparisons: "+ctr);
  
}

public static void quickSort(int array[]) {
  

doQuickSort(array, 0, array.length - 1);
  
}

private static void doQuickSort(int array[], int start, int end){

int pivotPoint;
if(start<end){

pivotPoint = partition(array, start, end);

doQuickSort(array, start, pivotPoint - 1);

doQuickSort(array, pivotPoint + 1, end);
  
}
  
}

private static int partition(int array[], int start, int end) {
int mid = (start + end) / 2;

int pivotValue = array[start]; //pivot a starting element

int endOfLeftList = start;

int unsortedValue;

int scan;

swap(array, start, mid);

for (scan = start + 1; scan <= end; scan++) {
ctr+=1; //incrementing comparisons

if (array[scan] < pivotValue) {

endOfLeftList++;

swap(array, endOfLeftList, scan); } }

swap(array, start, endOfLeftList);

return endOfLeftList; }

private static void swap(int[] array, int a, int b) {

int temp;

temp = array[a];

array[a] = array[b];

array[b] = temp; } }

Output:

Code: (For pivot as ending element)

import java.util.*;

import java.util.List;

public class Main {
static int ctr=0; //static counter for counting comparisons
public static void main(String[] args) {

int[] values = { 6, 5, 4, 3, 1, 7, 8 };

System.out.println("Original order: ");

for (int element : values)

System.out.print(element + " ");

quickSort(values);

System.out.println("\nFirst Sorted order: ");

for (int element : values)

System.out.print(element + " ");

System.out.println("\n Total number of comparisons: "+ctr);
  
}

public static void quickSort(int array[]) {
  

doQuickSort(array, 0, array.length - 1);
  
}

private static void doQuickSort(int array[], int start, int end){

int pivotPoint;
if(start<end){

pivotPoint = partition(array, start, end);

doQuickSort(array, start, pivotPoint - 1);

doQuickSort(array, pivotPoint + 1, end);
  
}
  
}

private static int partition(int array[], int start, int end) {
int mid = (start + end) / 2;

int pivotValue = array[end]; //pivot a starting element

int endOfLeftList = start;

int unsortedValue;

int scan;

swap(array, start, mid);

for (scan = start + 1; scan <= end; scan++) {
ctr+=1; //incrementing comparisons

if (array[scan] < pivotValue) {

endOfLeftList++;

swap(array, endOfLeftList, scan); } }

swap(array, start, endOfLeftList);

return endOfLeftList; }

private static void swap(int[] array, int a, int b) {

int temp;

temp = array[a];

array[a] = array[b];

array[b] = temp; } }

Output: