Quicksort algorithm in java with example program

  • Quick sort uses divide and conquer algorithm.
  • First will be divided in to two parts based on some pivot element. All elements which are less than pivot element will be placed left and and all elements which are greater than pivot will be in right part.

  • So now pivot element is exactly in middle. if we sort left and right side elements all elements will be sorted. Here recursive quick sort will take place in order to sort all elements.
  • Quick sort will be sorting these elements without using extra space that is the reason it is called in place sorting algorithm.
  • Using the first or middle elements as an pivot element. it splits the arrays by re arranging the elements like every thing that is less than pivot will come left side and all elements greater than or equal to pivot will come right side.
  • Now pivot is in middle and correct place it left and right arrays sorted then entire array will be sorted.
  • Quick sort exactly will do the same it will sort left and right recursively.
  • If size of input is very  less merge sort will be time consuming.
  • For smaller inputs quick sort is faster than merge sort.
  • Time complexity of Quicksort  default case is O(n log n).
  • Worst case Time complexity of  Quicksort  is O(n2).
Steps to implement quick sort algorithm: 

  • Create a array with some elements. Choose pivot element as middle element. we can choose first or last also.
  • After choosing pivot element arrange the elements like all elements which are less than pivot value comes left side and elements greater than equal to pivot come right side of pivot.
  • And then apply same to both sides. until it becomes one. then all elements in array will be sorted.

 Program #1: Java Example program to sort elements of array using quick sort algorithm:

  1. package quicksortjava;

  2. public class QuickSort {
  3.  
  4.     private int array[];
  5.     private int length;
  6.  
  7. public void sortElements(int[] arrayvalues) {
  8.          
  9.         if (arrayvalues == null || arrayvalues.length == 0) {
  10.             return;
  11.         }
  12.         this.array = arrayvalues;
  13.         length = arrayvalues.length;
  14.         doQuickSort(0, length - 1);
  15. }
  16.  
  17.   private void doQuickSort(int lowIndex, int highIndex) {
  18.          
  19.         int i = lowIndex;
  20.         int j = highIndex;
  21.         
  22.         int pivot = array[lowIndex+(highIndex-lowIndex)/2];
  23.         
  24.         // now Divide the array into two arrays(actually we are maintaining single array only)
  25.         while (i <= j) {
  26.        
  27.             while (array[i] < pivot) {
  28.                 i++;
  29.                 
  30.             }
  31.             while (array[j] > pivot) {
  32.                 j--;
  33.             }
  34.             if (i <= j) {
  35.                 swapElements(i, j);
  36.                
  37.                 //move index to next position on both sides
  38.                
  39.                 i++;
  40.                 j--;
  41.                 
  42.                 
  43.             }
  44.         }
  45.         
  46.         // call quickSort() method recursively
  47.         if (lowIndex < j){
  48.        
  49.         doQuickSort(lowIndex, j);
  50.         }
  51.         if (i < highIndex){
  52.        
  53.         doQuickSort(i, highIndex);
  54.             
  55.         }
  56.     }
  57.  
  58.     
  59.      
  60. private void swapElements(int i, int j) {

  61.         int temp = array[i];
  62.         array[i] = array[j];
  63.         array[j] = temp;

  64.  }
  65.      
  66.  public static void main(String a[]){
  67.          
  68.     QuickSort quicksort = new QuickSort();
  69.         int[] inputarray = {32,1,23,14,43,7,6,65};
  70.         
  71.         System.out.println("Before sorting");
  72.         for(int i:inputarray){
  73.             System.out.print(i);
  74.             System.out.print(" ");
  75.         }
  76.        
  77.  quicksort.sortElements(inputarray);

  78.         System.out.println("After sorting");
  79.         for(int i:inputarray){
  80.             System.out.print(i);
  81.             System.out.print(" ");
  82.         }
  83.     }

  84. }
 Output:

  1. Before sorting
  2. 32 1 23 14 43 7 6 65 
  3. After sorting
  4. 1 6 7 14 23 32 43 65 

Execution flow explanation of quick sort algorithm

quick sort program in java using recursion program

How to find uppercase letters in a string in java

  • How can we count upper case letter in String  java ?
  • How to find uppercase letters in String  java?
  • How to find capital letters in string in java?
  • How u discover the capital letter given sentence?
  • Yes We can find uppercase or capital letters in a String using isUpperCase() method of Character class in java
  • In order to find number of uppercase letters in a string of all capital letters in a string we need to iterate all characters of a string in a loop and check individual characters are uppercase letters or not using Character class provided isUpperCase() method.
  • To find the uppercase letters in a string in Java, you can use the isUpperCase() method of the Character class.




Program #1: Java example program to find all capital letters / Uppercase letters in a String


  1. package findUppercaseletters.String;
  2. public class FinfUppercaseLetters {
  3.  
  4.     /**
  5.      * @website: www.instanceofjava.com
  6.      */
  7.  
  8.  public static void main(String[] args) {
  9.         
  10.         
  11.   String str= "How to Print Uppercase Letters in Java";
  12.  
  13.     for (int i = 0; i < str.length(); i++) {
  14.     
  15.             if(Character.isUpperCase(str.charAt(i))){    
  16.             System.out.println(str.charAt(i));
  17.             }
  18.             
  19.  }
  20.  
  21. }
  22.  
  23. }

 Output:


  1. H
  2. P
  3. U
  4. L
  5. J
  • Above code will print all the uppercase letters in the string.
  • Alternatively, you can also use the toUpperCase() method of the Character class to convert all the characters in the string to uppercase and then use the equals() method to compare them to the original character.
Program #2: Java example program to count number of upperCase letters in a String


how to find uppercase letters in a string in java

Creating array of objects in java example program

  • Array is collection of similar data types.
  • Arrays can hold collection of data with indexes
  • We already know that we can hold group of primitive variables
  • Arrays can hold referenced variables also like Strings and objects
  • So we can say it is possible to store or create array of objects in java



Declaring arrays in java:

  •  One dimensional array can be created like
  • int[] singlearray;
  • Two dimensional array can be created like 
  • int[][] intdoubleArray;       
  • double[][] doubleArray;

Instantiation and Initialization of Arrays

Program #1: Java example program to store string object in array
  1. package arraysofobjectsinjava;
  2. public class ArrayOfObjects {
  3.  
  4.     /**
  5.      * @www.instanceofjava.com
  6.      *  creating and assigning values to arrays in java
  7.      */
  8.    public static void main(String[] args) {
  9.         
  10.         int[] a= new int[2];
  11.         a[0]=1;
  12.         a[1]=2;
  13.         
  14.         System.out.println(a[0]);
  15.         System.out.println(a[1]);
  16.         
  17.         int[] var= {1,2,3,4,5};
  18.         
  19.         
  20.         for (int i = 0; i < var.length; i++) {
  21.             System.out.println(var[i]);
  22.         }      
  23. int[][] array=new int[2][2];       
  24.         
  25.         array[0][0]=1;
  26.         array[0][1]=2;
  27.         array[1][0]=3;
  28.         array[1][1]=4;
  29.         
  30.   for(int i=0; i<array.length; i++) {
  31.  
  32.                for(int j=0; j<array[1].length; j++)
  33.                    System.out.print(array[i][j] + " ");
  34.                System.out.println();
  35. }  
  36.  
  37. }
  38.  
  39. }

 Output:


  1. 1
  2. 2
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 1 2 
  9. 3 4

Array of objects in java:

Program #2: Java example program to store string object in array


  1. package arraysofobjectsinjava;
  2. public class ArrayofStringObjects {
  3.  
  4.     /**
  5.      * @www.instanceofjava.com
  6.      * Storing String objects in String array
  7.      */
  8.     public static void main(String[] args) {
  9.         
  10.         
  11.         String a[]= new String[5];
  12.         a[0]="array of objects";
  13.         a[1]="object array in java";
  14.         a[2]="array of objects in java example program";
  15.         a[3]="array of objects in java tutorial";
  16.         a[4]="how to make array of objects in java";
  17.         
  18.         for (int i = 0; i < a.length; i++) {
  19.             System.out.println(a[i]);
  20.         }
  21.  
  22. }
  23.  
  24. }

Output:
  1. array of objects
  2. object array in java
  3. array of objects in java example program
  4. array of objects in java tutorial
  5. how to make array of objects in java

Creating custom array of objects in java
  •  We can also store custom objects in arrays .
  • Create a employee class.
  • Create multiple objects of employee class and assign employee objects to array.
  • Arrays can store objects but we need to instantiate each and every object and array can store it

Program#3: java example program to create custom objects and store in array


Employee.java

  1. package arraysofobjectsinjava;
  2. public class Employee {
  3.  
  4.     String name;
  5.     int id;
  6.     
  7.     Employee(String name, int id){
  8.         this.name=name;
  9.         this.id=id;
  10.         
  11.     }
  12.  
  13. }


array of objects in java

Tower of hanoi recursive solution using Java

  • Towers of  Hanoi is a famous game.
  • In this game there are three poles and N number of disks placed one over another in increasing in size from top to bottom.

  • Objective of this game is to move disks from first pole to last pole.
  • And the condition is we can not place bigger disk on top of smaller disk.
  • Initially all disks placed in first pole smaller disk will be on top and bigger disk will be on bottom.
  • We need to move all the disks from from first pole to last pole.

Rules of tower of  Hanoi:
  • We can move only one disk at a time.
  • At any poi of time larger disk can not be placed on smaller disk.
  • In order to solve this problem we have given a second pole so we can use second pole and move disks from  first pole to third pole.
  • We can solve this using rec recursive procedure.
Tower of  Hanoi with Single disk: N=1
  • Three poles are A , B ,C
  • And a disk is present at A we need to move from A to C
  • As it its single disk we can directly move disk A - > C 
tower of hanoi recursive solution

 Tower of  Hanoi with Two disks : N=2
  • Three poles are A , B ,C
  • And two disks are placed in pole A, Disk 1 and Disk2 top to bottom.( assume Disk 2 is smaller and Disk 1 bigger)
  • Move Disk2 from A to  B 
  • Move Disk1 From A to C.
  • Move Disk2 from B to C.
tower of hanoi in data structure program


Tower of  Hanoi with Three disks : N=3

  • Three poles are A , B ,C
  • And three disks are placed in pole A, Disk 1  top to bot, Disk2 and Disk 2 top bottom to .( assume Disk 3 is smaller and Disk 1 bigger)
  • In this firs we need to move two disk from  A to B which we already done in above procedure
  • So we need to repeat that here.
  • Move Disk1 from A to C.
  • Now Moving two disks from B to C we have already seen in above procedure so its recursive.


Tower of Hanoi Recursive Algorithm:

N = number of disks

If  N == 1
  • Move Single disk from A to C
If   N >1

  1. 1.Move n-1 disks from start A to B  TowersofHanoi(n-1,start, end , aux)
  2. Move last Disk from A to C
  3. Move n-1 disks from B to C.             TowersofHanoi(n-1,start, aux, end )
  • Step 1 and 3 are recursive procedures.
  • Lets see hoe to write  java recursive program for this towers of  Hanoi problem
  • Here B as auxiliary pole.

Program #1: Java Example program on towers of  Hanoi:

  1. package towersofhanoi;
  2. import java.util.Scanner;
  3.  
  4. public class TowersofHanoi {
  5.  
  6. public void TOH(int n, String start, String aux, String end) {
  7.  
  8.            if (n == 1) {
  9.                System.out.println(start + " -> " + end);
  10.            } else {
  11.                TOH(n - 1, start, end, aux);
  12.                System.out.println(start + " -> " + end);
  13.                TOH(n - 1, aux, start, end);
  14.            }
  15. }
  16.  
  17. public static void main(String[] args) {
  18.  
  19.            TowersofHanoi towersOfHanoi = new TowersofHanoi();
  20.  
  21.            System.out.print("Enter number of discs: ");
  22.            Scanner scanner = new Scanner(System.in);
  23.            int discs = scanner.nextInt();
  24.            towersOfHanoi.TOH(discs, "A", "B", "C");
  25. }
  26.  
  27. }

 Output:

  1. Enter number of discs: 
  2. 3
  3. A -> C
  4. A -> B
  5. C -> B
  6. A -> C
  7. B -> A
  8. B -> C
  9. A -> C

8 different ways to convert int to String in java

  • How to convert string to int or integer to string in java?
  • When we are working on a project we will be having some scenarios of expecting a string from int or integer from string.
  • Now we will be discussing on how to convert Integer to String in java with example java programs.



8 different ways to convert int to String in java

1.Convert Integer to String using Integer.toString() method: 
2.Convert Integer to String using String.valueOf() method.
3.Convert Integer to String / int to String using new Integer(int).toString() 
4.Convert Integer to String / int to String using String.format() method 
5.Convert Integer to String / int to String using DecimalFormat 
6.Convert Integer to String/ int to String using StringBuffer / StringBuilder 
7.Convert Integer to String / int to String directly by adding to "" 
8.Convert Integer to String / int to String using Special radix. 


1.Convert Integer to String using Integer.toString() method:

  •  Integer is a wrapper class in java which is mainly used to represent or convert primitive int value to object.
  • And Integer class having some predefined methods.
  • Integer class has special predefined method to convert integer value to string toString();
  • toString is a static method in Integer class so that by using class name itself we can call that method to convert Integer to corresponding string value.
Program #1: Java Example program to convert Integer to String by using toString() method:


 Output:


  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.         
  9.         
  10.  Integer i = new Integer(64);
  11.         
  12.  //converting integer to string by calling toString() method on integer object
  13.  
  14.   String str= i.toString();
  15.   // also we can use like String str= Integer.toString(i);

  16.  System.out.println(str);
  17.  
  18. }
  19.  
  20. }
 Output:


  1. 64

2.Convert Integer to String using String.valueOf() method.

  •  Integer class have toString() method to convert integer to string value same way String class also has valueOf() method to convert int or integer to string.
  • String class has a static method valueOf() which takes int as argument and converts into string.

Program #2: Java Example program to convert int to string using valueOf() method.

  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.   Integer i = new Integer(64);       
  10.  
  11.  //converting integer to string by calling valueOf() method on String clas
  12.   String str= String.valueOf(i);
  13.         
  14.   System.out.println(str);
  15.         
  16.         
  17.   int number=123;
  18.   String numberstr= String.valueOf(number);
  19.         
  20.   System.out.println(numberstr);     
  21.      
  22. }
  23.  
  24. }
 Output:


  1. 64
  2. 123


3.Convert Integer  / int to String using new Integer(int).toString()
  •  And here by creating Integer object and directly calling tostring method.
  • We can convert into to string directly with one statement this will be done by using Integer(int).toString()


Program #3: Java Example program to convert int to string using new Integer(int ).toString()

  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.   int number=23;
  10.  
  11.  String numberstr=    new Integer(number).toString();
  12.         
  13.  System.out.println(numberstr);
  14.      
  15. }
  16.  
  17. }
 Output:


  1. 23

4.Convert Integer  / int to String using String.format() method

  •  Another alternative way to convert int t string is by calling String.format method.
  • String.format ("%d", number);
 
Program #4: Java Example program to convert int to string using String.format() method


  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.   int number=23;
  10.  
  11.  String numberstr=   String.format ("%d", number);
  12.         
  13.  System.out.println(numberstr);
  14.      
  15. }
  16.  
  17. }
 Output:


  1. 23

 5.Convert Integer  / int to String using DecimalFormat

  •  Another alternative way to convert int t string is by java.text.DecimalFormat
  • DecimalFormat class mainly used to represent numbers in formats.
  • Decimal format class providing format() method to convert int to string with specified format.

Program #5: Java Example program to convert int to string using DecimalFormat class


  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.   int number=23;
  10.        
  11.   DecimalFormat obj= new DecimalFormat("#");
  12.         
  13.   String numberstr=    obj.format(number);
  14.         
  15.   System.out.println(numberstr);
  16.         
  17.         
  18. DecimalFormat objct= new DecimalFormat("#,###");
  19.         
  20. String numberstr1=    objct.format(3400);
  21.         
  22. System.out.println(numberstr1);
  23.      
  24. }
  25.  
  26. }
 Output:


  1. 23
  2. 3,400

6.Convert Integer  / int to String using StringBuffer / StringBuilder

  •  StringBuffer and StringBuilder classes also providing toString() method to convert int to string

Program #6: Java Example program to convert int to string using StringBuffer and StringBuilder


  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.     int number=234;     
  10.    
  11.     StringBuffer sf=new StringBuffer();
  12.     sf.append(number);
  13.     String numberstr=    sf.toString();
  14.         
  15.    System.out.println(numberstr);
  16.         
  17.         
  18.     StringBuilder sb=new StringBuilder();
  19.     sb.append(number);
  20.     String nstr=    sb.toString();
  21.             
  22.     System.out.println(nstr);     
  23. }
  24.  
  25. }
 Output:


  1. 234
  2. 234

7.Convert Integer  / int to String directly by adding to ""

  • We can convert a number to string simply by concatenating to "".
  • But it is not recommended to use.

Program #7: Java Example program to convert int to string by concat to ""



  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.   int number=8538;
  10.  
  11.  String numberstr=   ""+number;
  12.         
  13.  System.out.println(numberstr);
  14.      
  15. }
  16.  
  17. }
 Output:


  1. 8538

8.Convert Integer  / int to String using Special radix.


Program #8: Java Example program to convert int to string using special radix


  1. package convertintegertostring.java;
  2. public class IntegerToString {
  3.  
  4.     /**
  5.      * @ website: www.InstanceOfJava.com
  6.      */
  7. public static void main(String[] args) {
  8.  
  9.  int number=536;
  10.  
  11.    String binaryString = Integer.toBinaryString(number);
  12.    System.out.println(binaryString);
  13.         
  14.    String octalString = Integer.toOctalString(number);
  15.    System.out.println(octalString);
  16.     
  17.    String hexString = Integer.toHexString(number);
  18.    System.out.println(hexString);
  19.         
  20.    String customString = Integer.toString(number, 7);
  21.    System.out.println(customString);
  22.  

  23. }
 Output:


  1. 1000011000
  2. 1030
  3. 218
  4. 1364

8 different ways to convert int to string in java


convert int to string in java example

 Output:


  1. 64
  2. 64
  3. 536
  4. 536
  5. 3,400
  6. 536
  7. 536
  8. 1000011000

Deep copy in java example program

  • Creating a copy of the object can be done in two ways 
  • Shallow copy and deep copy. we have already discussed about shallow copy
  • Shallow copy in java example program
  • In shallow copy of object only object reference will be copied and if we change any data inside object changes will reflect in cloned object also this means both are referring to same object.
  •  


Deep copy / Deep cloning in  Java

  • In deep copy completely a new object will be created with same data.
  • If we change the data inside original object wont reflect in deeply cloned object.

deep cloning vs shallow cloning in java



Program #1: Java example program to demonstrate deep copy / deep cloning

Sample :

  1. package com.shallowcopyvsdeppcopy;

  2. public class Sample {
  3. int a;
  4. int b;

  5. Sample (int a, int b){
  6.     this.a=a;
  7.     this.b=b;
  8. }

  9. }

Empclone :
  1. package com.shallowcopyvsdeppcopy;
     
  2. public class empclone implements Cloneable {
  3.  
  4.     Sample s;
  5.     int a;
  6.     
  7.     empclone(int a, Sample s){
  8.         this.a=a;
  9.         this.s=s;
  10.        
  11.     }
  12.      
  13. public Object clone()throws CloneNotSupportedException{ 
  14.        return new empclone(this.a, new Sample(this.s.a,this.s.a));
  15. }  
  16.            
  17.     
  18. public static void main(String[] args) {
  19.      
  20.         empclone a= new empclone(2, new Sample(3,3));
  21.         empclone b=null;
  22.     
  23.  try {
  24.              b=(empclone)a.clone();
  25.            
  26.  } catch (CloneNotSupportedException e) {
  27.             // TODO Auto-generated catch block
  28.             e.printStackTrace();
  29.         }
  30.         System.out.println(a.s.a);
  31.         System.out.println(b.s.a);
  32.        
  33.         a.s.a=12;
  34.         System.out.println(a.s.a);
  35.         System.out.println(b.s.a);
  36. }
  37.  
  38. }

OutPut:
  1. 3
  2. 3
  3. 12
  4. 3

What is the difference between shallow copy and deep copy:
  • When we create a shallow copy of the object only reference will be copied
  • When we create deep copy of the object totally new object with same data will be created. 
  • Shallow copy and deep copy will be done by using Cloneable  interface in java. 
Select Menu