Quick Sort Java Algorithm | JavaSorting

Total Views : 49
Zoom In Zoom Out Read Later Print

we will discuss two different ways to implement quick sorting In Java Application. The project download URL has been added so that you can easily execute the given program, with appropriate examples and samples outputs added for quick sort In Java.

Here we are using two ways for sorting but they are not different from each other. Only difference is how we get input from the user and store it. Sorting of the element will be done in same way.

We will use following 2 ways to implement Quick Sort in Java.

1. Using Buffered Reader.
2. Using Array.

Quick Sort Using Buffered Reader

SortBufferReader.java

package com.manjeet.prodevsblog.quick;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SortBufferReader {

    public static void main(String[] args) throws IOException {

        System.out.println("Sorting Using Buffered Reader....");

        int n, i;
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter Number of Elements (n):");
        n = Integer.parseInt(b.readLine());
        int[] array = new int[n];

        System.out.println("Enter "+n+" Elements (Press Enter After Each Element) ");

        for( i = 0; i < n; i++) {
            array[i] = Integer.parseInt(b.readLine());
        }

        System.out.println( "Elements in Array Before Sorting...");
        printArray(array);

        sortArray(array, 0, n-1);

        System.out.println( "Elements in Array After Sorting");
        printArray(array);
    }

    public static void sortArray(int[] array,int l, int h) {
        if(l<h) {
            int m=partition(array, l, h);
            sortArray(array, l, m-1);
            sortArray(array,m+1, h);

        }
    }

    public static int partition(int[] array,int l,int h) {
        int i = l + 1, j = h, c = l, temp;

        for (; i <= j; ) {

            while (i <= h && array[i] < array[c])
                i++;
            while (array[j] > array[c] && j > l)
                j--;

            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            } else
                break;
        }

        temp = array[c];
        array[c] = array[j];
        array[j] = temp;
        return j;
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Output:

Sorting Using Buffered Reader....
Enter Number of Elements (n):6
Enter 6 Elements (Press Enter After Each Element) 
34
5
12
97
34
4
Elements in Array Before Sorting...
34 5 12 97 34 4 
Elements in Array After Sorting
4 5 12 34 34 97 

Process finished with exit code 0

Quick Sort Using Array & Scanner

SortArray.java

package com.manjeet.prodevsblog.quick;

import java.util.Scanner;

public class SortArray {

    public static void main(String[] args) {
        
        System.out.println("Sorting Using Array & Scanner....");

        int n, i;
        Scanner s = new Scanner(System.in);

        System.out.print("Enter Number of Elements (n):");
        n = s.nextInt();
        int[] array = new int[n];

        System.out.println("Enter "+n+" Elements (Press Enter After Each Element) ");

        for( i = 0; i < n; i++) {
            array[i] = s.nextInt();
        }

        System.out.println( "Elements in Array Before Sorting...");
        printArray(array);

        sortArray(array, 0, n-1);

        System.out.println( "Elements in Array After Sorting");
        printArray(array);
    }

    public static void sortArray(int[] array,int l, int h) {
        if(l < h) {
            int m = partition(array, l, h);
            sortArray(array, l, m-1);
            sortArray(array,m+1, h);

        }
    }

    public static int partition(int[] array,int l,int h) {
        int i = l + 1, j = h, c = l, temp;

        for (; i <= j; ) {

            while (i <= h && array[i] < array[c])
                i++;
            while (array[j] > array[c] && j > l)
                j--;

            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            } else
                break;
        }

        temp = array[c];
        array[c] = array[j];
        array[j] = temp;
        return j;
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + ", ");
        }
        System.out.println();
    }
}

Output:

Sorting Using Array & Scanner....
Enter Number of Elements (n):6
Enter 6 Elements (Press Enter After Each Element) 
45
4
-8
83
-3
-17
Elements in Array Before Sorting...
45, 4, -8, 83, -3, -17, 
Elements in Array After Sorting
-17, -8, -3, 4, 45, 83, 

Process finished with exit code 0

Sample Recursive Calls :

Elements in Array Before Sorting...
45, 4, -8, 83, -3, -17, 
45, 4, -8, 83, -3, -17, 
M : 4
-3, 4, -8, -17, 45, 83, 
M : 2
-8, -17, -3, 4, 45, 83, 
M : 1
-17, -8, -3, 4, 45, 83, 
-17, -8, -3, 4, 45, 83, 
-17, -8, -3, 4, 45, 83, 
-17, -8, -3, 4, 45, 83, 
Elements in Array After Sorting
-17, -8, -3, 4, 45, 83, 

1. The numbers enterd by the user will be stored in the Array array[].

2. The function printArray() prints the array elements, function sortArray() will sort the array elements using quick sort.

3.In quick sort, divide the array into partitions and sort each partition, then we will get the sorted array. So quick sort is also called as divide and conquer algorithm.

4. In this program sort() method calls itself recursively then partition() method partitions the array, repeats until there is no possibility to partition the array. Partition method partitions the array and sorts them.

5. Partition method returns the m value. m indicates where the array will be divided into partitions. Array divided in to two partitions as (a,l,m-3), (a,m+1,h)

6. From the given example the array elements are 45, 4, -8, 83, -3, -37.

partition method returns m=4 and the array is sorted as -3,4,-8,-37,45,83.

7. Now the array from index 4 to 3 will be sorted by sort(a,4,3) method, the rest of the elements in the array from index 4 to 5 will not be sorted. The array from index 4 to 3 is sorted and divided into a partition, now the partition from 4 to 2 elements are sorted and divided into a partition, partition from 4,1 elements are sorted, and there is no possibility to next partition. now the array from index 4 to 3 is sorted array. The array after sort(a,l,m-3) is -37,-8,-3,4,45,83.

Sort(a,m+1,h) will sort the remaining unsorted array and partition method will partition the unsorted part of the array. After two sort methods the sorted array is -37,-8,-3,4,45,15.

You can download the Complete project from below link.

See More

Latest Photos