quicksort for simple phonebook program

[ShaneMcD]

Hi,

I'm doing a fairly basic Java course, and I have to design a very simple phone book programme which will take a small number of phone entries (the number can be predefined so I can use arrays instead of lists), sort them and allow them to be searched.

I'm just concentrating on the sorting part of the problem at the moment, and I'm not sure where to start! There's two ways I can approach it:

1) Create an array of objects, each object containing a variable for a Name and a Phone Number, and then use quicksort on the array to sort the objects. The problems with this (for me anyway, I'm sure this is really easy for you guys!) is that I'm not sure on (a) how to get the individual objects into the array in the first place and (b) how to use quicksort in this case so that the Name variable is used for sorting purposes.

2) Create a much simpler string array containing the names as Strings, and have a second array with the relevant Phone numbers in the corresponding index position. The problems with this approach is that while performing quicksort on the String array to move the names around, I don't know how to ensure that the corresponding telephone number in the second array also moves.

Any help or suggestions much appreciated!

Shane

[JosAH]

The Object Oriented way in Java is to implement the Comparable interface
in your PhoneEntry class; the String class also implements this interface, that's
why it is so easy to sort Strings.

If you absolutely don't want to do that, have a look at the Comparator interface,
it can compare two instantiations of a class and decide which one is larger etc.
Read the API documentation for those two interfaces.

Never, ever consider your alternative 2) it is considered a criminal offence to rip
objects apart and stick their remnants in separate arrays. Java is not Fortran
and such practice will be frowned upon.

There's also a 'generic heap sort' article in Java's Howtos section that may be
worth reading.

kind regards,

Jos

[sukatoa]

Hi,

I'm doing a fairly basic Java course, and I have to design a very simple phone book programme which will take a small number of phone entries (the number can be predefined so I can use arrays instead of lists), sort them and allow them to be searched.

I'm just concentrating on the sorting part of the problem at the moment, and I'm not sure where to start! There's two ways I can approach it:

1) Create an array of objects, each object containing a variable for a Name and a Phone Number, and then use quicksort on the array to sort the objects. The problems with this (for me anyway, I'm sure this is really easy for you guys!) is that I'm not sure on (a) how to get the individual objects into the array in the first place and (b) how to use quicksort in this case so that the Name variable is used for sorting purposes.

2) Create a much simpler string array containing the names as Strings, and have a second array with the relevant Phone numbers in the corresponding index position. The problems with this approach is that while performing quicksort on the String array to move the names around, I don't know how to ensure that the corresponding telephone number in the second array also moves.

Any help or suggestions much appreciated!

Shane

If you like it to have an experiment.

You could use #2 implementation... to avoid more confusions later....

As you add a name, you must also add the number in the same element...

x = 0;
myname = StringName[ x ];
mynumber = StringNumber[ x ];

When you search them, just use the element... 1 element represents 2 values... from arrays....

Since you are using quicksort, you should use 2 temp variables for storing name and number... for swapping values....

Jo's reply is good to implement.

sukatoa...

[Laharl]

#2 could be accomplished with a Map. A TreeMap would even store the Strings in (effectively) sorted order...Admittedly, this is more complicated than you probably want to deal with...

[JosAH]

#2 could be accomplished with a Map. A TreeMap would even store the Strings in (effectively) sorted order...Admittedly, this is more complicated than you probably want to deal with...

Sure, and what to do with two different people having the same name? That option
2) stinks no matter what trickery is applied.

kind regards,

Jos

[chaarmann]

Sure, and what to do with two different people having the same name? That option
2) stinks no matter what trickery is applied.
Jos

yes, it's bad practise. Don't separate data that should be together.Solution one is better than 2. But there is a third solution: easier than solution 1 (for a beginner), and in principle like solution 2:

create an array of Strings where each string represents one record. Separate the data inside a string with "|". You can use also another character for separation, but it must be smaller than "a" (= your lexicographically smallest character in the name), or the comparison will fail.
Example:

String[] array = {
  "police|119", 
  "name2|phone2",
   ...
}
 
// Now sort array. This works, because String class already implements Comparable interface
Arrays.sort(array);
 
// print out array:
System.out.println(Arrays.asList(array));

[JosAH]

yes, it's bad practise. Don't separate data that should be together.Solution one is better than 2. But there is a third solution: easier than solution 1 (for a beginner), and in principle like solution 2:

create an array of Strings where each string represents one record. Separate the data inside a string with "|". You can use also another character for separation, but it must be smaller than "a" (= your lexicographically smallest character in the name), or the comparison will fail.
Example:

String[] array = {
  "police|119", 
  "name2|phone2",
   ...
}
 
// Now sort array. This works, because String class already implements Comparable interface
Arrays.sort(array);
 
// print out array:
System.out.println(Arrays.asList(array));

That is just plain hacking; you have sorted a string representation of the original
objects but haven't sorted the objects themselves. That sort of hacking has brought
more misery than good in the past and it gives the IT branch a bad name. It is
worth nothing to do such things and beginners certainly shouldn't resort to that
trickery-dickery.

kind regards,

Jos

[ShaneMcD]

Thanks for the answers guys. So I think I'm going to go with the comparable method on option 1 so.

I've started my coding - and I'm having problems getting the my PhoneEntry objects into the array.

I've got a PhoneEntry class which looks like this so far:

class PhoneEntry 
{
 
//declare class variables
private static String person;
private static int phone;
 
//constructor
public PhoneEntry(String name, int number)
    {
    person = name;
    phone = number;
    }// end constructor
 
public static void print()
    {
    System.out.println("~ " + person + "  ~ " + phone);
    }//end print
 
 
}//end class
 

And I've got a main PhoneBook class in which I am trying to set up an array of 10 objects, and pre-define the data for each of the 10 entries. I'm then just trying to call the print method from the PhoneEntry class to confirm that each object is stored correctly and will print.

import java.util.*;
class PhoneBook 
{
    public static void main(String[] args) 
    {
        PhoneEntry[] book = new PhoneEntry[10]; //set up the array of PhoneEntry objects
 
        //hard-code 10 phone book entries
        book[0] = new PhoneEntry("Madsen Declan", 016271624);
        book[1] = new PhoneEntry("Madsen Eoin", 016275236);
        book[2] = new PhoneEntry("Courtney Shane", 016275364);
        book[3] = new PhoneEntry("Moran Tess", 016245327);
        book[4] = new PhoneEntry("Leydon Claire", 016271446);
        book[5] = new PhoneEntry("Crean Ruth", 016243354);
        book[6] = new PhoneEntry("Byrne Paul", 016243247);
        book[7] = new PhoneEntry("Hanafin Ruari", 016233214);
        book[8] = new PhoneEntry("Molloy John", 016274342);
        book[9] = new PhoneEntry("Farrell Peter", 016273636);
 
        for (int i = 0; i < book.length; i++)
            PhoneEntry.print();
 
    }//end main
}//end class
 

Both classes are compiling ok, but all I get printed is:

"~ Farrell Peter ~ 3766174" ten times.

Its clear that there's something wrong with the way I'm using my print method to try to print each individual entry, as it's just printing the last name 10 times. And I'm really puzzled by the number that its printing out beside the name, because as you can see from the data I'm using, none of the phone numbers matches this number so I don't know where it came from!

[JosAH]

How does the static method PhoneEntry.print() know what entry to print? It doesn't
take any parameters so I wonder if there's magic around here ...

kind regards,

Jos

[ShaneMcD]

Hmm, yes, I see what you're saying. I've tried a couple of parameters but I don't really know what I'm doing with that, so alternatively I tried to scrap the print method in PhoneEntry and instead changed the private variables in PhoneEntry to public, and created two variables in the PhoneBook class called

String name = PhoneEntry.person;
int number = PhoneEntry.phone;
 

...thinking that I'd be able to use these to get at the different name and number values, and print directly from the PhoneBook class instead of trying to call a print method from PhoneEntry:

for (int i = 0; i < book.length; i++)
    System.out.println("~ " + name + "  ~ " + number);
 

....didn't work though. Just got "~ null ~ 0" printed 10 times. *sigh*

[chaarmann]

You should read about static methods/variables (class-level) and nonstatic methods/variables (object-level). There is just one memory location for the "person" that is shared among all your instantiated objects, because you declared it "static". You are creating objects here, but you always overwrite your person and number of the previous old object. So when you call your print-method at the end, it just writes the data that you have given as parameters for your last created object.

If you wonder why it prints 3766174?
Because it's the same as the number 01624532, but it is not given in octal as you did (by accident), but decimal!
remember : the leading "0" in front of your number marks an octal system, while a leading "0x" in front of your number marks a hexadecimal system.
therefore 08 does not exist, you would get a compiler error!
For example 10 (decmal) = 012 (=1*8 + 2) (octal) = 0xA (hexadecmal)

if you want leading zeros, just give the number as a String. Or better: give the number without a zero in front, but use functions of class DecimalFormat to print it with leading zero at the end.

Both classes are compiling ok, but all I get printed is:

"~ Farrell Peter ~ 3766174" ten times.

Its clear that there's something wrong with the way I'm using my print method to try to print each individual entry, as it's just printing the last name 10 times. And I'm really puzzled by the number that its printing out beside the name, because as you can see from the data I'm using, none of the phone numbers matches this number so I don't know where it came from!

[chaarmann]

That is just plain hacking; you have sorted a string representation of the original
objects but haven't sorted the objects themselves. That sort of hacking has brought
more misery than good in the past and it gives the IT branch a bad name. It is
worth nothing to do such things and beginners certainly shouldn't resort to that
trickery-dickery.

kind regards,

Jos

Plain hacking, quick and dirty, is exactly what I wanted to provide. because it's easier to understand for beginners than dealing with Objects and Comparable interface. If he is a professional, of course I would never suggested that. I just wanted him to concentrate on his task, the "binary sort" algorithm. That's already difficult enough. Once he has mastered that, he can climb up the ladder from "procedural" to "object orientated" programming.
I have forseen that his teacher will tell him to use objects anyhow if he presents the "quick and dirty" solution. But then he will have a nice discussion and learn why this is better.
I mean he was considering solution 2 with the 2 separated string arrays, and you told him this is not good, but he really did not understand WHY it is not good. He can only get the experience from trying it the dirty way and then getting into big trouble when he adds more and more features to his program. (for example if the teacher says, now change your program so that it also can sort by phone number instead by only name). Then he can clearly understand why using the comparable-interface with objects is the best solution.

[JosAH]

Ok, it's your way then; I leave the poster up to you; the poster is all yours.
I only hop in now and then mumbling about generics and interfaces ;-)

kind regards,

Jos