Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class QuickSort
- {
- /* This function takes last element as pivot,
- places the pivot element at its correct
- position in sorted array, and places all
- smaller (smaller than pivot) to left of
- pivot and all greater elements to right
- of pivot */
- int partition(int arr[], int low, int high)
- {
- int pivot = arr[high];
- for(int i = low; i < high; i++) {
- if(arr[i] < pivot) {
- int temp = arr[i];
- arr[i] = arr[low];
- arr[low] = temp;
- low++;
- }
- }
- int temp = pivot;
- arr[high] = arr[low];
- arr[low] = temp;
- return low;
- }
- /* The main function that implements QuickSort()
- arr[] --> Array to be sorted,
- low --> Starting index,
- high --> Ending index */
- void sort(int arr[], int low, int high)
- {
- if (low < high)
- {
- int pIndex = partition(arr, low, high);
- sort(arr, low, pIndex -1);
- sort(arr, pIndex + 1, high);
- }
- }
- static void printArray(int arr[])
- {
- int n = arr.length;
- for (int i=0; i<n; ++i)
- System.out.print(arr[i]+" ");
- System.out.println();
- }
- // Driver program
- public static void main(String args[])
- {
- int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
- int n = arr.length;
- QuickSort ob = new QuickSort();
- ob.sort(arr, 0, n-1);
- System.out.println("sorted array");
- printArray(arr);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement