Collections – sorting and searching

Sorting

In order to sort a Collection, one should use java.util.Collections class as follows (assuming ArrayList will be used):

List<String≫ words = new ArrayList<String>();
... //populate list of words 
Collections.sort(words);

It’s similar with arrays of objects.

In the above mentioned example the List contained obects of String type. Shall an own object type be used, special rules of sorting must be defined with Comparable or Comparator interfaces.

java.lang.Comparable

  • used to sort:
    • a Listjava.util.Collections.sort(A_COLLECTION)
    • an array of objects – java.util.Arrays.sort(AN_ARRAY)
  • MyClass needs to implement public int compareTo(MyClass o) method, which returns:
    • negative value – this object < another object
    • 0 – this object == another object
    • positive value – this object > another object
  • the drawback: there’s only one way of sorting

Example of the class implementing Comparable interface:

class Book implements Comparable<Book> {
    private String title;
    
    public String getTitle() {
        return title;
    }

    public void setTitle(String title_p) {
        title = title_p;
    }

    public int compareTo(Book o) {
        return this.title.compareTo(o.getTitle());
    }
}

java.util.Comparator

  • used to sort:
    • a Listjava.util.Collections.sort(A_COLLECTION, Comparator)
    • an array of objects – java.util.Arrays.sort(AN_ARRAY, Comparator)
  • a special class that implements java.util.Comparator interface needs to be created; this class defines public int compare(MyClass o1, MyClass o2) method (only one), which returns:
    • negative value – this object < another object
    • 0 – this object == another object
    • positive value – this object > another object
  • allows many one ways of sorting
  • allows to sort even those class that can’t be modified

Example of the class implementing Comparator interface:

class NameSort implements Comparator {
    public int compare(Book book1, Book book2) {
        return book1.getTitle().compareTo(book2.getTitle());
    }
}

Searching

  • In order to search in a Collection or an array of objects, they must be sorted:

    Arrays.sort(anArray);
    Arrays.binarySearch(anArray, "string_to_search");
    

    or

    Arrays.sort(anArray, aComparator);
    Arrays.binarySearch(anArray, "string_to_search", aComparator);
  • when search succeeds, the index of the serched element is returned
  • when search fails, insertionPoint is returned: -(insertion point) - 1 (if the element should be placed as a firston, so at 0 index, the returned value is -1)

0 Responses to “Collections – sorting and searching”


  • No Comments

Leave a Reply