How to implement Quick Sort in java

How to implement Quick Sort in java

Quick sort which by name conveys sorting done quickly. It is based on Divide and Conquer as termed as Partition exchange sort. Though this sorting algorithm is not stable but it requires very less additional space and is fast. To follow its definition of divide and conquer, it first selects a pivot value and with the assistance of Pivot value list is splitting into three parts as mentioned below-

  1. Elements lesser than Pivot value
  2. Pivot Value
  3. Elements greater than Pivot value

There are many ways to choose the pivot value, but generally middle index item in list selected as pivot value. The actual position of pivot value in final sorted list is called a splitting point.

Worst Case Time Complexity : O(n2)

Best Case Time Complexity : O(n log n)

Average Time Complexity : O(n log n)

Space Complexity : O(n log n)

Space required by quick sort is very less, only O(n log n) additional space is required.

Quick sort is not a stable sorting technique, so it might change the occurrence of two similar elements in the list while sorting.

Let’s see an example-

package com.code2succeed.sorting;
import java.util.Arrays; 
public class QuickSort{ 
	public static void main(String args[]) { 

	// unsorted array with integer elements 
	int[] unsortedarray = {15, 14, 12, 10, 17, 16, 11, 13}; 
	System.out.println("Unsorted array :" + Arrays.toString(unsortedarray)); 
	QuickSortArray algorithm = new QuickSortArray(); // Sort integer array using QuickSortArray algorithm 
	algorithm.sort(unsortedarray); // Print sorted array 
	System.out.println("Sorted array :" + Arrays.toString(unsortedarray)); 
	} 
} 

// QuickSortArray defined here
class QuickSortArray {
	private int input[]; 
	private int length; 
	public void sort(int[] numbers) { 
		if (numbers == null || numbers.length == 0) { 
		return;
		} 
	this.input = numbers; 
	length = numbers.length; 
	quickSort(0, length - 1); 
	} 
	private void quickSort(int low, int high) { 
		int i = low; 
		int j = high; 
		// Select pivot element at middle index 
		int pivot = input[low + (high - low) / 2]; // Split given array into two arrays 
		
		while (i <= j) { 
	
				while (input[i] < pivot) { 
					i++; 
					}
				while (input[j] > pivot) {
					j--; 
					} 
				if (i <= j) { 
					swap(i, j); 
					i++; j--; // move index to next position on both sides 
					} 
			} // Recursively call quickSort() method 
	
		if (low < j) { 
			quickSort(low, j);
			} 
		if (i < high) { 
			quickSort(i, high); 
			} 
		} 
	private void swap(int i, int j) {
		int temp = input[i]; 
		input[i] = input[j]; 
		input[j] = temp; 
		} 
			
		}

Output

Unsorted array :[15, 14, 12, 10, 17, 16, 11, 13]
Sorted array :[10, 11, 12, 13, 14, 15, 16, 17]

Leave a Reply

Your email address will not be published. Required fields are marked *