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("");
	}
}

 

 

Learn how to create different versions of your App like Free and Paid

Android framework makes it quite easy for you to generate different flavors and variants of your App. Like you can create a free version or a paid version of your App.

In order to do this you need to follow these steps:

You need to specify the variants or flavors in your App’s build.gradle file.

Like

productFlavors {
    demo {
        applicationId "com.edocent.demo"
        versionName "1.0-demo"
    }
    full {
        applicationId "com.edocent.full"
        versionName "1.0-full"
    }
}

In all likelihood your Free App version will need a different Activity compared to the Paid one. So you need to create different folders for the two flavors.

So go to the Project->src folder and create a new Java Folder – free.

Create another one for paid similarly.

Add appropriate Activity and other files to this folder.

And you are all set. Execute Generate Signed APK task from the Build option. This will ask you which flavor you need the APK for.

Cool isn’t it.

Source code is available here