dcsimg
October 1, 2016
Hot Topics:

Working with Searching and Sorting APIs in Java

  • December 29, 2014
  • By Manoj Debnath
  • Send Email »
  • More Articles »

Although C/C++ provides the tools and support to make a module as efficient as it can be, Java literally provides some of the frequently required: efficient, ready to use modules in the form of a collection framework. These modules not only make the life of a programmer easy, but also saves the valuable time of rewriting common algorithms and tuning them for efficiency over time. Collection API developers of Java fine tuned them on behalf of all and brought a sense of oneness with the core APIs of Java. The article tries to explore some specific aspects of searching and sorting APIs found in the Java library.

The Algorithm APIs

Searching and sorting algorithms are perhaps the most used and much needed algorithms overtly exploited by developers for almost any type of development, from applications to systems to database and so forth. The collection framework in Java is replenished with several high-performance algorithms for manipulating collection elements. These polymorphic algorithms that operate on collection wrappers are implemented as static methods so that they can operate on or return collection without having to create class objects; in other words, they are class methods and can be called by class names. The algorithms are polymorphic in the sense that regardless of underlying implementation, they can operate on objects that implement specific interfaces. There are diverse lists of algorithms in the API library; common among them are sort, binarySearch, reverse, shuffle, fill, and copy that operate on List(s), whereas algorithms such as min, max, addAll, frequency, and disjoint operate on Collection(s). We shall try to delineate the intricacies rather than visit each of them with examples.

Sorting Algorithm

A sorting algorithm arranges the elements of a List in a particular order. The elements in the List must implement the Comparable interface and the order is determined by the compareTo() method called as a natural comparison method, declared in the Comparable interface. However, we always can specify an alternate ordering of the elements with the help of the Comparator object passed as an argument to the sort method. For example, if we want to sort the following:

private static final String colors[] = { "red", "green",
    "blue","magenta", "cyan", "purple", "brown" };

we can write the code as shown below.

List<String> list=Arrays.asList(colors);
Collections.sort(list);

And, for numbers such as the following, we can write it as follows,

private static final Integer[]
   nos={45,23,16,89,22,59,23,78,345};
List<Integer> list2=Arrays.asList(nos);
Collections.sort(list2,
   Collections.reverseOrder());

The Comparator argument passed as reverseOrder() signifies that the sorting be done in descending order. Observe, in the Javadoc that both String and Integer implements a Comparable interface. So, unless a class implements the Comparable interface and defines the abstract compareTo() method, sorting cannot be applied from collection framework.

The next example illustrates how a simple custom comparator class can be used for sorting.

public class CustomComparator implements Comparator<Integer> {
   @Override
   public int compare(Integer num1, Integer num2) {
      return num1-num2;
   }
}

public class CustomComparatorSort {

   private static final List<Integer> list =
      new ArrayList<Integer>();

   public static void main(String[] args) {
      Random r = new Random();
      for (int i = 0; i < 10; i++)
         list.add(new Integer(r.nextInt(99)));

      printlist("Unsorted list");
      Collections.sort(list, new CustomComparator());
      printlist("Sorted list");

   }

   public static void printlist(String s) {
      System.out.println(s);
      for (Integer i : list) {
         System.out.print(" " + i);
      }
      System.out.println();
   }
}

The type of sorting algorithm, used internally by the sort method, is a variation of an efficient mergesort.

[Excerpt from Javadoc]

"...iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays...

"The implementation was adapted from Tim Peters's list sort for Python (TimSort)..."

Searching Algorithm

A binary search is a very efficient searching algorithm, but it requires that the array of elements be sorted.

[Excerpt from Javadoc]

"...The list must be sorted into ascending order according to the specified comparator (as by the sort (List, Comparator) method), prior to making this call. If it is not sorted, the results are undefined..."

Built into the Java collection framework as a static method of class Collections, this algorithm locates an object in a List (LinkedList, Vector, ArrayList), and when the object is found, its index is returned; otherwise, a negative value is returned. The negative value is determined by calculating the insertion point and making its sign negative. To ensure that the search method returns positive numbers (>=0) when the object is found, 1 is subtracted from the insertion point to obtain the return value. In case there is a multiple element matched with the search key, there is no guarantee which one will be located first.

public class BinarySearchDemo {

   private static final String languages[] = { "english", "spanish",
      "french","mandarin", "sanskrit", "Urdu", "Latin" };

   private static final List<String> list = new ArrayList<>(
      Arrays.asList(languages));

   public static void main(String[] args) {
      Collections.sort(list);
      search("sanskrit");
      search("pali");
   }

   public static void search(String key) {
      System.out.println("\nSearching for " + key);
      int result = Collections.binarySearch(list, key);
      if (result >= 0)
         System.out.print(" Found at index " + result);
      else
         System.out.print(" Not found [" + result + "]");
   }
}

Conclusion

The usage of algorithms defined in the Collections are pretty straightforward. Other algorithms, such as shuffle, fill, and copy operate on Lists, whereas min and max operate on Collections. Fill is is used to set every List element to a specified Object, and copy copies elements from one List into another. To append an array of elements to a collection, we can use the addAll method, frequency finds out the number of times a specified element is found in a collection, and disjoint determines whether two collections have elements in common. The implementation of the Java collection framework is quite stable and, unless required for a very specific purpose, these algorithms from the core Java API should be used rather than reinventing the wheel when programming.


Tags: Java, search algorithms, sort, Java APIs




Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date
Rocket Fuel