Quick Sort Algorithm and Flowchart with implementation in Java

(290 Views)


What is Quick Sort Algorithm?

It is an algorithm of the type Divide & Conquer. Divide stands for : Rearranging the elements and split arrays into two sub-arrays and an element in between search that each element in left sub array is less than or equal to the average element and each element in the right sub- array is larger than the middle element.


Conquer stands for : Recursively, sorting two sub arrays.
Combine stands for: Combining the already sorted array.

QuickSort

Image Reference: Geeks for Geeks

Quick Sort Flowchart:

QuickSortFlowchart

Image Reference: Geeks for Geeks

Quick Sort PseudoCode:

QUICKSORT (array A, int m, int n) 1 if (n > m) 2 then 3 i ? a random index from [m,n] 4 swap A [i] with A[m] 5 o ? PARTITION (A, m, n) 6 QUICKSORT (A, m, o - 1) 7 QUICKSORT (A, o + 1, n)

Quick Sort Implementation in Java:

// Java program for implementation of QuickSort 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]; int i = (low-1); // index of smaller element for (int j=low; j< high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } /* 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) { /* pi is partitioning index, arr[pi] is now at right place */ int pi = partition(arr, low, high); // Recursively sort elements before // partition and after partition sort(arr, low, pi-1); sort(arr, pi+1, high); } } /* A utility function to print array of size n */ 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[] = {10, 7, 8, 9, 1, 5}; int n = arr.length; QuickSort ob = new QuickSort(); ob.sort(arr, 0, n-1); System.out.println("sorted array"); printArray(arr); } }

Output:

Sorted array: 1 5 7 8 9 10

Solution Worked 1 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote

        


Comments



Search


Play 2048 Game Online

Play Duckhunt Online
Search Tags