home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / javafile / ch02 / Sort.java < prev    next >
Encoding:
Java Source  |  1998-12-14  |  3.0 KB  |  111 lines
  1. import java.io.*;
  2.  
  3. /*
  4.  * Sort.class reads a text file specified by args[0] and
  5.  * sorts each line for display
  6.  */
  7. class Sort {
  8.  
  9. static final int NMaxLines = 128;    // an arbitrary limit
  10.  
  11. public static void main (String args[]) {
  12. /*
  13.  * Allocate new array of strings; this is where the file
  14.  * is read and sorted in place
  15.  */
  16.        String sortArray[] = new String [NMaxLines];
  17.        FileInputStream fs=null;
  18.        int nlines;
  19.  
  20.        if (args.length != 1) {
  21.                System.out.println ("usage: java Sort <file>");
  22.                System.exit (1);
  23.         }
  24.         try {
  25.                fs = new FileInputStream (args[0]);
  26.         } catch (Exception e) {
  27.                System.out.println ("Unable to open "+args[0]);
  28.                System.exit (1);
  29.         }
  30.       
  31.        BufferedReader ds = new BufferedReader(new InputStreamReader(fs));
  32.  
  33.         for (nlines=0; nlines<NMaxLines; nlines += 1) {
  34.                try {
  35.                       sortArray[nlines] = ds.readLine ();
  36.                       if (sortArray[nlines] == null) break;
  37.                } catch (IOException e) {
  38.                       System.out.println("Exception caught during read."); 
  39. break;
  40.                }
  41.         }
  42.         try {
  43.                fs.close ();
  44.         } catch (IOException e) {
  45.                System.out.println ("Exception caught closing file."); 
  46. }
  47.  
  48. /*
  49.  * Sort in place and print
  50.  */     
  51.         QSort qsort = new QSort ();
  52.         qsort.sort (sortArray, nlines);
  53.         print (sortArray, nlines);
  54. }
  55.  
  56. /*
  57.  * print method prints an array of strings of n elements
  58.  *      String a[]    array of strings to print
  59.  *      int n         number of elements
  60.  */
  61. private static void print (String a[], int n) {
  62.         int i;
  63.         
  64.         for (i=0; i<n; i+=1) System.out.println (a[i]);
  65.         System.out.println ("");
  66. }
  67. }
  68.  
  69. /*
  70.  * QSort.class uses the standard quicksort algorithm
  71.  * Detailed explanation of the techniques are found in online help
  72. */
  73. class QSort {
  74.  
  75. /*
  76.  * This is used internally, so make it private
  77.  */
  78. private void sort (String a[], int lo0, int hi0) {
  79.         int lo = lo0;
  80.         int hi = hi0;
  81.  
  82.         if (lo >= hi) return;
  83.         String mid = a[(lo + hi) / 2];
  84.         while (lo < hi) {
  85.                while (lo<hi && a[lo].compareTo (mid) < 0) lo += 1;
  86. while (lo<hi && a[hi].compareTo (mid) > 0) hi -= 1;
  87. if (lo < hi) {
  88.                       String T = a[lo];
  89.                       a[lo] = a[hi];
  90.                       a[hi] = T; 
  91.                }
  92.         }
  93.         if (hi < lo) {
  94.                int T = hi;
  95.                hi = lo;
  96.                lo = T;
  97.         }
  98.         sort(a, lo0, lo);    // Yes, it is recursive
  99.         sort(a, lo == lo0 ? lo+1 : lo, hi0); 
  100. }
  101.  
  102. /*
  103.  * The method called to start the sort
  104.  *    String a[]    an array of strings to be sorted in place
  105.  *    int n        the number of elements in the array
  106.  */
  107. public void sort (String a[], int n) {
  108.        sort (a, 0, n-1);
  109. }
  110. }
  111.