Sorting Asciibetically

[Lexy Yang]

How do you sort strings asciibetically?

[Pondurai Singh]

Example program Sort an array of ASCII strings into ascending order
Reference: oreilly.com/9781565923713/

// Copyright (c) 1997 by David Flanagan
// These are some classes we need for internationalized string sorting
import java.text.Collator; 
import java.text.CollationKey;
import java.util.Locale;

/**
 * This class defines a bunch of static methods for efficiently sorting
 * arrays of Strings or other objects.  It also defines two interfaces that
 * provide two different ways of comparing objects to be sorted.
 **/
public class Sorter {
  /**
   * This interface defines the compare() method used to compare two objects.
   * To sort objects of a given type, you must provide an appropriate Comparer
   * object with a compare() method that orders those objects as desired
   **/
  public static interface Comparer {
    /**
     * Compare objects and return a value that indicates their relative order:
     * if (a > b) return > 0; 
     * if (a == b) return 0;
     * if (a < b) return < 0. 
     **/
    public int compare(Object a, Object b);
  }

  /**
   * This is an alternative interface that can be used to order objects.  If a
   * class implements this Comparable interface, then any two instances of that
   * class can be directly compared by invoking the compareTo() method.
   **/
  public static interface Comparable {
    /** 
     * Compare objects and return a value that indicates their relative order:
     * if (this > other) return > 0
     * if (this == other) return 0
     * if (this < other) return < 0
     **/
    public int compareTo(Object other);
  }

  /**
   * This is an internal Comparer object (created with an anonymous class)
   * that compares two ASCII strings.  
   * It is used in the sortAscii methods below.
   **/
  private static Comparer ascii_comparer = new Comparer() {
    public int compare(Object a, Object b) {
      return ((String)a).compareTo((String)b);
    }
  };

  /**
   * This is another internal Comparer object.  It is used to compare two
   * Comparable objects.  It is used by the sort() methods below that take
   * Comparable objects as arguments instead of arbitrary objects
   */
  private static Comparer comparable_comparer = new Comparer() {
    public int compare(Object a, Object b) {
      return ((Comparable)a).compareTo(b);
    }
  };

  /** Sort an array of ASCII strings into ascending order */
  public static void sortAscii(String[] a) {
    // Note use of the ascii_comparer object
    sort(a, null, 0, a.length-1, true, ascii_comparer); 
  }

  /** 
   * Sort a portion of an array of ASCII strings into ascending or descending
   * order, depending on the argument up
   **/
  public static void sortAscii(String[] a, int from, int to, boolean up) {
    // Note use of the ascii_comparer object
    sort(a, null, from, to, up, ascii_comparer);
  }

  /** Sort an array of ASCII strings into ascending order, ignoring case */
  public static void sortAsciiIgnoreCase(String[] a) {
    sortAsciiIgnoreCase(a, 0, a.length-1, true);
  }

  /**
   * Sort an portion of an array of ASCII strings, ignoring case.  Sort into
   * ascending order if up is true, otherwise sort into descending order.
   **/
  public static void sortAsciiIgnoreCase(String[] a, int from, int to,
                                         boolean up) {
    if ((a == null) || (a.length < 2)) return;
    // Create a secondary array of strings that contains lowercase versions
    // of all the specified strings. 
    String b[] = new String[a.length];
    for(int i = 0; i < a.length; i++) b[i] = a[i].toLowerCase();
    // Sort that secondary array, and rearrange the original array 
    // in exactly the same way, resulting in a case-insensitive sort.
    // Note the use of the ascii_comparer object
    sort(b, a, from, to, up, ascii_comparer);
  }

  /** 
   * Sort an array of strings into ascending order, using the correct
   * collation order for the default locale
   **/
  public static void sort(String[] a) {
    sort(a, 0, a.length-1, true, false, null);
  }

  /**
   * Sort a portion of an array of strings, using the collation order of
   * the default locale.   If up is true, sort ascending, otherwise, sort
   * descending.  If ignorecase is true, ignore the capitalization of letters
   **/
  public static void sort(String[] a, int from, int to, 
                          boolean up, boolean ignorecase) {
    sort(a, from, to, up, ignorecase, null);
  }

  /**
   * Sort a portion of an array of strings, using the collation order of
   * the specified locale.   If up is true, sort ascending, otherwise, sort
   * descending.  If ignorecase is true, ignore the capitalization of letters
   **/
  public static void sort(String[] a, int from, int to, 
                          boolean up, boolean ignorecase, 
                          Locale locale) {
    // Don't sort if we don't have to
    if ((a == null) || (a.length < 2)) return;

    // The java.text.Collator object does internationalized string compares
    // Create one for the specified, or the default locale.
    Collator c;
    if (locale == null) c = Collator.getInstance();
    else c = Collator.getInstance(locale);

    // Specify whether or not case should be taken into account in the sort.
    // Note: this option does not seem to work correctly in JDK 1.1.1
    // using the default American English locale.
    if (ignorecase) c.setStrength(Collator.SECONDARY);

    // Use the Collator object to create an array of CollationKey objects that
    // correspond to each of the strings.  
    // Comparing CollationKeys is much quicker than comparing Strings
    CollationKey[] b = new CollationKey[a.length];
    for(int i = 0; i < a.length; i++) b[i] = c.getCollationKey(a[i]);

    // Now define a Comparer object to compare collation keys, using an
    // anonymous class.
    Comparer comp =  new Comparer() {
      public int compare(Object a, Object b) {
        return ((CollationKey)a).compareTo((CollationKey)b);
      }
    };

    // Finally, sort the array of CollationKey objects, rearranging the 
    // original array of strings in exactly the same way.
    sort(b, a, from, to, up, comp);
  }

  /** Sort an array of Comparable objects into ascending order */
  public static void sort(Comparable[] a) {
    sort(a, null, 0, a.length-1, true);
  }

  /**
   * Sort a portion of an array of Comparable objects.  If up is true,
   * sort into ascending order, otherwise sort into descending order.
   **/
  public static void sort(Comparable[] a, int from, int to, boolean up) {
    sort(a, null, from, to, up, comparable_comparer);
  }

  /**
   * Sort a portion of array a of Comparable objects.  If up is true,
   * sort into ascending order, otherwise sort into descending order.
   * Re-arrange the array b in exactly the same way as a.
   **/
  public static void sort(Comparable[] a, Object[] b, 
                          int from, int to, boolean up) {
    sort(a, b, from, to, up, comparable_comparer);
  }

  /**
   * Sort an array of arbitrary objects into ascending order, using the 
   * comparison defined by the Comparer object c
   **/
  public static void sort(Object[] a, Comparer c) {
    sort(a, null, 0, a.length-1, true, c);
  }

  /**
   * Sort a portion of an array of objects, using the comparison defined by
   * the Comparer object c.  If up is true, sort into ascending order, 
   * otherwise sort into descending order.
   **/
  public static void sort(Object[] a, int from,int to, boolean up, Comparer c){
    sort(a, null, from, to, up, c);
  }
  
  /**
   * This is the main sort() routine.  It performs a quicksort on the elements
   * of array a between the element from and the element to.  The up argument
   * specifies whether the elements should be sorted into ascending (true) or
   * descending (false) order.  The Comparer argument c is used to perform
   * comparisons between elements of the array.  The elements of the array b
   * are reordered in exactly the same way as the elements of array a are.
   **/
  public static void sort(Object[] a, Object[] b, 
                          int from, int to, 
                          boolean up, Comparer c)
  {
    // If there is nothing to sort, return
    if ((a == null) || (a.length < 2)) return;

    // This is the basic quicksort algorithm, stripped of frills that can make
    // it faster but even more confusing than it already is.  You should
    // understand what the code does, but don't have to understand just 
    // why it is guaranteed to sort the array...
    // Note the use of the compare() method of the Comparer object.
    int i = from, j = to;
    Object center = a[(from + to) / 2];
    do {
      if (up) {  // an ascending sort
        while((i < to) && (c.compare(center, a[i]) > 0)) i++;
        while((j > from) && (c.compare(center, a[j]) < 0)) j--;
      } else {   // a descending sort
        while((i < to) && (c.compare(center, a[i]) < 0)) i++;
        while((j > from) && (c.compare(center, a[j]) > 0)) j--;
      }
      if (i < j) { 
        Object tmp = a[i];  a[i] = a[j];  a[j] = tmp;          // swap elements
        if (b != null) { tmp = b[i]; b[i] = b[j]; b[j] = tmp; }// swap b, too
      }
      if (i <= j) { i++; j--; }
    } while(i <= j);
    if (from < j) sort(a, b, from, j, up, c); // recursively sort the rest
    if (i < to) sort(a, b, i, to, up, c);
  }

  /**
   * This nested class defines a test program that demonstrates several
   * ways to use the Sorter class to sort ComplexNumber objects
   **/
  public static class Test {
    /**
     * This subclass of ComplexNumber implements the Comparable interface
     * and defines a compareTo() method for comparing complex numbers.
     * It compares numbers based on their magnitude.  I.e. on their distance
     * from the origin.
     **/
    static class SortableComplexNumber extends ComplexNumber 
                                implements Sorter.Comparable {
      public SortableComplexNumber(double x, double y) { super(x, y); }
      public int compareTo(Object other) {
        return sign(this.magnitude()-((ComplexNumber)other).magnitude());
      }
    }

    /** This is the test program.  It sorts complex numbers in various ways. */
    public static void main(String[] args) {
      // Define an array of SortableComplexNumber objects.  Initialize it
      // to contain random complex numbers.
      SortableComplexNumber[] a = new SortableComplexNumber[5];
      for(int i = 0; i < a.length; i++)
        a[i] = new SortableComplexNumber(Math.random()*10, Math.random()*10);

      // Now sort it using the SortableComplexNumber compareTo() method, which
      // sorts by magnitude, and print the results out.
      System.out.println("Sorted by magnitude:");
      Sorter.sort(a);
      for(int i = 0; i < a.length; i++) System.out.println(a[i]);

      // Sort the complex numbers again, using a Comparer object that
      // compares them based on the sum of their real and imaginary parts
      System.out.println("Sorted by sum of real and imaginary parts:");
      Sorter.sort(a, new Sorter.Comparer() {
        public int compare(Object a, Object b) {
          ComplexNumber i = (ComplexNumber)a, j = (ComplexNumber)b;
          return sign((i.real() + i.imaginary()) - 
                      (j.real() + j.imaginary()));
        }
      });
      for(int i = 0; i < a.length; i++) System.out.println(a[i]);

      // Sort them again using a Comparer object that compares their real
      // parts, and then their imaginary parts
      System.out.println("Sorted descending by real part, then imaginary:");
      Sorter.sort(a, 0, a.length-1, false, new Sorter.Comparer() {
        public int compare(Object a, Object b) {
          ComplexNumber i = (ComplexNumber) a, j = (ComplexNumber) b;
          double result = i.real() - j.real();
          if (result == 0) result = i.imaginary() - j.imaginary();
          return sign(result);
        }
      });
      for(int i = 0; i < a.length; i++) System.out.println(a[i]);
    }

    /** This is a convenience routine used by comparison routines */
    public static int sign(double x) {
      if (x > 0) return 1;
      else if (x < 0) return -1;
      else return 0;
    }
  }
}

[Rob Spoor]

No offense, but I would never use anything from that code:
1) That Comparer interface is exactly the same as the old non-generic java.util.Comparator interface.
2) That Comparable interface is exactly the same as the old non-generic java.lang.Comparable interface.
3) That sorting functionality already exists in java.util.Arrays. To sort in reverse order, you can use one of the two reverseOrder methods in java.util.Collections.

[Campbell Ritchie]

Rob Spoor wrote: . . . To sort in reverse order, you can use one of the two reverseOrder methods in java.util.Collections.

Or you write a Comparator

import java.util.Comparator;

public final class ReverseStringComparator implements Comparator<String>
{
   public ReverseStringComparator()
   {
      super();
   }

   public int compare(String s1, String s2)
   {
      return s2.compareTo(s1);
   }
}

Now that is really complicated, isn’t it

[Rob Spoor]

That compare method is 100% identical to the implementation of reverseOrder(). That's also a singleton which makes it slightly more efficient - no matter how many times you call the method, only one object is created.

[Campbell Ritchie]

I hadn’t noticed that reverseOrder creates a Comparator rather than reversing the list