In JAVA I\'ve already wrote the code for the Quick Sort and array and ONLY need

Question

In JAVA

I've already wrote the code for the Quick Sort and array and ONLY need help with the analysis part.

Create an array of 5000 randomly generated integers. Use the Quick sort algorithm to sort the elements of the array. Analyze the efficiency of the program. Specify the best and worst time needed to sort the elements using Quick sort.

I know that worst case for Quick Sort is O(n2) and that best /average case is O(n logn). I also know that Quick Sort works best for very large randomly ordered arrays, just like this program. But I don't understand what it means by analyzing the efficiency of the program and specifying the best and worst time needed to sort the elements. Is it looking for me to partially order the elements and then run Quick Sort and compare how long it takes to when its randomly ordered? If someone can really explain to me how to analyze the efficiency of the program and how to specify the best and worst time needed to sort the elements.

Here is my source code for the Quick Sort Algorithm :

public class QuickSort {

public static void quickSort(int[] array, int low, int high) {
if (array == null || array.length == 0) {
return;
}

if (low >= high) {
return;
}

// pick the pivot
int middle = low + (high - low) / 2;
int pivot = array[middle];

// make left < pivot and right > pivot
int i = low, j = high;
while (i <= j) {
while (array[i] < pivot) {
i++;
}

while (array[j] > pivot) {
j--;
}

if (i <= j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}

// recursively sort two sub parts
if (low < j) {
quickSort(array, low, j);
}

if (high > i) {
quickSort(array, i, high);
}
}
}

Here is the code for test program:

import java.util.*;
public class QuickSortTest {
public static void main(String[] args){
System.out.println("Quick Sort's best and average case is O(nlogn).");
System.out.println("Since Quick Sort works best with large arrays who's order is randomly generated, the algorithm is working at O(nlogn) in this program.");
Random r = new Random();
int [] anArray= new int[5000];
for (int i= 0; i<(anArray.length);i++){
anArray[i]= r.nextInt(5000)+1;
}
System.out.println("Array before Quick Sort");
printArray(anArray);
  
int low = 0;
int high = anArray.length-1;
QuickSort.quickSort(anArray, low, high);
System.out.println("Array after Quick Sort");
printArray(anArray);
  
}

  
public static void printArray(int [] array){
int // this just makes so the whole array can be printed
int twoTenths = (oneTenth*2);
int threeTenths = (oneTenth*3);
int fourTenths = (oneTenth*4);
int> int sixTenths = (oneHalf+oneTenth);
int sevenTenths = (oneHalf+twoTenths);
int eightTenths= (oneHalf + threeTenths);
int nineTenths = (oneHalf + fourTenths);
  
  
for(int i=0; i<(oneTenth); i++){
System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for (int i=oneTenth; i<(twoTenths); i++)
{ System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= twoTenths; i<threeTenths; i++)
{ System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= threeTenths; i< fourTenths; i++){
System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= fourTenths; i< oneHalf; i++){
System.out.print(array[i]);
System.out.print(" , "); }
  
System.out.println();
for(int i= oneHalf; i< sixTenths; i++){
System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= sixTenths; i< sevenTenths; i++){
System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= sevenTenths; i< eightTenths; i++){
System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= eightTenths; i< nineTenths; i++){
System.out.print(array[i]);
System.out.print(" , ");
}
System.out.println();
for(int i= nineTenths; i< array.length; i++){
System.out.print(array[i]);
System.out.print(" , ");
}
  
System.out.println();
System.out.println();
}
}

Explanation / Answer

public class MyQuickSort { private int array[]; private int length; public void sort(int[] inputArr) { if (inputArr == null || inputArr.length == 0) { return; } this.array = inputArr; length = inputArr.length; quickSort(0, length - 1); } private void quickSort(int lowerIndex, int higherIndex) { int i = lowerIndex; int j = higherIndex; // calculate pivot number, I am taking pivot as middle index number int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; // Divide into two arrays while (i

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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