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]

Sorted Circular Linked List Implementation And Insert Operation

Circular Linked List Data Structure (Unsorted). Source: Wikipedia

Circular Linked List is a kind of Linked List where the elements are accessed sequentially and the last node of the sequence points back to the first node, thus creating a circle. Circular linked lists can be created with simple Java Objects. The only tricky portion is to understand how to link the next element.

The following piece of code demonstrates:

  1. How to create a circular linked list data structure
  2. How to insert elements to the list so that the insertion creates a sorted data structure.
  3. How to handle special scenarios such as:
    • Inserting to an empty list
    • Inserting duplicate elements
    • Inserting element smaller than head (thus forming new head)
    • Inserting element greater than tail (thus forming new tail)
    • Inserting element in between two elements.

package com.icodejava.blog.datastructure;
/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 22, 2014
 * Last Modified On - Feb 22, 2014
 */
public class CircularListInsert {
	public static void main(String args[]) {

		CircularList myList = new CircularList(5);
		myList.printAll();
		
		myList = myList.insert(2);
		myList.printAll();
		
		//test for value smaller than the head.
		myList = myList.insert(1);
		myList.printAll();
		
		myList = myList.insert(3);
		myList.printAll();
		
		//Test for duplicate value
		myList = myList.insert(5);
		myList.printAll();
		
		//test for value greater than he tail.
		myList = myList.insert(6);
		myList.printAll();
	}
}

class CircularList {
	CircularList next;
	int value;

	public CircularList(int value) {
		this.next = this;
		this.value = value;
	}

	/**
	 * @param value
	 *            - new value to be inserted in the list.
	 * @return head node in the circular list
	 * 
	 * This method inserts data in ascending order.
	 */
	public CircularList insert(int value) {

		// if the current list is null.
		if (this == null) {
			return new CircularList(value);
		} else if (this.next == this) {
			// if the current list is head and tail i.e. single element
			this.next = new CircularList(value);
			this.next.next = this;

			// return the smallest node as the head
			if (this.value < value) {
				return this;
			} else {
				return this.next;
			}
		} else if (value < this.value) {

			// if the value is smaller than the head
			// find the tail and append.

			CircularList temp = new CircularList(value);
			temp.next = this;

			CircularList current = this.next;
			while (current.next != this) {
				current = current.next;
			}

			current.next = new CircularList(value);
			current.next.next = this;

			return current.next;

		} else if (value >= this.value) {
			CircularList current = this;

			/**
			 * Keep looking for nodes until all the nodes are smaller than the
			 * value to be inserted.
			 */
			while (current.next != this && current.next.value <= value) {
				current = current.next;
			}

			/**
			 * Once we find the node to be inserted, make a copy of the
			 * current's next value. Insert a node as current's next. and Make
			 * current's next's next value as the previous next which has been
			 * copied as temp
			 */
			CircularList temp = current.next;
			current.next = new CircularList(value);
			current.next.next = temp;
			return this;

		}

		return this;
	}

	public void printAll() {

		if (this == null) {
			return;
		}

		CircularList current = this;
		
		do {

			System.out.print(current.value + ",");
			current = current.next;
		} while (current != this);

		System.out.println();
	}
}


The output of running this program is below. Please note that the elements appear sorted.

5,
2,5,
1,2,5,
1,2,3,5,
1,2,3,5,5,
1,2,3,5,5,6,

Finding Mean Value Of An Integer Array In Java

In Basic Algebra, mean is nothing but just an average of all the points and is calculated as a sum of all the numbers divided by the total count. Don’t be surprised if you are asked to write a java program that can calculate mean value of an array of integers.

The interviewer might be trying to test your coding style, clean coding ability and ability to think about the boundary conditions and user errors. As you can see in the program below, I have written the method to be fail proof from null value or an empty integer.

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 21, 2014
 * Last Modified On - Feb 21, 2014
 * 
 * This class can be used to find the mean value in an array
 */
public class AlgebraMeanFinder {
	
	public static void main(String args []) {
		int [] numbers = {5,5,7,2,3,9,8,9,2,6,7,8,1};
		/**
		 * Finding mean number of a valid integer array
		 */
		findMeanValue(numbers);
		
		/**
		 * Testing for null array
		 */
		findMeanValue(null);
		
		/**
		 * Passing an empty array
		 */
		findMeanValue(new int[] {});
	}

	/**
	 * @param numbers - array of numbers whose mean has to be found
	 * Mean is a simple average value of all numbers.
	 * This method is capable of handling boundary conditions.
	 */
	public static double findMeanValue(int[] numbers) {

		double sum = 0;
		if (numbers == null || numbers.length < 1) {
			System.out.println("\nInvalid Input. Returning 0. Input was:" + Arrays.toString(numbers));
			return sum;
		}

		for (int index = 0; index < numbers.length; index++) {
			sum += numbers[index];
		}

		double mean = (sum / numbers.length);
		System.out.println("\nInput Array is: " + Arrays.toString(numbers));
		System.out.println("Sum:" + sum + " Count:" + numbers.length + " Mean Value is: " + mean);

		return mean;

	}

}

Here is the output of this program.


Input Array is: [5, 5, 7, 2, 3, 9, 8, 9, 2, 6, 7, 8, 1]
Sum:72.0 Count:13 Mean Value is: 5.538461538461538

Invalid Input. Returning 0. Input was:null

Invalid Input. Returning 0. Input was:[]