A simple QuickSort Program in Java

Introduction to Quick Sort

QuickSort algorithm is based on the Divide and Conquer Approach.

For a given sequence S there are 4 basic steps involved:

• Pick a number X from S. This program picks the last element.
• Create two Lists. One list will store elements less than X and the other will store greater than X.
• Sort the two lists recursively.
• Combine the left list elements with X and the right list elements.

The program below sorts a sequence of Integers. After which another version has been provided which can be used to sort a sequence of characters.These are my own versions of the QuickSort Algorithm.

Both the programs use a utility file which is also provided. The Source Code is also available here

package impl;

import java.util.ArrayList;

/*
 * Ankur Srivastava
 * QuickSort Implementation using ArrayList for Sorting a sequence of Integers
 * */

public class ArrayListQuickSort {

	public ArrayListQuickSort() { }

	public static void main(String[] args) {
		Utility.printList(sort(Utility.createMockList()));
	}
	
	public static ArrayList<Integer> sort(ArrayList<Integer> input){
		int size = input.size();
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		if(size > 1){
			int last = input.get(size-1);
			
			ArrayList<Integer> left = new ArrayList<Integer>();
			ArrayList<Integer> right = new ArrayList<Integer>();
			
			for(int i=0;i<size;i++){
				if(input.get(i) < last){
					left.add(input.get(i));
				}else if(input.get(i) > last){
					right.add(input.get(i));
				}
			}
			
			//Utility.printList(\"left\", left);
			//Utility.printList(\"right\", right);
			
			if(left != null && left.size() > 1){
				left = sort(left);	
			}
			if(right != null && right.size() > 1){
				right = sort(right);	
			}
			result = combine(left, last, right);
		}
		//Utility.printArray(result);
		return result;
	}
	
	public static ArrayList<Integer> combine(ArrayList<Integer> left, int center, ArrayList<Integer> right){
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		if(!left.isEmpty()){
			for(int i =0; i<left.size(); i++){
				result.add(left.get(i));
			}
		}
		result.add(center);
		if(!right.isEmpty()){
			for(int i = 0; i<right.size(); i++){
				result.add(right.get(i));
			}
		}
		//Utility.printList(\"merge\", result);
		return result;
	}
}

Next one demonstrates how to sort a character sequence

package impl;

import java.util.ArrayList;

public class ArrayListCharQS {

	public ArrayListCharQS() {
		// TODO Auto-generated constructor stub
	}

	public static void main(String[] args) {
		Utility.printCharList(sort(Utility.createMockCharList()));
	}
	
	public static ArrayList<Character> sort(ArrayList<Character> input){
		int size = input.size();
		ArrayList<Character> result = new ArrayList<Character>();
		
		if(size > 1){
			char last = input.get(size-1);
			
			ArrayList<Character> left = new ArrayList<Character>();
			ArrayList<Character> right = new ArrayList<Character>();
			
			for(int i=0;i<size;i++){
				if(input.get(i) < last){
					left.add(input.get(i));
				}else if(input.get(i) > last){
					right.add(input.get(i));
				}
			}
			
			//Utility.printList(\"left\", left);
			//Utility.printList(\"right\", right);
			
			if(left != null && left.size() > 1){
				left = sort(left);	
			}
			if(right != null && right.size() > 1){
				right = sort(right);	
			}
			result = combine(left, last, right);
		}
		//Utility.printArray(result);
		return result;
	}
	
	public static ArrayList<Character> combine(ArrayList<Character> left, char center, ArrayList<Character> right){
		ArrayList<Character> result = new ArrayList<Character>();
		
		if(!left.isEmpty()){
			for(int i =0; i<left.size(); i++){
				result.add(left.get(i));
			}
		}
		result.add(center);
		if(!right.isEmpty()){
			for(int i = 0; i<right.size(); i++){
				result.add(right.get(i));
			}
		}
		//Utility.printList(\"merge\", result);
		return result;
	}
}

The Utility file used by both the programs above

package impl;

import java.util.ArrayList;

public class Utility {

	public Utility() {
		// TODO Auto-generated constructor stub
	}
	
	public static void show(String str){
		System.out.println(str);
	}
	
	public static void printArray(int[] A){
		System.out.println(\"\");
		for(int i=0; i<A.length; i++){
			System.out.print(A[i]+\"  \");
		}
		System.out.println(\"\");
	}
	
	//Check if Array has 0\'s
	public static boolean emptyArray(int[] input){
		if(input[0] == 0 && input[input.length-1] == 0){
			return true;
		}
		return false;
	}
	
	public static ArrayList<Integer> createMockList(){
		ArrayList<Integer> inputArray = new ArrayList<Integer>();
		/*
		inputArray.add(6);
		inputArray.add(4);
		inputArray.add(7);
		inputArray.add(3);
		inputArray.add(2);
		*/
		inputArray.add(3);
		inputArray.add(6);
		inputArray.add(2);
		inputArray.add(7);
		inputArray.add(5);
		printList(inputArray);
		return inputArray;
	}
	
	public static ArrayList<Character> createMockCharList(){
		ArrayList<Character> inputArray = new ArrayList<Character>();
		/*
		inputArray.add(6);
		inputArray.add(4);
		inputArray.add(7);
		inputArray.add(3);
		inputArray.add(2);
		*/
		inputArray.add(\'d\');
		inputArray.add(\'b\');
		inputArray.add(\'a\');
		inputArray.add(\'f\');
		inputArray.add(\'e\');
		inputArray.add(\'a\');
		printCharList(inputArray);
		return inputArray;
	}
	
	public static void printList(ArrayList<Integer> list){
		printList(\"\", list);
	}
	
	public static void printList(String message, ArrayList<Integer> list){
		System.out.println(\"\");
		System.out.println(message);
		for(int i:list){
			System.out.print(i+\" \");
		}
		System.out.println(\"\");
	}
	
	public static void printCharList(ArrayList<Character> list){
		System.out.println(\"\");
		for(char i:list){
			System.out.print(i+\" \");
		}
		System.out.println(\"\");
	}
}