Sorting Phone numbers? no code just a questions

[.11]

I am working on an phone book class, and I have to have the Phone numbers, which have a name and address in an order list(linked).

But I have to sort by phone nnumber, not by name...I have been trying to think of ways to sort the phone numbers.

So far the only thing I have is sorting by ASCII values or if a number is longer than another(Area Codes).

So my question is, how would you go about sorting phone book, using only the phone numbers to sort by?

[BestJewSinceJC]

I think bucket sort or radix sort is supposed to be the best for that, but I don't remember the argument there, so look into it those topics.

[.11]

I think bucket sort or radix sort is supposed to be the best for that, but I don't remember the argument there, so look into it those topics.

I'll look into it, all I know is we have to test it with Circular Linked List and see how much faster it would by using and implementing binary search.

[thines01]

What if you just used the BigInteger.compareTo() and made your own sorter?

[BestJewSinceJC]

A binary search should eliminate half of the items each time a search is done. You can think of it similar to a dictionary. The way a binary search program would look up a word in the dictionary is it'd jump to the halfway point automatically. If the word there was greater than your word, then it knows your word is to the left of the word it is at, so it just eliminated half of the words. It continuous eliminating half of the words in this way until it finds the word it was looking for.

for more intuition to help you solve your problem, read this:
http://www.coders2020.com/can-we-do-a-binary-search-on-a-linked-list

edit: wait - were your instructors claiming that a doubly linked list implementation of a BST (which btw makes little sense to do) is better than a singly linked list implementation (which also makes little sense to do)? If so I claim that neither has any advantage over the other. Or were they saying something else?

[.11]

Thanks for the article on linked list binary I look into it.

thines01, I have to right my own compareTo method, which is where I wanted to add my Ascii comparing strategy, but it just seems inefficient.

[BestJewSinceJC]

Sorry, I just edited my post. Confirm the last part for me?

[.11]

Oh no, we are just writing an ordered linked list phone book, ordered by the phone numbers.(I just dont know how to go about sorted it by numbers. Like will "234-9873" go after "243-9000" and etc).

Well test of the search by number.

Then we implementing using binary search and test out the search to see if it is faster.

[thines01]

I'll scan back through the posts to make sure I'm on the right track, but...
Could you use something like this?

import java.util.Vector;
import java.util.Collections;

class TestSort
{
	public static void main(String[] args)
	{
		Vector<String> lst_strPhoneNums = new Vector<String>();
		lst_strPhoneNums.add(new String("9139119234"));
		lst_strPhoneNums.add(new String("8169110000"));
		lst_strPhoneNums.add(new String("4045519234"));

		///////////////////////////////
		System.out.println("Unsorted");
		for(String str : lst_strPhoneNums)
		{
			System.out.println(str);
		}

		//Do the sort
		Collections.sort(lst_strPhoneNums);


		///////////////////////////////
		System.out.println("\nSorted");
		for(String str : lst_strPhoneNums)
		{
			System.out.println(str);
		}
	}
}

[.11]

I'll scan back through the posts to make sure I'm on the right track, but...
Could you use something like this?

import java.util.Vector;
import java.util.Collections;

class TestSort
{
	public static void main(String[] args)
	{
		Vector<String> lst_strPhoneNums = new Vector<String>();
		lst_strPhoneNums.add(new String("9139119234"));
		lst_strPhoneNums.add(new String("8169110000"));
		lst_strPhoneNums.add(new String("4045519234"));

		///////////////////////////////
		System.out.println("Unsorted");
		for(String str : lst_strPhoneNums)
		{
			System.out.println(str);
		}

		//Do the sort
		Collections.sort(lst_strPhoneNums);


		///////////////////////////////
		System.out.println("\nSorted");
		for(String str : lst_strPhoneNums)
		{
			System.out.println(str);
		}
	}
}

I wish =D, but no, we write our own methods and class. This is something I just threw together right now.

Needs a few modification, but in my LinkedL.java, I would have a add method like this:

public void add(Phone detail) 
	{
		Node temp = tail.getNext();
		Node toAdd;
		if(isEmpty() || temp.getPhoneData().compareTo(detail) == 0)
		{
			Node newFirst = new Node(detail, head);
			head = newFirst;
		}
		else
		{
			while(temp.getPhoneData().compareTo(detail) < 0 && temp.getNext() != null)
			{
				temp = temp.getNext();
			}
			
			if((temp.getNext() == null))
			{
				toAdd = new Node(detail, null);
				temp.setNext(toAdd);
			}
			else
			{
				toAdd = new Node(detail, temp.getNext());
				temp.setNext(toAdd);
			}
		}
}

then

public int compareTo(Phone details)
	{
		//Compares the phone numbers with this.getNumber() and details.getNumber()

               //Returns -1 if less than, or 0 if greater than or equal to
	}

[bigdognec]

Pretty old thread but as somebody pointed out try radix sort ... Its linear time algorithm (though not absolutely linear but better than nlogn all the same for a big enough number of items, in this case phone numbers). The argument is as follows:
No comparison algorithm can be less than nlogn but since number of digits in a phone number is fixed we can use a non comparison algorithm.
The last elements are first sorted using the least significant character first and then proceed one by one till the most significant one. wikipedia has some more info you can refer up : http://en.wikipedia.org/wiki/Radix_sort

But it always isnt better. The constants depend on number of characters and that may turn out to be less efficient than binary sort at times especially when the number of elements to be sorted is less