Algorithm and Flowchart for Quick Sort with implementation in Java

[1699 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 algorithm

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)

Partition Pseudocode below rearranges the sub arrays in a place.

PARTITION (array A, int m, int n) 1 x = A[m] 2 o = m 3 for p = m + 1 to n 4 do if (A[p] < x) 5 then o = o + 1 6 swap A[o] with A[p] 7 swap A[m] with A[o] 8 return o

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
        

Algorithm Logic Test

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once. 



Need any help in Programming? Chat with Us

Comments



Online Compiler
Search
Algorithm Quiz

Only 5% Users were able to score above 75% in this Quiz. Can You Crack this?

Deals Ends in





Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    Quick Sort algorithm explanation

    Java Program for Quick Sort Algorithm

    Flowchart for Quick Sort