QuickSort in java using divide and conquer algorithm

Posted By: Java Examples - 1:40 PM

Share

& Comment


Algorithm :


Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

An example of quicksort thanks Wikipedia

Java version of the QuickSort  is given below :

 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sort.quicksort;

/**
 *
 * @author ACHCHUTHAN
 */
public class Quicksort {
    int array[];
    int size;

    public Quicksort(int n){
        size=n;
        //create array with size n+1
        array=new int[n+1];
        //asign value into the array
        for (int i=0;i<n;i++){
            array[i]=(int) Math.round(Math.random()*89+10);
        }
        //set the last element as big value
        array[n]=99999;
    }
    public int partition(int p, int q) {
        int i = p;
        int j = q + 1;
        // Get the pivot element from the middle of the list
        int pivot = array[p];
        // Divide into two lists
        do {
            // If the current value from the left list is smaller then the pivot
            // element then get the next element from the left list
            do {
                i++;// As we not get we can increase i
            } while (array[i] < pivot);
             // If the current value from the right list is larger then the pivot
            // element then get the next element from the right list
            do {
                j--;// As we not get we can increase j
            } while (array[j] > pivot);
            // If we have found a values in the left list which is larger then
            // the pivot element and if we have found a value in the right list
            // which is smaller then the pivot element then we exchange the values.
            if (i <j) {
                swap(i, j);
            }

        } while (i <j);
        //swap the pivote element and j th element
        swap(p, j);
        return j;
    }

    private void swap(int p, int j) {
        //exachage the elements
        int temp = array[p];
        array[p] = array[j];
        array[j] = temp;
    }

    public void quicksort(){
        // Recursion
        quicksort(0, size-1);
    }

    public void quicksort(int p, int q) {
        int j;
        if (p < q) {
            // Divide into two lists
            j = partition(p, q);
            // Recursion
            quicksort(p, j - 1);
            quicksort(j + 1, q);
        }
    }
    public void print(){
        //print the elements of array
       for(int i=0;i<size;i++){
        System.out.print(array[i]+" | ");
        }
       System.out.println();

    }

    public static void main(String args[]) {
        Quicksort q = new Quicksort(15);
        System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
        q.print();
        q.quicksort();
        System.out.println("After Sort > > > > > > > > > > > >");
        q.print();
        System.out.println("=======+============+=======+============+=======+============");
        Quicksort q2=new Quicksort(125);
        System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
        q2.print();
        q2.quicksort();
        System.out.println("After Sort > > > > > > > > > > > >");
        q2.print();
        System.out.println("=======+============+=======+============+=======+============");
        Quicksort q3=new Quicksort(5);
        System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<");
        q3.print();
        q3.quicksort();
        System.out.println("After Sort > > > > > > > > > > > >");
        q3.print();

    }
}

Output of this program
run:
Before Sort <<<<<<<<<<<<<<<<<<<<<
85 | 61 | 48 | 78 | 68 | 57 | 15 | 36 | 80 | 54 | 83 | 17 | 69 | 53 | 70 | 
After Sort > > > > > > > > > > > >
15 | 17 | 36 | 48 | 53 | 54 | 57 | 61 | 68 | 69 | 70 | 78 | 80 | 83 | 85 | 
=======+============+=======+============+=======+============
Before Sort <<<<<<<<<<<<<<<<<<<<<
60 | 92 | 42 | 63 | 70 | 60 | 92 | 29 | 37 | 95 | 89 | 27 | 57 | 49 | 14 | 19 | 41 | 18 | 71 | 46 | 80 | 48 | 36 | 34 | 65 | 
After Sort > > > > > > > > > > > >
14 | 18 | 19 | 27 | 29 | 34 | 36 | 37 | 41 | 42 | 46 | 48 | 49 | 57 | 60 | 60 | 63 | 65 | 70 | 71 | 80 | 89 | 92 | 92 | 95 | 
=======+============+=======+============+=======+============
Before Sort <<<<<<<<<<<<<<<<<<<<<
32 | 92 | 75 | 52 | 56 | 
After Sort > > > > > > > > > > > >
32 | 52 | 56 | 75 | 92 | 
BUILD SUCCESSFUL (total time: 1 second)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .