O lava Programming-Sol × \\ (E) Activity 2 Design and D × D Acti ty 4 Sorting Ro
ID: 3868581 • Letter: O
Question
O lava Programming-Sol × (E) Activity 2 Design and D × D Acti ty 4 Sorting Routir ×Q Activity 1: Assignment 2 Secure I https://tdsbelearningontario.ca/d2Vie/content/100907 11/viewContent/88860719/View :: x M inbox (1)-shaheed ka AppsNBA MIX-20140 0 2014 NBA Mix. Hal Bayyinah TV: Dashbo Peelsch osSYOD : Muhammad Shahe e ) Homepage. Toronto D o Neymar Jr2014/201 Other bookmarks My Home eSummer-August 20 I Ej 1 Muhammad Kamran Program 2 - Sorting Efficiencies Save the following program as Sorting Efficiencies. You can copy the entire Sorting Routine program and modify it to do the following Write a program that will display a list of random numbers. The random numbers should be in the range from -10 000 to 10 000. The random numbers should be displayed in two text areas, one with A user should have the choice of the number of random numbers to display (10, 100, 1 000, or 5 000) . the order the numbers will be sorted in (ascending, descending) The program will sort the original unsorted numbers using each of the four sorting methods studied in this activity: selection, bubble, insertion, and quick. The program will display the counters for the number of times that a loop is executed, the number of times that a comparison is made, the number of times a value was shifted from one location to another, and the actual time, in milliseconds, that it took to complete the sort Sample Input Screen Basic Application Example Enter the "out of 'anters nteust 010 O100 010005000 ort Numbers Sort Repits Sort Order Ascng 3:00 PM 2017-08-17 Type here to searchExplanation / Answer
The below code is the code for the quick sort algorithm which is the hardest one to implement ( personal opinion).
I have also set and mentioned all the counters , the same method can be used to perform all the other sortings.
I have seprately written code for generating random numbers as it is going to be a one time deal to generate random numbers. So the code for generating random numbers looks like this:-
public class GenerateRandomIntByRange {
public static void main(String args[]){
If you want a number between 5 and 15 the range is 10 [15-5]
replace the 5 with the staring number.
If you want the lowest number in the range to be 5 then add 5.
Example :
int ran = (int)(Math.random()*100)-50;
will return a value in the range [-50;50]
*/
int random = (int)(Math.random()* 10000 );
System.out.println(random);
}
}
Quick Sort Algorithm:-
public class MyQuickSort {
private int array[];
private int length;
int cmp,loop,shift;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
cmp++;
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.
*/
cmp++;
loop++;
while (array[i] < pivot) {
cmp++;
loop++;
i++;
}
while (array[j] > pivot) {
cmp++;
loop++;
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
cmp++;
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
cmp++;
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
cmp++;
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
shift += 2;
}
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(" ");
}
}
}
public class MyQuickSort {
private int array[];
private int length;
int cmp,loop,shift;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
cmp++;
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.
*/
cmp++;
loop++;
while (array[i] < pivot) {
cmp++;
loop++;
i++;
}
while (array[j] > pivot) {
cmp++;
loop++;
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
cmp++;
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
cmp++;
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
cmp++;
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
shift += 2;
}
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(" ");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.