Quick Sort Algorithm using Java

Quick Sort works on Divide and Conquer algorithm. Here, given array is divided into two parts, left and right. and both array are being sorted individually. After then we combine and will have sorted array.

How it works:

1. Pick up any element in Array. ex. middle element of array. we called this one as Pivot.
2. All elements which are smaller than Pivot are placed in one array and All elements which are larger than pivot are placed in another array
3. Using recursion sort both array using quicksort
4. Combine array as mentioned below.

Java Program using Quick sort algorithm:

package com.anuj.algorithms;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 
 * @author Anuj
 *
 */
public class QuickSort {

 public static void main(String[] args) {
  QuickSort quickSort = new QuickSort();
  List<Integer> input = quickSort.generateRandomNumbers(10);

  System.out.println(input);
  System.out.println(quickSort.quickSort(input));
 }

 private List<Integer> generateRandomNumbers(int n) {
  List<Integer> input = new ArrayList<Integer>();
  Random random = new Random();

  for (int i = 0; i < n; i++) {
   input.add(random.nextInt(n * 10));
  }
  return input;
 }

 private List<Integer> quickSort(List<Integer> input) {
  if (input.size() <= 1) {
   return input;
  }

  int middle = (int) Math.ceil((double) input.size() / 2);
  int pivot = input.get(middle);

  List<Integer> less = new ArrayList<Integer>();
  List<Integer> greater = new ArrayList<Integer>();

  for (int i = 0; i < input.size(); i++) {
   if (input.get(i) <= pivot) {
    if (i == middle) {
     continue;
    }
    less.add(input.get(i));
   } else {
    greater.add(input.get(i));
   }
  }

  return concate(quickSort(less), pivot, quickSort(greater));
 }

 private List<Integer> concate(List<Integer> less, int pivot, List<Integer> greater) {
  List<Integer> list = new ArrayList<Integer>();

  for (int i = 0; i < less.size(); i++) {
   list.add(less.get(i));
  }
  list.add(pivot);
  for (int i = 0; i < greater.size(); i++) {
   list.add(greater.get(i));
  }

  return list;
 }
}

Output

[60, 86, 17, 7, 18, 26, 69, 74, 97, 53]
[7, 17, 18, 26, 53, 60, 69, 74, 86, 97]