CD List 2 - Sorted and Printed

  Download Source Code

/**************************************************
After adding more CD titles, Joe decided he would like to see
an alphabetical (sorted) list of the titles, so he could browse
through looking for favorite CDs, rather than typing titles.
Now the program starts by sorting and printing the array,
and then inputs search requests. In the real program,
he has a lot more titles.
***************************************************/

public class CDlistSorted
{
  String[] titles = {"Cafe del Mar 18",
    "Valtari",
    "Nature One",
    "Swagg",
    "Netsky 2",
    "DJ Kicks",
    "Trouble"
  };
  
  public CDlistSorted()
  {
    sortList();
    printList();
    String name = "";
    do
    {
      name = input("Type the name of the CD");
      search(name);
    } while(name.length() > 0);   // type nothing to quit
  }
  
  void sortList()   // an ineffient BubbleSort algorithm
  {
    for(int pass = 0; pass < titles.length; pass = pass + 1)
    {
      for(int x = 0; x < titles.length-1; x = x+1)
      {
        if(titles[x].compareTo(titles[x+1]) > 0)
        {
          String first = titles[x];     // swapping neighbors
          String second = titles[x+1];
          titles[x] = second;
          titles[x+1] = first;
        }       
      }
    }
  }
  
  void printList()
  {
    for(int c = 0; c < titles.length; c=c+1)
    {
      System.out.println(titles[c]);
    } 
    System.out.println("========");
  }

  void search(String name)
  {
    for(int c = 0; c < titles.length; c=c+1)
    {
      if( titles[c].equals(name) )
      {
        output("Found " + name);
        return;                   // quits if name is found
      }  
    }
    output("Not found - you don't own that"); 
  }
  
  public static void main(String[] args)
  {  new CDlistSorted();  }
  
  public String input(String prompt)
  { return javax.swing.JOptionPane.showInputDialog(null,prompt); }
  
  public void output(String message)
  {  javax.swing.JOptionPane.showMessageDialog(null,message);  }
}
Cafe del Mar 18
DJ Kicks
Nature One
Netsky 2
Swagg
Trouble
Valtari
========

Sorting into Alphabetical Order

This program prints out a list of ALL the CD titles owned by the user. 
As he adds more and more titles, the list could get quite long and difficult to read. 
Printing the titles in alphabetical order is more convenient.

The method sortList moves the entries around in the array to put them in alphabetical order.
To do this, it must compare 2 titles to see which is alphabetically before the other. 
This is done by .compareTo.

    if( titles[x].compareTo( titles[x+1] ) > 0 )
    { .. then swap the names in locations x and x+1 .. }

The compareTo method return +1 if  titles[x] is "greater than" titles[x+1].
It returns 0 if the two Strings are equal.
It returns -1 if the first String [x] is "less than" [x+1].
So if the result is greater than 0, the two Strings are in the wrong order
and must be "swapped" (exchanged).

Bubble Sort Algorithm

The program must do lots of comparisons and swaps to get everything in the right order,
especially if the list is quite long.  This requires a systematic algorithm for deciding which Strings
to compare to which, and what to do first, second, etc.

A Bubble Sort algorithm is quite simple to write and simple to understand. 
Start by comparing the first two Strings, [0] and [1], and swap them if they are out of order.
Now compare items [1] and [2] and swap if necessary.  Then compare [2] and [3].
Continue to the end of the list, comparing [titles.length-2] to [titles.length - 1].

That is a lot of work, but it is still not finished.  For example, if "Abba" is in position 6,
it will only move ahead 1 position during this process.  So we need to do it again -
go through the entire list comparing neighbors and swapping them again. 
Then go through the entire list again.  How many times?

The "worst-case scenario" is when "Abba" starts out at the very end of the list.
It moves ahead one position in each "pass", so it is necessary to make list.length-1 passes
to ensure that the worst case is taken care of.

So here is the algorithm for a Bubble Sort:

This requires two nested loops, like this:

loop for PASSES from 1 to N-1
   loop for POSITION from 0 to N-2
       compare item[POSITION] and item[POSITION+1],
         then swap if they are out of order
   end loop
end loop

Efficiency

The simple Bubble Sort described above requires a total of (N-1)*(N-1) comparisons,
When N is a large number (say 1 million) this is very close to N*N, or Nē . 
That is a lot of iterations (steps).  It's good if this can be a bit faster.

One way to improve efficiency is to notice that, after the first pass, the LAST item must
already be in the correct position.  So there is no point in examining it again.
After 2 passes, the last 2 items are already correctly placed.  In general, pass X does not
need to examine the last X-1 items.  So the inner loop could better be written as:

    loop for POSITION from 0 to N-1-PASSES

Then the last PASS only examines the first 2 items, #0 and #1, and then quits.
This makes the whole process twice as fast.

An even better improvement can be achieved by realizing that, if the list starts out sorted,
then it should only take 1 pass to confirm that it is in order.  And if a new item is added at
the beginning of a sorted list, it will be correctly placed after 1 pass.  This is a bit tricky
to program, but it's possible.

For now, a simple inefficient Bubble Sort is adequate for our needs.

Programming Practice