Java QuickSort Example

Chapter: Interview Programs Last Updated: 05-11-2016 13:18:24 UTC

Program:

            /* ............... START ............... */
                
public class JavaQuickSort {

	private int array[];
	private int length;

	public void sortElements(int[] arrayvalues) {

		if (arrayvalues == null || arrayvalues.length == 0) {
			return;
		}
		this.array = arrayvalues;
		length = arrayvalues.length;
		doQuickSort(0, length - 1);
	}

	private void doQuickSort(int lowIndex, int highIndex) {

		int i = lowIndex;
		int j = highIndex;

		int pivot = array[lowIndex + (highIndex - lowIndex) / 2];
		while (i <= j) {

			while (array[i] < pivot) {
				i++;

			}
			while (array[j] > pivot) {
				j--;
			}
			if (i <= j) {
				swapElements(i, j);

				i++;
				j--;

			}
		}

		if (lowIndex < j) {

			doQuickSort(lowIndex, j);
		}
		if (i < highIndex) {

			doQuickSort(i, highIndex);

		}
	}

	private void swapElements(int i, int j) {

		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;

	}

	public static void main(String a[]) {

		JavaQuickSort quicksort = new JavaQuickSort();
		int[] inputarray = { 32, 1, 23, 14, 43, 7, 6, 65 };

		System.out.println("Before sorting");
		for (int i : inputarray) {
			System.out.print(i);
			System.out.print(" ");
		}

		quicksort.sortElements(inputarray);

		System.out.println("After sorting");
		for (int i : inputarray) {
			System.out.print(i);
			System.out.print(" ");
		}
	}
}
                /* ............... END ............... */
        

Output

Before sorting
32 1 23 14 43 7 6 65 After sorting
1 6 7 14 23 32 43 65 

Notes:

  • Quick sort uses divide and conquer algorithm.
  • First will be divided in to two parts based on some pivot element. All elements which are less than pivot element will be placed left and and all elements which are greater than pivot will be in right part.
  • So now pivot element is exactly in middle. if we sort left and right side elements all elements will be sorted. Here recursive quick sort will take place in order to sort all elements.
  • Quick sort will be sorting these elements without using extra space that is the reason it is called in place sorting algorithm.
  • Using the first or middle elements as an pivot element. it splits the arrays by re arranging the elements like every thing that is less than pivot will come left side and all elements greater than or equal to pivot will come right side.
  • Now pivot is in middle and correct place it left and right arrays sorted then entire array will be sorted.
  • Quick sort exactly will do the same it will sort left and right recursively.
  • If size of input is very less merge sort will be time consuming.
  • For smaller inputs quick sort is faster than merge sort.
  • Time complexity of Quicksort default case is O(n log n).
  • Worst case Time complexity of Quicksort is O(n2).

Tags

QuickSort Example, Java, Interview Programs

Similar Programs Chapter Last Updated
Java Program To Find Frequency Of Character In String Interview Programs 28-09-2017
Java Program To Find Power Of Number Using While Loop Interview Programs 30-08-2017
Java Program To Count Divisors Of Integer Number Interview Programs 24-06-2017
Java Program To Sort N Names In Ascending Order Interview Programs 24-06-2017
Java Program To Count Total Number Of Words In String Interview Programs 24-06-2017
Java Program To Print All Prime Numbers From 1 to N Interview Programs 24-06-2017
Java Program To Extract Digits / Numbers From String Interview Programs 22-09-2018
Java First Repeated Character In String Interview Programs 16-05-2017
Java String Character Repetition Count Interview Programs 15-05-2017
Java Program To Check Vowel Or Not Interview Programs 25-09-2018
Java Program To Check Alphabet Or Not Interview Programs 06-04-2017
Java Program To Find First Repeated And Non Repeated Character In String Interview Programs 25-03-2017
Java Spiral Matrix Interview Programs 22-09-2018
Java Program To Reverse A Number Using Strings Interview Programs 13-02-2017
Java Program To Print Diamond Star Pattern Interview Programs 16-12-2016
Java Program To Print Pyramid Pattern Of Star Interview Programs 16-12-2016
Java Program To Find Second Largest Number In Array Interview Programs 04-12-2016
Java Depth First Search Interview Programs 04-12-2016
Java Breadth First Search Interview Programs 04-12-2016
Java Linked List Length Recursive Solution Interview Programs 17-11-2016
Java Linked List Length Iterative Solution Interview Programs 17-11-2016
Java Linked List Node Deletion At Given Position Interview Programs 17-11-2016
Java Linked List Node Delete Interview Programs 17-11-2016
Java Sum Of Digits Using Recursion Interview Programs 06-11-2016
Java Program To Reverse Vowels Of String Interview Programs 05-11-2016
Java Program To Remove Vowels From String Interview Programs 05-11-2016
Java Find Top Two Maximum Numbers In Array Interview Programs 05-11-2016
Java Binary Tree Spiral Level Traversal Interview Programs 04-11-2016
Java Binary Tree Preorder Traversal Interview Programs 04-11-2016
Java Binary Tree InOrder Traversal Interview Programs 31-10-2016

1 2 3 4 5