Java Programing! A 16 element array stores the integers 81, 16, 2, 89, 54, 23, 7
ID: 3767247 • Letter: J
Question
Java Programing!
A 16 element array stores the integers 81, 16, 2, 89, 54, 23, 76, 25, 37, 107, 1, 74, 45, 16, 31, and 58 in elements 0 through 15, respectively. They are to be sorted using the Quicksort.
a. How many passes will be performed to complete the sort?
b. Show the contents of the array at the beginning of the sort and after the first two passes.
c. How many partitions will there be after pass three?
d. Give the total number of comparisons and swaps performed by the algorithm using the formulas presented in Table 8.6.
Table 8.6 Performance of the Quicksort Algorithm Memory Overhead Range Bytes Speed Range Effort Algorithm Binary Tree fast/slow Comments high 8n Fast for random data, slow for already sorted data (n+1)[log2(n + 1)-2]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 <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
it will require atleast 8 passes to complete the sorting.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.