Skip to main content

Quick sort Implementation

 Quick sort : In quick sort, we will consider a pivot element and divide the array so that all the lesser element will be in left side of pivot element while all the greater element will be in right side.

   This process we will continue recursively until array is fully sorted.
     Time complexity will beO(nlogn) but in worst case when elements are in sorted order time complexity will become O(n^2) as in each call only one element will be consider as sorted and for rest again we need to follow same process.
     space complexity will be O(1).

class QuickSort {

    public static void sort(int[] array) {
        int n = array.length;
        shuffle(array);
        sort(array, 0, n - 1);
    }

    private static void sort(int[] array, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(array, lo, hi);
        sort(array, lo, j - 1);
        sort(array, j + 1, hi);
    }

    private static int partition(int[] array, int lo, int hi) {
        int i = lo + 1;
        int j = hi;
        int pivot = array[lo];
        while (i <= j) {
            while (array[i] <= pivot) {
                i++;
                if (i > hi) break;
            }
            while (array[j] >= pivot) {
                j--;
                if (j == lo) break;
            }
            if (i >= j) break;
            swap(array, i, j);
        }
        swap(array, lo, j);
        return j;
    }

    private static void shuffle(int[] array) {
        Random random = new Random();
        for (int i = 1; i < array.length; i++) {
            int j = random.nextInt(i + 1); // [0, i]
            swap(array, i, j);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void print(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] A = {111, 80, 14, 21, 19, 31, 19, 121, 10, 190, 80, 6, 7};
        sort(A);
        print(A);
    }
}

Please have a look to the  source code of all sorting method from below link
  1. BUBBLE SORT PROGRAM
  2. SELECTION SORT PROGRAM
  3. INSERTION SORT PROGRAM
  4. MERGE SORT PROGRAM
  5. QUICK SORT PROGRAM
Labels:

Comments

Post a Comment

Popular posts from this blog

JAVA MEMORY LEAK, UTILISATION AND MONITORING USING JFR using Mission Control

JAVA MEMORY LEAK, UTILISATION AND MONITORING USING JFR using Mission Control Java flight recording(JFR) help us to analyse and find the root cause of any slowness in our program along with CPU usage , hot methods and garbage collection , profiling etc. To visualise we need to feed .jfr file to JDK mission control present in JDK bin folder. After successful compilation , we should run the program with below option which will generate the .jfr and feed to mission control.   command :  j ava -XX:+UnlockCommercialFeatures -XX:+FlightRecorder  -XX:StartFlightRecording=duration=200s,filename=flight.jfr -cp ./out/ path-and-class-name Below are some example to understand how this JFR can be helpful. 1. Lets consider we have created a java program in which we have used LinkList to store the elements and in same program we are using contains method inside a for loop of 1 million , in this case each time this contains method will be called then 1 million records will be sc...
Post a Comment
Read more

JAVA 8 FUNTIONAL INTERFACE

JAVA 8 FUNTIONAL INTERFACE  Funtional Interface :     An interface which has only one abstract method can be called a funtional interface. Comparable , Runnable , Callable all these interfaces has only one abstract method and can be consider as funtional interface.    How it works :        Once we will create a interface with one abstract method then java internally predicates the input type and based on the Interface reference it apply the logic mentioned after lambda expression    lets consider we have created an interface as below @FunctionalInterface public interface FuntionalExample { public int cal ( int a , int b) ; } And below class to test our funtional Interface. public class FuntionalInterfaceExample { public static void main (String args[]) { FuntionalExample addition=( int a , int b) -> a+b ; FuntionalExample subtraction=( int a , int b) -> a-b ; FuntionalExample multipl...
Post a Comment
Read more

Java Overview : Basic Java Overview

  JAVA BASIC OVERVIEW :  Java is high-level, class-based, robust, platform independent and object oriented programming language. Here each keyword has specific meaning which we need to understand.     How java internally works and execute our logic ?    We will need to write a file with extension .java, in which we will be writing our logics to be executed and this should be inside a class because java starts from main method of any class which is public inside the file named same as class name.    Example :  public class FirstJavaProgram {      public static void main(String[] args) {      //our logics      } }   This code should be saved in a file named as  FirstJavaProgram.java Whenever we are writing a java class, it's basically a blue print of what class has and it can do, it means characteristics  and behaviour , just like a simple real l...
Post a Comment
Read more