Quicksort

Quicksort array in Java

What is Quicksort?

Quicksort is a divide and conquer algorithm. It first divides a large list into two smaller sub-lists and then recursively sort the two sub-lists. If we want to sort an array without any extra space, Quicksort is a good option. On average, time complexity is O(n log(n)).

The basic step of sorting an array are as follows:

  1. Select a pivot, normally the middle one
  2. From both ends, swap elements and make all elements on the left less than the pivot and all elements on the right greater than the pivot
  3. Recursively sort left part and right part

 

Quicksort in Java

package algorithm.sort;
 
public class QuickSort {
 
	public static void main(String[] args) {
		int[] x = { 9, 2, 4, 7, 3, 7, 10 };
		printArray(x);
 
		int low = 0;
		int high = x.length - 1;
 
		quickSort(x, low, high);
		printArray(x);
	}
 
	public static void quickSort(int[] arr, int low, int high) {
 
		if (arr == null || arr.length == 0)
			return;
 
		if (low >= high)
			return;
 
		//pick the pivot
		int middle = low + (high - low) / 2;
		int pivot = arr[middle];
 
		//make left < pivot and right > pivot
		int i = low, j = high;
		while (i <= j) {
			while (arr[i] < pivot) {
				i++; 	
			}
   			while (arr[j] > pivot) {
				j--;
			}
			if (i <= j) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				i++;
				j--;
			}
		}
 
		//recursively sort two sub parts
		if (low < j)
 			quickSort(arr, low, j);
   		if (high > i)
			quickSort(arr, i, high);
	}
 
	public static void printArray(int[] x) {
		for (int a : x)
			System.out.print(a + " ");
		System.out.println();
	}
}

Output:

9 2 4 7 3 7 10
2 3 4 7 7 9 10

The mistake I made is selecting the middle element. The middle element is not (low+high)/2, but low + (high-low)/2. For other parts of the programs, just follow the algorithm.

References:
http://www.programcreek.com/2012/11/quicksort-array-in-java

Published by

Milad Rahimi

I’m a software engineer with some big targets, I love what I do and nothing else matters…

Leave a Reply

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