It is a very small question but it just looks long! /*quick sort algorithm */ Re
ID: 669955 • Letter: I
Question
It is a very small question but it just looks long!
/*quick sort algorithm */
Read the Quick Sort Algorithm
and debug the code to print the correct output.
DO NOT hardcode the size of the file . Create a constant variable max_length = 200, which will be the maximum size of the file.
//---------------------------------------------------------------
NOTE: DO NOT ADD ANY COUT STATEMENTS IN THE FINAL SUBMISSION
OF THE CODE. ALSO, DO NOT MODIFY THE SEQUENCE OF THE INPUT, OR
CHANGE THE INPUT
//---------------------------------------------------------------
*/
#include <cstdlib>
#include <iostream>
using namespace std;
void print_array(int array[], int low, int hi)
{
cout<< "quick sort partition steps: ";
for (int j=low; j<=hi;j++)
cout <<" "<< array[j];
cout << endl;
}//end of print_array
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(" ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.