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){
}else if(input.get(i) > last){
}
}

//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++){
}
}
if(!right.isEmpty()){
for(int i = 0; i<right.size(); 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){
}else if(input.get(i) > last){
}
}

//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++){
}
}
if(!right.isEmpty()){
for(int i = 0; i<right.size(); 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>();
/*
*/
printList(inputArray);
return inputArray;
}

public static ArrayList<Character> createMockCharList(){
ArrayList<Character> inputArray = new ArrayList<Character>();
/*
*/
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("");
}
}```

Author: Ankur

I am Enthusiastic about Learning new things and sharing my Knowledge. I like programming and have a pretty good background in Computer Science.