Quick Sort Java Implementation ...

Quick Sort: Quick sort is basically divide and conquer concept. It is just an awesome implementation of divide and conquer algorithm.

• Divide: Partition array into two subarrays such that element in the lower part of array is less than or equal to higher part of the array.

• Conquer: Recursively sort the two subarrays.

• Combine: After partition its need to combine both the partition.

There are many ways where sorting technique has been implemented. Quick Sort uses best and efficient idea to sort the input. It uses in place sorting paradigm. It means there is no extra memory is required to sort the input. It is very practical sorting technique as its average sort performance is O(nlogn) with small constant factors but worst time complexity O(n2).

Implementation: We have got two part of the process. One is partition process and other is sort process. This implementation is based on recursive pattern. first we divide the input array in two parts and we find the pivot element, this is the value we get after partitioning the input array. This pivot element will be at any index as it depends on given input array. once we get pivot element we recursively do the same process again and again based on the division happen in the array. As we can see from the java class implementation partitioned index is being used to divide the input.

/* Class definition to implement Quick sort in java */

package com.ds.sort;

import java.util.Scanner;

public class QuickSort

{

     private void quickSort(int[] array, int low, int high)

     {

         if (low < high) {

            int partionIndex = partition(array, low, high);

            quickSort(array, low, partionIndex - 1);

            quickSort(array, partionIndex + 1, high);

         }

     }

     private int partition(int[] arr, int low, int high)

     {

         int p = arr[high];

         int i = low - 1;

         int j = high + 1;

                  

         for (;;) {

             while (arr[++i] < p) {

                if (i >= high) {

                    break;

                }

             }

             while (arr[--j] > p) {

                if (j <= low) {

                    break;

                }

             }

             if (i < j) {

                 int tmp = arr[i];

                 arr[i] = arr[j];

                 arr[j] = tmp;

             } else {

                 return j;

             }

         }

     }

     public static void main(String[] args) throws Exception

     {

         QuickSort quickSort = new QuickSort();

         Scanner scan = new Scanner(System.in);

         System.out.println("Quick Sort Test\n");

         int n, i;

         System.out.println("Enter number of integer elements");

         n = scan.nextInt();

         /** Create array of n elements **/

         int arr[] = new int[n];

         System.out.println("\nEnter " + n + " integer elements");

         for (i = 0; i < n; i++) {

             arr[i] = scan.nextInt();

         }

         quickSort.quickSort(arr, 0, n - 1);

         System.out.println("\nElements after sorting ");

      

         for (i = 0; i < n; i++)

             System.out.print(arr[i] + " ");

             System.out.println();

             scan.close();

         }

     }