Create a complete Java program that implements a quick sort. The program should

Question

Create a complete Java program that implements a quick sort. The program should run the sort on three different sets of data: An array of randomly generated integers .A list of sorted integers A list of integers sorted in reverse order Allow the user to specify the size of the array to sort. Test each run of the sort to make sure that it produces correct output. Add functionality to count the number of array comparisons taking place during each sorting algorithm. Run the sort for at least three different array sizes for each type of data set (random, sorted, reverse). For each data set/array size combination, list the expected number of operations from an algorithmic analysis of the sorting algorithm. Then compare the theoretical results with the results from your program runs. Present the results in a tabular format. For example: Theoretical Expectation Actual Performance Sort Array Type uickSort uickSort uickSort uickSort ickSort QuickSort Array Size 100 100 100 1000 1000 1000 Random Sorted Reverse Random Sorted Reverse P2 P2 P2

Explanation / Answer

import java.util.Scanner;

import java.util.concurrent.ThreadLocalRandom;

// Java program for the implementation of QuickSort Algorithm

class QuickSort

{

/* This function takes last element as the pivot,

the placing of pivot element at correct place, and placeing all

the smaller ones (smaller than the pivot) to left of

pivot and all elements that are greater towards right

of pivot */

int part(int ar[], int ll, int hl)

{

int pivot = ar[hl];

int i = (ll-1); // index of lower limit element

for (int j=ll; j<hl; j++)

{

counter++; //counting the number of comparisons

// If element at current location is smaller than or

// equal to pivot

if (ar[j] <= pivot)

{

i++;

// swap ar[i] and ar[j]

int temp = ar[i];

ar[i] = ar[j];

ar[j] = temp;

}

}

// swap ar[i+1] and ar[hl] (or pivot)

int temp = ar[i+1];

ar[i+1] = ar[hl];

ar[hl] = temp;

return i+1;

}

/* The main function for implementing QuickSort()

ar[] --> Array to be sorted,

ll --> Lower limit index,

hl --> Higher limit index */

void sort(int ar[], int ll, int hl)

{

if (ll < hl)

{

/* parti is partition index, ar[pi] is

now at right place */

int parti = part(ar, ll, hl);

// Recursively sort elements before

// partition and after partition

sort(ar, ll, parti-1);

sort(ar, parti+1, hl);

}

}

/* A utility function for printing array of size n */

static void printArray(int ar[])

{

int n = ar.length;

for (int i=0; i<n; ++i)

System.out.print(ar[i]+" ");

System.out.println();

}

//utility function to reverse an array

static void rvereseArray(int ar[],

int ll, int hl)

{

int temp;

  

while (ll < hl)

{

temp = ar[ll];

ar[ll] = ar[hl];

ar[hl] = temp;

ll++;

hl--;

}

}

public static int counter; //for counting the number of comparisons

// Driver program

public static void main(String args[])

{

int rand_int;

int ar[] ;

int n ;

System.out.println("Enter the Size of array");

Scanner sc= new Scanner(System.in);

n = sc.nextInt();

ar=new int[n];

for (int i=0;i<n;i++)

{

rand_int = ThreadLocalRandom.current().nextInt(); // Generating random numbers

ar[i]=rand_int;

}

QuickSort qs = new QuickSort();

qs.sort(ar, 0, n-1);

System.out.println("sorted array");

printArray(ar);

System.out.println("No. of comparisons for Random"+counter);

counter=0;

qs.sort(ar, 0, n-1);

printArray(ar);

System.out.println("No. of comparisons for Sorted"+counter);

counter=0;

rvereseArray(ar, 0, n-1);

//printArray(ar);

qs.sort(ar, 0, n-1);

printArray(ar);

System.out.println("No. of comparisons for Reversed"+counter);

}

}

N

(Array Size)

Theoretical

Expectation

Actual

Performance

Sort

N

(Array Size)

Array Type

Theoretical

Expectation

Actual

Performance

QuickSort 100 Random 460

  585

QuickSort 100 Sorted 4950

  4950

QuickSort 100 Reversed 4950

  4950

QuickSort 1000 Random 6907

  10995

QuickSort 1000 Sorted

  499500

  499500

QuickSort 1000 Reversed

  499500

  499500

QuickSort 10000 Random 92103

  163299

QuickSort 10000 Sorted

  49995000

  49995000

QuickSort 10000 Reversed

  49995000

  49995000

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.