Quick Sort Implementation In Java – Working Sample Code Example

Quick Sort is a sorting technique which uses Divide and Conquer mechanism to do the sorting. The algorithm for Quick Sort which is also sometimes known with it’s alternative name of “Partition Exchange Sort” is given below:

Quick Sort Algorithm:

  1. Pick an element from the list as Pivot, usually the middle one.
  2. Re-arrange elements with elements smaller than pivot on one side and greater that pivot on the other side.
  3. Recursively apply this to the smaller partition and larger partitions separately.

Algorithm Complexity:

  • Best Case: nlogn
  • Worst Case: n^2
  • Average Case: nlogn

Java Implementation:

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 24, 2014
 * Last Modified On - Feb 24, 2014
 */
public class QuickSort {

	public static void main(String args[]) {
		int[] items = { 0, 5, -1, 2, 3, 9, 7, 12, 5, 4 };
		sort(items);
	}

	public static void sort(int[] items) {
		if (items == null || items.length <= 0) {
			return;
		}

		System.out.println("Input Array: " + Arrays.toString(items));
		quickSort(items, 0, items.length - 1);
		System.out.println("Sorted Array: " + Arrays.toString(items));

	}
	
	/**
	 * Recursively apply quickSort - one for partition smaller than pivot -
	 * another for partition bigger than pivot
	 */
	public static void quickSort(int items[], int start, int end) {
		if (start >= end) {
			return;
		}

		int pivot = partition(items, start, end);

		if (start < pivot - 1) {
			quickSort(items, start, pivot - 1);
		}

		if (end > pivot) {

			quickSort(items, pivot, end);
		}

		
	}

	/**
	 * Reorganizes the given list so all elements less than the first are before
	 * it and all greater elements are after it.
	 */
	private static int partition(int[] items, int start, int end) {

		int pivot = items[(start + end) / 2];
		while (start <= end) {
			while (items[start] < pivot) {
				start++;
			}
			while (items[end] > pivot) {
				end--;
			}

			if (start <= end) {
				swap(items, start, end);
				start++;
				end--;
			}
		}
		return start;

	}



	/**
	 * Swaps data from an array. 
	 */
	private static void swap(int[] array, int firstIndex, int secondIndex) {
		if (array == null || firstIndex < 0 || firstIndex > array.length
				|| secondIndex < 0 || secondIndex > array.length) {
			return;
		}
		int temp = array[firstIndex];
		array[firstIndex] = array[secondIndex];
		array[secondIndex] = temp;

	}

}

The output of running above program is:

Input Array: [0, 5, -1, 2, 3, 9, 7, 12, 5, 4]
Sorted Array: [-1, 0, 2, 3, 4, 5, 5, 7, 9, 12]
Tagged , , , , , , . Bookmark the permalink.

One Response to Bubble Sorting A String Array in Ascending And Descending Order

  1. Ririn says:

    Thanks buat script codenya, membantu saya mengerkajan tugas saya

Leave a Reply

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