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

Now a wearable device to help you change your Habits !!

If you are like me then you might have a tendency to bite your nails, pull your hairs or keep doing something which you want to get rid off. Problem in such cases is awareness.

Soon you might be able to tame these habits using a wearable device. HabitAware has created a device called Liv.

A smart bracelet that creates awareness of subconscious behaviors like hair pulling, nail biting, skin picking and thumb-sucking in older children.

Willingness to change is the first step. Awareness is the second. Liv helps with this second step.

Learn how to generate a signed APK file

All Android Apps must be digitally signed before they are installed on a device.

This is required to verify identity of developer who published it. And also to verify if it has been tampered.

Follow the video to generate the signed APK file and also to learn how to automate the process.

 

Learn how to create and use a Android Module in your Android Project

You saw why using modules is important and how to create a Java module in an earlier Post. In a similar fashion you can add an Android module to your project.

Android Studio makes it easy to add a new module. Follow the video to understand the steps.

Source code is available here

What is Android Debug Bridge or ADB ?

An ADB is a command line tool which can be used to communicate with Emulator or Android Devices.

When your development machine needs to communicate with an Android Device it does so using ADB. It’s a process that is controlled by a command also known as adb.

The adb command works by talking to an adb server which runs in the background at port 5037. The server is also known as adb daemon or adbd.

Android Studio also talks to this server when it needs to run an app via an Android Device.

To work with ADB you need Android SDK.

Learn how to create and use a Java Module in Android Project

Creating modules is a good practice since it aids in reusability. In your Android project you can easily add a Java or Android module.

Follow the video to create a Java module and add it as a dependency in your Android Project.

Project source code is available in GitHub