package com.nokia.verify.dataos.test; public class QuickSort { public void quickSort(int array[]) // pre: array is full, all elements are non-null integers // post: the array is sorted in ascending order { quickSort(array, 0, array.length - 1); // quicksort all the elements in the array } public void quickSort(int array[], int start, int end) { for (int i =0; i= 1) // check that there are at least two elements to sort { int pivot = array[start]; // set the pivot as the first element in the partition while (k > i) // while the scan indices from left and right have not met, { while (array[i] i) // from the left, look for the first i++; // element greater than the pivot while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first k--; // element not greater than the pivot if (k > i) // if the left seekindex is still smaller than swap(array, i, k); // the right index, swap the corresponding elements } swap(array, start, k); // after the indices have crossed, swap the last element in // the left partition with the pivot quickSort(array, start, k - 1); // quicksort the left partition quickSort(array, k + 1, end); // quicksort the right partition } else // if there is only one element in the partition, do not do any sorting { return; // the array is sorted, so exit } } public void swap(int array[], int index1, int index2) // pre: array is full and index1, index2 < array.length // post: the values at indices 1 and 2 have been swapped { int temp = array[index1]; // store the first value in a temp array[index1] = array[index2]; // copy the value of the second into the first array[index2] = temp; // copy the value of the temp into the second } public static void main(String[] args) { int arr[] = {3, 1, 4, 5, 9, 2, 6, 8, 7}; QuickSort qs = new QuickSort(); qs.quickSort(arr); } }