Write a program to implement the recursive Quicksort method. You should write a

Question

Write a program to implement the recursive Quicksort method.

You should write a recursive method called quicksort that takes as an arguement an array of integers. Your method should choose a pivot somewhere in the middle of the input array (it need not be exactly in the middle, especially if the array is of even size).

As we've seen, the quicksort method should then create two new arrays, less and greater, and place elements into them depending on whether they are greater or less than the pivot element. Recursively call quicksort on your two new arrays, less and greater.

Finally, write a main method to call and test your quicksort method. Create an array of integers by using the Java built-in method Math.random(). Your integers should each be greater than or equal to zero and less than 100.

Test your quicksort method with several ( at least 5) different input arrays of varying sizes, and validate that the results were sorted correctly. Include in your java file a detailed comment at the top describing the different inputs you tested and the results that you saw.

Explanation / Answer

/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package quicksort;
import java.util.Random;
/** * * @author M K Khedawat */ public class Quicksort { private static int[] numbers; private static int number; private static int SIZE=10; private static int MAX =99; public static void main(String[] args) { numbers = new int[SIZE]; Random generator = new Random(); for (int i = 0; i < numbers.length; i++) numbers[i] = generator.nextInt(MAX);    System.out.println("Before Sorting"); for (int i = 0; i < numbers.length; i++) { System.out.print(numbers[i]+" "); }    System.out.println();    sort();    System.out.println("After Sorting"); for (int i = 0; i < numbers.length; i++) System.out.print(numbers[i]+" "); System.out.println(); }
public static void sort() { // check for empty or null array if (numbers ==null || numbers.length==0){ return; } number = numbers.length; quicksort(0,number - 1); }
private static void quicksort(int low, int high) { int i = low, j = high; // Get the pivot element from the middle of the list int pivot = numbers[low + (high-low)/2];
// Divide into two lists while (i <= j) { // If the current value from the left list is smaller then the pivot // element then get the next element from the left list while (numbers[i] < pivot) { i++; } // If the current value from the right list is larger then the pivot // element then get the next element from the right list while (numbers[j] > pivot) { j--; }
// If we have found a values in the left list which is larger then // the pivot element and if we have found a value in the right list // which is smaller then the pivot element then we exchange the // values. // As we are done we can increase i and j if (i <= j) { exchange(i, j); i++; j--; } } // Recursion if (low < j) quicksort(low, j); if (i < high) quicksort(i, high); }
private static void exchange(int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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