Java Program for Quick Sorting

What is quick sort ?

Quick sort is one of the divide-and-conquer algorithm.

Quick sort is to sort an array array[0], array[1],....array[n] by picking some element in the array as pivot element around which to rearrange the elements in the array in order to get sorted elements.

Quick sort reduces the space complexity and removes the use of the auxiliary array that is used in merge sort.

Use random pivot instead of first array element as pivot element to reduces the time complexity.

Quick Sort Algorithm

Pick the pivot element in random which can be first element also in the array.

Move all the elements in left side of pivot element which are less than pivot element.

Move all the elements in right side of pivot element which are greater than pivot element.

Partition array elements which are less than pivot element and repeat the process 1 to 3 till all sub array elements in sorted order.

Partition array elements which are greater than or equal to pivot element and repeat the process 1 to 3 till all sub array elements in sorted order.

Quick Sorting Steps

Quick Sorting Time complexity

Quick sorting time complexity is O(NlogN), here N is the number of elements in the list. worst case time complexity of this algorithm is O(N^2).

Quick Sorting Java Program

import java.util.Scanner;

public class QuickSortingTest {
	public static void swap(int[] listVals, int index1, int index2){
		int temp = listVals[index1];
		listVals[index1] = listVals[index2];
		listVals[index2] = temp;
	}    
	
	public static int partitionByPivot(int[] listVals, int startIndex, int endIndex){
		int i = startIndex + 1;
		// First element as pivot element.
		int pivotElement = listVals[startIndex];
		for(int j=startIndex+1;j<endIndex+1;j++){
	        // Arranges the list elements which are less than pivot                  
	        // on one side and which are greater that on other side.
			if(listVals[j]<pivotElement){
				swap(listVals, i, j);
				i += 1;
			}
		}
		// swaps pivot element in correct position
		swap(listVals, startIndex, i-1);
		// returns the updated pivot element position
		return i-1;
	}
	
	public static void quickSort(int[] listVals, int startIndex, int endIndex){
		if(startIndex < endIndex){
			// position of pivot element
			int pivotElementPosition =  partitionByPivot(listVals, startIndex, endIndex);
			quickSort(listVals, startIndex, pivotElementPosition-1);
			quickSort(listVals, pivotElementPosition+1, endIndex);
		}
	}

	public static void main(String[] args){
	    int[] numberList;
	    Scanner in = new Scanner(System.in); 
	    System.out.println("Quick Sorting");
	    System.out.println("--------------------");
	    System.out.println("Enter numbers count: ");                   
	    int count = in.nextInt();                   
	    numberList = new int[count];
	    System.out.println("Enter numbers: "); 
	    for (int i=0;i<count;i++){
	    	numberList[i]=in.nextInt();
	    }
	    in.close();
	    quickSort(numberList, 0, numberList.length-1);
	    
	    System.out.println("Sorted numbers: "); 
	    for(int number : numberList){
	    	System.out.print(number+"\t");
	    }
	}
}                                                                                                                                                                                                                

$ javac QuickSortingTest.java
$ java QuickSortingTest 
Quick Sorting
--------------------
Enter numbers count: 
5
Enter numbers: 
24
18
32
15
7
Sorted numbers: 
7	15	18	24	32