Reverse int Array Iteratively in Java

A reverse of a primitive int array can be achieved by swapping elements from the start with the end iteratively.

If the swap operation of the primitive array elements starts from the index 0 then it is going to be enough to iterate till the half of the array.

Following is the in-place where there is no need to create-allocate a new array for reversing primitive array items implementation in Java.

package basics;

public class IterativeArrayReverse {

 private static void reverseArray( int[] inArr )
 {
     if ( inArr==null || inArr.length==0 )
         return ;
        
     int len = inArr.length;
     for( int i=0; i<len/2; i++ )
         swap(inArr, i, len-i-1);
 }
 
 private static void swap( int[] inArr, int i, int j )
 {
     int temp = inArr[i];
     inArr[i] = inArr[j];
     inArr[j] = temp;
 }
 
 public static void main(String[] args) {
  
     int[] arr = { 1,2,3,4,5,6 };
     System.out.println("Before Reverse");
     for( int i=0; i<arr.length; i++ )
         System.out.printf("%s ", arr[i]);  
  
     reverseArray( arr );
  
     System.out.println("\nAfter Reverse");
     for( int i=0; i<arr.length; i++ )
         System.out.printf("%s ", arr[i]);
  
     int[] arr2 = {4,3,6,2,7,8,9,5};
     System.out.println("\n\nBefore Reverse");
     for( int i=0; i<arr2.length; i++ )
         System.out.printf("%s ", arr2[i]);  
  
     reverseArray( arr2 );
  
     System.out.println("\nAfter Reverse");
     for( int i=0; i<arr2.length; i++ )
         System.out.printf("%s ", arr2[i]);
 }
}

Create a IterativeArrayReverse.java file in your workspace.

When the main method inside the IterativeArrayReverse class executed it is going to print :

Before Reverse
1 2 3 4 5 6
After Reverse
6 5 4 3 2 1

Before Reverse
4 3 6 2 7 8 9 5
After Reverse
5 9 8 7 2 6 3 4

Generic Method to Print Array Elements in Java

Generics in Java enable programmers to provide compile-time type-safety.

There are some main benefits of using generics in Java such as :

1-) Strong type-checking
2-) Elimination of casts
3-) Provide a way to develop generic algorithms

Methods can also be designed in a generic fashion in Java, too. Following generic method prints all the elements of an array one-by-one in a for-loop for both wrapper types and custom defined types.

package basics;

public class GenericPrint {

 static class Employee
 {
  String name;
  Employee(String pName)
  {
   name = pName;
  }
  
  public String toString() {
   return "[Employee Name = "+name+" ]";
  }
 }
 
 // Generic method
 public static <T> void print( T[] inParam )
 {
  for( T t: inParam )
  {
   System.out.printf("%s ", t);
  }
 }
 
 
 public static void main(String[] args) {
  
  String[] strArr = {"D1","D2","D3","D4"};  
  print(strArr);
  
  Integer[] intArr = { 1,2,3 };
  System.out.println();
  print(intArr);
  
  Double[] dArr = { 5.5, 6.6, 7.7 };
  System.out.println();
  print(dArr);
    
  Employee e1 = new Employee("Emply1");
  Employee e2 = new Employee("Emply2");
  Employee e3 = new Employee("Emply3");
  
  Employee[] empArr = { e1, e2, e3 };
  
  System.out.println();
  print(empArr);  
 } 
}

Create a GenericPrint.java file in your workspace.

When the main method inside the GenericPrint class executed it is going to print :

D1 D2 D3 D4
1 2 3
5.5 6.6 7.7
[Employee Name = Emply1 ] [Employee Name = Emply2 ] [Employee Name = Emply3 ]

Shell Sort Comparable Array Items in Java

Shell sort is considered as an extension of insertion sort algorithm.

Insertion sort algorithm is not suggested for large input sets but shell sort comes with increased speed achievements for insertion sort algorithm.

Shell sort achieves speed improvement by exchanging of input entries that are away from each other and produces partially sorted input data sets.

Space and time complexity values are :

Worst case performance : О(n²)
Best case performance : О(n log² n)
Average case performance : depends on gap sequence

Space complexiy :  О(n) total, O(1) auxiliary

There is an animation for the shell sort algorithm at :

Following is the Java implementation of the Shell Sort algorithm where the sort method accepts an array of Comparable items as input parameter.

package basics;

public class ShellSort {

 public static void sort(Comparable[] a) {

  // Sort a[] into increasing order.
  int N = a.length;
  int h = 1;
  while (h < N / 3)
   h = 3 * h + 1;
  
  // h-sort the array.
  while (h >= 1) { 
   for (int i = h; i < N; i++) { 
    for (int j = i; j >= h && (a[j].compareTo(a[j - h]) < 0); j -= h) {
     Comparable temp = a[j];
     a[j] = a[j - h];
     a[j - h] = temp;
    }
   }
   h = h / 3;
  }

 }

 public static void main(String[] args) {

  String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };

  System.out.println("Before Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println("\n");

  sort(strArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println();

  Integer[] intArr = { 9, 8, 7, 6, 6, 5, 4, 3, 2, 2, 1 };

  System.out.println();
  System.out.println("Before Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println("\n");

  sort(intArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println();
 }
}

Create a ShellSort.java file in your workspace.

When the main method inside the ShellSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, so it is safe to send an array of items where each item implements Comparable interface in Java.

Integer and String classes in Java implement Comparable interface so it is acceptable to send this types as parameters to sort method.

Insertion Sort Comparable Array Items in Java

Insertion sort is one of the most common sorting algorithms.

Insertion sort algorithm achieves expected output by applying following steps :

1-) Start from the beginning index
2-) Compare next element with the previous item
3-) If current element is smaller than the previous element than swap elements
4-) Repeat step 3 until a sorted array is achieved

Space and time complexity values are :

Worst case performance О(n²)
Best case performance О(n)
Average case performance О(n²)

There is an animation for the insertion sort algorithm at :

Following is the Java implementation of the Insertion Sort algorithm where the sort method accepts an array of Comparable  items as input parameter.

package basics;

public class InsertionSort {

 public static void sort(Comparable[] a) {

  // Sort a[] into increasing order.
  int N = a.length;
  
  // Insert a[i] among a[i-1], a[i-2], a[i-3]....
  for (int i = 1; i < N; i++) { 
   for ( int j = i; j > 0 && ( (a[j].compareTo( a[j-1]))< 0 ); j--)
   {
       Comparable temp = a[j];
       a[j] = a[j - 1];
       a[j - 1] = temp;    
   }    
  }

 }

 public static void main(String[] args) {

  String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };

  System.out.println("Before Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println("\n");

  sort(strArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println();

  Integer[] intArr = { 9, 8, 7, 6, 6, 5, 4, 3, 2, 2, 1 };

  System.out.println();
  System.out.println("Before Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println("\n");

  sort(intArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println();
 }
}

Create an InsertionSort.java file in your workspace.

When the main method inside the InsertionSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, so it is safe to send an array of items where each item implements Comparable interface in Java.

Integer and String classes in Java implement Comparable interface so it is acceptable to send this types as parameters to sort method.

Selection Sort Comparable Array Items in Java

Selection sort is one of the in-place sorting algorithms.

It is considered simple to implement but not efficient for large inputs.

General steps :

1-) Start from the beginning index
2-) Find the minimum
3-) Swap the found minimum with the item at the starting position of the set
4-) Do it until the last item is reached


Space and time complexity values are :

Worst case performance О(n²)
Best case performance О(n²)
Average case performance О(n²)

Worst case space complexity O(n) total, O(1) auxiliary

Following is the Java implementation of the Selection Sort algorithm where the sort method accepts an array of Comparable items as input parameter.

package basics;

public class SelectionSort {

   public static void sort(Comparable[] a) { 
  
    int N = a.length;
  
    for (int i = 0; i < N; i++) { 

        int minIndex = i;
        for (int j = i + 1; j < N; j++)
        if ( a[j].compareTo(a[minIndex])<0 )
             minIndex = j;

        if (minIndex != i) {
            Comparable temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
  
  }

  public static void main(String[] args) {
  
    String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };
  
    System.out.println("Before Sort = " );
    for (int i = 0; i < strArr.length; i++)
     System.out.print(strArr[i] + " ");
    System.out.println("\n");
  
    sort(strArr);
  
    System.out.println("After Sort = " );
    for (int i = 0; i < strArr.length; i++)
     System.out.print(strArr[i] + " ");
    System.out.println();
  
    Integer[] intArr = { 9,8,7,6,6,5,4,3,2,2,1 };
  
    System.out.println();
    System.out.println("Before Sort = " );
    for (int i = 0; i < intArr.length; i++)
     System.out.print(intArr[i] + " ");
    System.out.println("\n");
  
    sort(intArr);
  
    System.out.println("After Sort = " );
    for (int i = 0; i < intArr.length; i++)
     System.out.print(intArr[i] + " ");
    System.out.println();
  }
}

Create a SelectionSort.java file in your workspace.

When the main method inside the SelectionSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, it is safe to send an array of items where each item implements Comparable interface in Java.

Custom Reverse Primitive Integer Array in Java

In order to reverse an integer primitive array in java an in-place algorithm can be used.

General algorithm for reversing an integer array is :

1-) Traverse the array until the midpoint found in a loop construct
2-) Implement a swap algorithm to exchange values of the items in the array

Following is a utility method used to reverse an existing array in java.

package basics;

public class ArrayUtility {
 
 static int[] reverse( int[] input )
 {
     if( input==null || input.length==0 )
         return null;
        
     int N = input.length;
  
     for( int i=0; i<N/2; i++ )
     {
        int temp = input[i];
        input[i] = input[N-i-1];
        input[N-i-1] = temp;
     }
  
     return input;
 } 

 public static void main(String[] args) {
  
  int[] original = {22,55,66,11,32,56,67,89,95,10};
  
  System.out.print("Original Array = ");
  for( int i = 0; i<original.length; i++ )
   System.out.print( original[i]+" " );
  
  int[] reverseArray = reverse( original );
 
  System.out.print("\nReversed Array = ");
  for (int i = 0; i <reverseArray.length; i++)
   System.out.print(reverseArray[i]+" ");  
 }
 
}

Create a ArrayUtility.java file in your workspace.

When the main method inside the ArrayUtility class executed it is going to print :

Original Array = 22 55 66 11 32 56 67 89 95 10
Reversed Array = 10 95 89 67 56 32 11 66 55 22

Custom Deep Copy Primitive Integer Array in Java

There are different methods to create copies of an array. Deep copy is considered as an expensive method when compared to shallow copying.

Following is a utility method used to copy an existing array into a new freshly created array in java.

package basics;

import java.util.Arrays;

public class ArrayUtility {
 
 static int[] copy( int[] input )
 {
     if ( input==null || input.length==0 )
         return null;
        
     int N = input.length;
     int[] copy = new int[N];
     for( int i = 0; i<N ; i++ )
         copy[i] = input[i];
  
     return copy;
 } 

 public static void main(String[] args) {
  
  int[] original = {22,55,66,11,32,56,67,89,95,10};
  
  int[] copyArray = copy( original );
  
  boolean result = Arrays.equals( original, copyArray );
  
  System.out.println( "Arrays are equal = "+result ); 

  System.out.print("\nOriginal Array = ");
  for( int i = 0; i< original.length; i++ )
       System.out.print( original[i]+" " );
  

  System.out.print("\nCopy Array = ");
  for (int i = 0; i < copyArray.length; i++)
    System.out.print(copyArray[i]+" ");
  
 }
}

Create a ArrayUtility.java file in your workspace.

When the main method inside the ArrayUtility class executed it is going to print :

Arrays are equal = true

Original Array = 22 55 66 11 32 56 67 89 95 10
Copy Array = 22 55 66 11 32 56 67 89 95 10

Recursive Binary Search Algorithm in Java

Binary Search is one of the most effective search algorithms used for searching a list of sorted items.

Known complexities for average, best and worst cases are considered as follows :

Worst case performance       =  O(log n)
Best case performance         =  O(1)
Average case performance   =  O(log n)

Following is the recursive implementation of binary search algorithm in Java.

package basics;

import java.util.Arrays;

public class RecursiveBinarySearch {

 public static int index( int[] input, int key )
 {
     return index( input, key, 0, input.length-1 );
 }
 
 public static int index( int[] input, int key, int low, int high )
 {
     if( low>high )
         return -1;
  
     int mid = low+(high-low)/2;
  
     if( key>input[mid] )
         return index(input, key, mid+1, high);
     else if( key<input[mid] )
         return index( input, key, low, mid-1 );
     else
         return mid;
 }
 
 public static void main(String[] args) {
  
  int[] list = {22,55,66,11,32,56,67,89,95,10};
  
  Arrays.sort(list);
  
  System.out.print("Sorted Array = ");
  for (int i = 0; i < list.length; i++) {
   System.out.print(list[i]+" ");
  }
  
  int itemIndex = index(list, 22);
  System.out.println("\n\nItem = "+22+", Index = "+itemIndex);
  
  itemIndex = index(list, 11);
  System.out.println("Item = "+11+", Index = "+itemIndex);
  
  itemIndex = index(list, 67);
  System.out.println("Item = "+67+", Index = "+itemIndex);
  
  itemIndex = index(list, 10);
  System.out.println("Item = "+10+", Index = "+itemIndex);

  itemIndex = index(list, 101);
  System.out.println("Item = "+101+", Index = "+itemIndex);
  
 }
}

Create a RecursiveBinarySearch.java file in your workspace.

When the main method inside the RecursiveBinarySearch class executed it is going to print :

Sorted Array = 10 11 22 32 55 56 66 67 89 95

Item = 22, Index = 2
Item = 11, Index = 1
Item = 67, Index = 7
Item = 10, Index = 0
Item = 101, Index = -1

Iterative Binary Search Algorithm in Java

Binary Search is one of the most effective search algorithms used for searching a list of sorted items.

Known complexities for average, best and worst cases are considered as follows :

Worst case performance       =  O(log n)
Best case performance          =  O(1)
Average case performance   =  O(log n)

Following is the iterative implementation of binary search algorithm in Java.

package basics;

import java.util.Arrays;

public class IterativeBinarySearch {
 
 public static int index( int[] input, int key )
 {
    int low = 0;
    int high = input.length-1;  
    while( low<=high )
    {
       int mid = low+(high-low)/2;
       if( key<input[mid] )
          high = mid-1;
       else if( key>input[mid] )
          low = mid+1;
       else
          return mid;
    }
    return -1;
 }
 
 public static void main(String[] args) {
  
  int[] list = {22,55,66,11,32,56,67,89,95,10};
  
  Arrays.sort(list);
  
  int itemIndex = index(list, 22);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 11);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 67);
  System.out.println(itemIndex);
  
  itemIndex = index(list, 10);
  System.out.println(itemIndex);

  itemIndex = index(list, 101);
  System.out.println(itemIndex);
 }
 
}

Create a IterativeBinarySearch.java file in your workspace.

When the main method inside the IterativeBinarySearch class executed it is going to print :

2
1
7
0
-1

Generic NonRecursive BottomUp Merge Sort in Java

MergeSort can also be implemented with a non-recursive bottom-up approach.

Non-recursive bottom-up merge-sort runs in O(nlogn) time as recursive version does.

It is considered a bit faster than recursive merge-sort in practice because it does not make recursive-calls.

There is a detailed description about this implementation at here.

package interviewquestions;

import java.util.Comparator;

public class MergeSortRoutine {

 public static <K> void merge(K[] in, K[] out, Comparator<K> comp, int start, int inc) {

  int end1 = Math.min(start + inc, in.length);
  int end2 = Math.min(start + 2 * inc, in.length);
  int x = start;
  int y = start + inc;
  int z = start;
  
  while (x < end1 && y < end2)
   if (comp.compare(in[x], in[y]) < 0)
    out[z++] = in[x++];
   else
    out[z++] = in[y++];
  
  if (x < end1)
   System.arraycopy(in, x, out, z, end1 - x);
  else if (y < end2)
   System.arraycopy(in, y, out, z, end2 - y);
 }

 public static <K> void mergeSortBottomUp(K[] orig, Comparator<K> comp) {
  
  int n = orig.length;
  K[] src = orig;
  K[] dest = (K[]) new Object[n];
  K[] temp;
  for (int i = 1; i < n; i *= 2) { 
   
   for (int j = 0; j < n; j += 2 * i)
    merge(src, dest, comp, j, i);
   
   temp = src;
   src = dest;
   dest = temp;
  }
  if (orig != src)
   System.arraycopy(src, 0, orig, 0, n);
 }

 private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
  public int compare(T a, T b) {
   return a.compareTo(b);
  }
 }

 public static void main(String[] args) {

  Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };

  System.out.println("Before sorting integer array with generic mergesort ");
  for (int i = 0; i < inputArr.length; i++) {
   System.out.print(inputArr[i] + " ");
  }

  mergeSortBottomUp(inputArr, new IntComparator<Integer>());

  System.out.println("\nAfter sorting integer array with generic mergesort ");
  for (int i = 0; i < inputArr.length; i++) {
   System.out.print(inputArr[i] + " ");
  }

  String[] values = { "asd", "basd", "cwe", "awe", "vasd" };

  System.out.println("\n\nBefore sorting String array with generic mergesort ");
  for (int i = 0; i < values.length; i++) {
   System.out.print(values[i] + " ");
  }

  mergeSortBottomUp(values, new IntComparator<String>());

  System.out.println("\nAfter sorting String array with generic mergesort ");
  for (int i = 0; i < values.length; i++) {
   System.out.print(values[i] + " ");
  }
  
 }
}

Above Non-recursive bottom-up Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSortBottomUp method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd

Generic Recursive Merge Sort in Java

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. 

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Merge sort animation. The sorted elements are represented by dots.

package interviewquestions;

import java.util.Arrays;
import java.util.Comparator;

public class MergeSortRoutine {

   public static <K> void merge(K[] S1, K[] S2, K[] S, Comparator<K> comp) {

     int i = 0, j = 0;
     while (i + j < S.length) {
         if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0))
            S[i + j] = S1[i++]; 
         else
            S[i + j] = S2[j++]; 
     }

   }

   public static <K> void mergeSort(K[] S, Comparator<K> comp) {

     int n = S.length;
     if (n < 2)
        return; 

     int mid = n / 2;
     K[] S1 = Arrays.copyOfRange(S, 0, mid); 
     K[] S2 = Arrays.copyOfRange(S, mid, n);

     mergeSort(S1, comp); 
     mergeSort(S2, comp);

     merge(S1, S2, S, comp);
   }

   private static class IntComparator<T extends Comparable<T>> implements Comparator<T> {
     public int compare(T a, T b) {
      return a.compareTo(b);
     } 
   }

   public static void main(String[] args) {

     Integer[] inputArr = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };  
  
     System.out.println("Before sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
    
     mergeSort( inputArr, new IntComparator<Integer>() );
  
     System.out.println("\nAfter sorting integer array with generic mergesort ");
     for (int i = 0; i < inputArr.length; i++) {
       System.out.print(inputArr[i]+" ");
     }
  
     String[] values = { "asd","basd","cwe", "awe", "vasd" };
  
     System.out.println("\n\nBefore sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
  
     mergeSort(values, new IntComparator<String>());
  
     System.out.println("\nAfter sorting String array with generic mergesort ");
     for (int i = 0; i < values.length; i++) {
       System.out.print(values[i]+" ");
     }
   }
}

Above Mergesort works for types that implements Comparable interface. Generic Comparator class instace is passed as a parameter to the generic mergeSort method.

Create a MergeSortRoutine.java file in your workspace.

When the main method inside the MergeSortRoutine class executed it is going to print :

Before sorting integer array with generic mergesort
45 23 11 89 77 98 4 28 65 43
After sorting integer array with generic mergesort
4 11 23 28 43 45 65 77 89 98

Before sorting String array with generic mergesort
asd basd cwe awe vasd
After sorting String array with generic mergesort
asd awe basd cwe vasd