Guide to Algorithms used in Java Library

In this guide, we will learn what are the algorithms used in Java built-in classes like Arrays and Collections.
Let's discuss the usage of most commonly used Java built-in Utility classes are Arrays and Collections.

The polymorphic algorithms described here are pieces of reusable functionality provided by the Java platform. All of them come from the Arrays and Collections class, and all take the form of static methods whose first argument is the array or collection on which the operation is to be performed.
The great majority of the algorithms provided by the Java platform operate on List instances, but a few of them operate on arbitrary Collection instances.

I would like to describe the following algorithms:
  • Sorting
  • Shuffling
  • Routine Data Manipulation
  • Searching
  • Composition
  • Finding Extreme Values
Let's sort the elements in either in ascending order or descending order.

Arrays Utility Class

Java provides Arrays utility class is very helpful for sorting array elements in ascending and descending order. This class also contains a static factory method that allows arrays to be viewed as lists.
JDK provides this utility class contains various methods for manipulating arrays (such as sorting and searching).

You can refer this link to know more API of Arrays Utility class.
A complete example to a demonstration of Arrays Utility Class
import java.util.Arrays;
import java.util.Date;
import java.util.List;

public class AlgorithmsDemo {
    public static void main(String[] args) {
       sortArrayOfPrimitives();
       sortArrayOfString();
       convertArrayToList();
       binarySerachAlgorithm();
 }

 private static void binarySerachAlgorithm() {
     final String key = "abc";
     String[] strArray = { "abc", "cdf", "pqr" };
     Arrays.binarySearch(strArray, key);
     int[] intArray = { 1, 2, 3, 4 };
     Arrays.binarySearch(intArray, 3);

     byte k = 1;
     byte[] byteArray = { 1, 2, 3, 4, 5 };
     Arrays.binarySearch(byteArray, k);

     char charKey = 'a';
     char[] charArray = { 'a', 'b', 'c' };
     Arrays.binarySearch(charArray, charKey);

     double[] doubleArray = { 0.1, 0.2, 0.3 };
     Arrays.binarySearch(doubleArray, 0.2);

     long[] longArray = { 1, 2, 3, 4, 5 };
     Arrays.binarySearch(longArray, 1);

     float[] floatArray = { 1, 2, 3, 4, 5 };
     Arrays.binarySearch(floatArray, 2);
 }

 // Convert array to list
 private static void convertArrayToList() {
     List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
     for (String str : stooges) {
         System.out.println(" print list ----" + str);
     }
 }

 // Sort array of primitive elements
 private static void sortArrayOfPrimitives() {
     int[] intArray = { 1, 2, 3, 4 };
     Arrays.sort(intArray);

     byte[] byteArray = { 1, 2, 3, 4, 5 };
     Arrays.sort(byteArray);

     char[] charArray = { 'a', 'b', 'c' };
     Arrays.sort(byteArray);

     double[] doubleArray = { 0.1, 0.2, 0.3 };
     Arrays.sort(doubleArray);

     long[] longArray = { 1, 2, 3, 4, 5 };
     Arrays.sort(longArray);

     float[] floatArray = { 1, 2, 3, 4, 5 };
     Arrays.sort(floatArray);
 }

 // Sort array of string elements
 private static void sortArrayOfString() {
    // String internally implements Comparable interface.
     String[] strArray = { "abc", "cdf", "pqr" };
     Arrays.sort(strArray);
     // Date internally implements Comparable interface
     Date[] dates = { new Date("08-26-2016"), new Date("08-27-2016") };
  }
}

Collections Utility class

Key points about Collections Utility class.
  • This class is a member of the Java Collections Framework.
  • All elements in the list must implement the Comparable interface. Furthermore, all elements in the list must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the list).
  • This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
  • The specified list must be modifiable, but need not be resizable.
  • It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends. 
  • We can sort the elements in descending order using - Collections.sort(projects, Collections.reverseOrder());
You can refer this link to know more API of Collections Utility class. https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html
A complete example to a demonstration of the Collections Utility Class
Example: Sorts the specified list into ascending order, according to the natural ordering of its elements.
import java.util.Collections;
import java.util.LinkedList;

public class CollectionsDemo {

 public static void main(String[] args) {
     listSortingAlgorithmsDemo();
 }

 private static void listSortingAlgorithmsDemo() {
     LinkedList<String> list = new LinkedList<>();
     list.add("element 2");
     list.add("element 1");
     list.add("element 4");
     list.add("element 3");
     // Sorts the specified list into ascending order, according to
     // the natural ordering of its elements.
     Collections.sort(list);
     for (String str : list) {
       System.out.println(" sort elements in ascending order  --" + str);
     }
   }
}
Sorting list of Custom Objects in ascending and descending Order
Java provides two interfaces to sort objects using data members of the class:
Java Comparable interface is used to order the objects of a user-defined class. This interface is found in java.lang package and contains only one method named compareTo(provides. It provides single sorting sequence only i.e. you can sort the elements on based on single data member only. public int compareTo(Object obj): is used to compare the current object with the specified object. We can sort the elements of:
  • String objects
  • Wrapper class objects
  • User-defined class objects
Java Comparator interface is used to sort the objects of a user-defined class. Collections class provides static methods for sorting the elements of a collection. Method of Collections class for sorting List elements public void sort(List list, Comparator c): is used to sort the elements of List by the given Comparator. Example :
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class AlgorithmsDemo {
    public static void main(String[] args) {
     // sortingCustomObjectsByComparable();
     sortingCustomObjectsByComparator();
 }

 private static void sortingCustomObjectsByComparable() {
  // Sort Projects by project id in ascending order.
     List projects = new ArrayList<>();
     Project project = new Project();
     project.setProjectId(100);
     project.setProjectName("project 100");
     projects.add(project);

     Project project2 = new Project();
     project2.setProjectId(200);
     project2.setProjectName("project 200");
     projects.add(project2);

     Project project3 = new Project();
     project3.setProjectId(50);
     project3.setProjectName("project 50");
     projects.add(project3);
     Collections.sort(projects);
     printList(projects);
 }

 private static void sortingCustomObjectsByComparator()           
                 // Sort Projects by project id in ascending order.                 
                 List projects = new ArrayList<>();
                 Project project = new Project();
                 project.setProjectId(100);
                 project.setProjectName("project 100");
                 projects.add(project);
                 
                 Project project2 = new Project();
                 project2.setProjectId(200);
                 project2.setProjectName("project 200");
                 projects.add(project2);
                 Project project3 = new Project();
                 project3.setProjectId(50);
                 project3.setProjectName("project 50");
                 projects.add(project3);
                 
                 // Sorting project by project id in ascending order in Java
                 Collections.sort(projects);
                 printList(projects);
                 
                 // Sorting project by project id in descending order in Java
        Collections.sort(projects, Collections.reverseOrder());
        printList(projects);

        
     // Sorting project by project name in ascending order in Java
          Comparator comparator = new Comparator() {
               @Override
               public int compare(Project o1, Project o2) {
                   // TODO Auto-generated method stub
                   return o1.getProjectName().compareTo(o2.getProjectName());
               }
          };
           Collections.sort(projects, comparator);
           printList(projects);                 
         }

 private static void printList(List projects) {
  for (Project project : projects) {
   System.out.println(project.getProjectId());
   System.out.println(project.getProjectName());
  }
 }

}

class Project implements Comparable {
    private int projectId;
    private String projectName;

 public int getProjectId() {
    return projectId;
 }

 public void setProjectId(int projectId) {
    this.projectId = projectId;
 }

 public String getProjectName() {
    return projectName;
 }

 public void setProjectName(String projectName) {
     this.projectName = projectName;
 }

   @Override
   public int compareTo(Project o) {
    // TODO Auto-generated method stub
    return this.projectId - o.getProjectId();
  }
}

Shuffle

The shuffle algorithm does the opposite of what sort does, destroying any trace of order that may have been present in a List. That is, this algorithm reorders the List based on input from a source of randomness such that all possible permutations occur with equal likelihood, assuming a fair source of randomness.
Collections utility class provides the shuffling methods Example:
private static void shuffleAlgorithmsDemo() {
  List list = new LinkedList<>();
  list.add("element 2");
  list.add("element 1");
  list.add("element 4");
  list.add("element 3");

  Collections.sort(list);
  for (String str : list) {
   System.out.println(" sort elements in ascending order  --" + str);
  }

  // randomly permutes the elements in a List.
  Collections.shuffle(list);
  printMessage(list, "shuffle elements ");
 }

Routine Data Manipulation

The Collections class provides five algorithms for doing routine data manipulation on List objects, all of which are pretty straightforward: 
  • reverse - reverses the order of the elements in a List. 
  • fill - overwrites every element in a List with the specified value. This operation is useful for reinitializing a List. 
  • copy - takes two arguments, a destination List and a source List, and copies the elements of the source into the destination, overwriting its contents. The destination List must be at least as long as the source. If it is longer, the remaining elements in the destination List are unaffected. 
  • swap - swaps the elements at the specified positions in a List. 
  • addAll - adds all the specified elements to a Collection. The elements to be added may be specified individually or as an array.
Example:
private static void listAlgorithmsDemo(){      
         List list = new LinkedList<>();
         list.add("element 2");
         list.add("element 1");
         list.add("element 4");
         list.add("element 3");
                  // Sorts the specified list into ascending order, according to 
         //the natural ordering of its elements.
         // All elements in the list must implement the Comparable interface.
         // Furthermore, 
         //all elements in the list must be mutually 
         //comparable (that is, e1.compareTo(e2) 
         //must not throw a ClassCastException for any elements e1 and e2 in the list). 
         Collections.sort(list);
         for(String str : list){
                 System.out.println(" sort elements in ascending order  --" + str);
         }
         //reverses the order of the elements in a List.
         Collections.reverse(list);
         printMessage(list, "reverse  elements ");
         
         // rotates all the elements in a List by a specified distance.
         Collections.rotate(list, 1);
         printMessage(list, "rotate elements ");
         
         //swaps the elements at specified positions in a List.
         Collections.swap(list, 0, 1);
         printMessage(list, "swap elements ");
         
         //replaces all occurrences of one specified value with another.
         Collections.replaceAll(list, "element 3", "element 6");
         printMessage(list, "replaces all occurrences of one 
                        specified value with another "
                        specified value with another "
                        specified value with another ");
         
         List destList = new ArrayList<>();
         Collections.copy(destList, list);
         printMessage(destList, " copied elemets ");
}

private static void printMessage(List list, String message){
         for(String str : list){
                 System.out.println(message + " ---> " + str);       
         }
}

Searching

The binarySearch algorithm searches for a specified element in a sorted List. This algorithm has two forms. The first takes a List and an element to search for (the "search key"). This form assumes that the List is sorted in ascending order according to the natural ordering of its elements. The second form takes a Comparator in addition to the List and the search key, and assumes that the List is sorted into ascending order according to the specified Comparator. The sort algorithm can be used to sort the List prior to calling binarySearch. 
Example:
private static void searchingAlgorithmsDemo(){
         List list = new LinkedList<>();
         list.add("element 2");
         list.add("element 1");
         list.add("element 4");
         list.add("element 3");
         // Sorts the specified list into ascending order, according to the 
         // natural ordering of its elements.
         // All elements in the list must implement the Comparable interface.
         // Furthermore, 
         //all elements in the list must be mutually 
         //comparable (that is, e1.compareTo(e2) 
         //must not throw a ClassCastException for any elements e1 and e2 in the list). 
         Collections.sort(list);
         for(String str : list){
         System.out.println(" sort elements in ascending order  --" + str);
         }         
        // searches for an element in an ordered List using the binary search algorithm.
         Collections.binarySearch(list, "element 4"); 
}

Composition

The frequency and disjoint algorithms test some aspect of the composition of one or more Collections: 
  • frequency - counts the number of times the specified element occurs in the specified collection.
  • disjoint - determines whether two Collections are disjoint; that is, whether they contain no elements in common.
Example:
private static void compositionAlgorithmDemo(){
         List list = new LinkedList<>();
         list.add("element 2");
         list.add("element 1");
         list.add("element 1");
         list.add("element 3");
      //Returns the number of elements in the specified collection         
       //equal to the specified object.
         System.out.println(Collections.frequency(list, "element 1"));
         List list2 = new LinkedList<>();
         list2.add("element 2");
         list2.add("element 1");
         list2.add("element 1");
         list2.add("element 3");
         //Returns true if the two specified collections have no elements in common. 
         System.out.println(Collections.disjoint(list, list2));
}

Finding Extreme Values

The min and the max algorithms return, respectively, the minimum and maximum element contained in a specified Collection. Both of these operations come in two forms. The simple form takes only a Collection and returns the minimum (or maximum) element according to the elements' natural ordering. The second form takes a Comparator in addition to the Collection and returns the minimum (or maximum) element according to the specified Comparator. 
Example:
private static void findingExtremeValuesAlgorithm(){
         List list = new LinkedList();
         list.add(100);
         list.add(300);
         list.add(200);
         list.add(500);
         // Returns the minimum element of the given collection, 
         // according to the natural ordering of its elements.
         // All elements in the collection must implement the Comparable interface.
         System.out.println(Collections.min(list));
         //Returns the maximum element of the given collection,
         // according to the natural ordering of its elements. 
         //All elements in the collection must implement the Comparable interface. 
         System.out.println(Collections.max(list));
}


Comments