by BehindJava

Data Structures - Quick Sort Algorithm

Home » datastructures » Data Structures - Quick Sort Algorithm

In this tutorial, we are going to learn about quick sort in detail and its algorithmic implementation.

Quick Sort

  • In-place algorithm.
  • O(n log n) - base 2. we are repeatedly partitioning the array into two halves.
  • Divide and Conquer algorithm.
  • Recursive in structure.
  • Uses a pivot element to partition the array into two parts.
  • Elements < pivot to its left, elements > pivot to its right.
  • Pivot will then be in its correct sorted position.
  • Process is now repeated for the left array and right array.
  • Eventually, every element has been the pivot. So every element will be in its correct sorted position.
  • As with merge sort, we’ll end up partitioning the array into a series of 1- element arrays.
  • Unstable algorithm.

Quick Sort Algorithm

QUICK_SORT (A, p, r)

  1. if p < r
  2. then: q <- PARTITION ( A, p, r)
  3. QUICK_SORT (A, p, q-1)
  4. QUICK_SORT (A, q+1, r)

PARTITION (A, p, r)

  1. Set x <- A[r].
  2. Set i <- p-1.
  3. Repeat Step 4 to 6 for j <- p to r-1
  4. do if A[j] <= x.
  5. then i = i+1.
  6. Exchange A[i] <—> A[j]
  7. Exchange A[i+1] <—> A[r]
  8. return i+1.

TOWER (N, BEG, AUX, END)

  1. If N = 1, Then:
    (a) Write: BEG -> END.
    (b) Return.
    [End of If Structure.]
  2. Call TOWER (N-1, BEG, END, AUX).
    [Move N-1 disks from peg BEG to peg AUX.]
  3. Write BEG -> END.
  4. Call TOWER (N-1, AUX, BEG, END).
    [Move N-1 disks from peg AUX to peg END.]
  5. Return.

Quick Sort Programmatic Implementation in Java

public class QuickSort {
	public static void main(String[] args) {
		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

		quickSort(intArray, 0, intArray.length);

		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}
	}

	public static void quickSort(int[] input, int start, int end) {
		if (end - start < 2) {
			return;
		}

		int pivotIndex = partition(input, start, end);
		quickSort(input, start, pivotIndex);
		for (int i = 0; i < input.length; i++) {
			//System.out.println(input[i]);
		}
		quickSort(input, pivotIndex + 1, end);
	}

	public static int partition(int[] input, int start, int end) {
		// This is using the first element as the pivot
		int pivot = input[start];
		int i = start;
		int j = end;
		while (i < j) {
			// NOTE: empty loop body
			while (i < j && input[--j] >= pivot);
			if (i < j) {
				input[i] = input[j];
			}
			// NOTE: empty loop body
			while (i < j && input[++i] <= pivot);
			if (i < j) {
				input[j] = input[i];
			}
		}
		input[j] = pivot;
		return j;
	}
}

Output:

-22 -15 1 7 20 35 55