need help with an alphabetizing algorithm

zskillz · March 18th, 2002, 12:08 PM

ok... here's the deal. (using java) I'm reading in a comma delimited file and creating an object from each line. The rules of the assignment are that I have to alphabetize the objects and put them in a linked list as I'm reading them in. I'm having a hell of a time with this. I can get it so that all of the A's, B's, etc are together, but I cannot get them to be alphabetized within their respective areas. Can anyone offer me some help with this problem. it's annoying as heck. I think that I could use a recursive method, but I was hoping to speed up runtime by avoiding a bunch of method calls and instead just using some sort of while loops or something.

thanks all
-Z

**Whir** · March 18th, 2002, 01:20 PM

Do you HAVE to alphabetize them as you write the list, or can you write the list after you alphabatize them?? If you just have to write them in order, you could just save all the objects into a string array and triquick sort or bubble sort them. Otherwise, you could bubble sort each time you add something to your linked list...

I'm not a java programmer, but I don't see how that wouldn't work in java...

-Whir

SickPup404 · March 18th, 2002, 01:32 PM

I'm a mainframe programmer, and what it sounds like you want to do is called a bubble sort.

A bubble sort looks kinda like this (pseudo-like pseudocode

)

- You have a list that is "X" items big.
- Do "X" times
- Do "X - 1" times
- Is Item "X" > Item "X+1"
- Item "X" and Item "X+1" swap places
- Go back to inside Do
- Go back to outside Do

I could give you an example in COBOL, but I'd be embarassed to let people know I still speak it!

Hope that makes sense.

I had this nicely indented....

[edit for last comment]

dragonb · March 18th, 2002, 02:07 PM

I did something similar in C.
I would assume you would want to put them in order as you put them in the linked list.
I would suggest a doubly linked list. With 1 list being 26 long, for the 26 letters of the alphabet, with a linked list off of each one of those that is dynamic, where you put each word in order as you go. And, once you can picture it, it really isn't as hard as it sounds.
Plus, it should be quite a bit faster than bubble sorting at the end, or bubble sort for each element.

Another way to do it is to put them in a binary tree. Picking m as your root, and then put them in before or after depending on the alphabetical. Then, just traverse the list in different ways for alphabetical, reverse-alphabetical, etc.

fun stuff, but after a whole semester of just that, it gets old, but you sure learn pointers!
dragonb

zskillz · March 18th, 2002, 02:35 PM

yes.. i have to alphabetize them as I write the list... which is really annoying, but that's a strict rule of the assignment. I suppose that a bubble sort is probably the quickest way to do it since the data will almost be totally in order anyway. here's the problem though.... I'm still having trouble comparing words that start with the same letter...

separating by first letter is easy since you can do charAt(0), but after the first letter, it gets much trickier to sort them alphabetically. is there some sort of unknown class/method in java that already does this or am I gonna have to figure it out on my own?

thanks for the help thus far
-Z

dragon... that sounds like a pretty good idea... but I'm pretty new to lists, so I'm wondering if I wanted to print out all of the data in the list.... wouldn't that be a little more complicated? or could I just print the 26 letter list and would that take care of everything else?. besides that... since the list of length 26 is constant... is it possible to build a list of an element in an array?... I mean - I could build an array of 26 (a-z) and then build a list of each element in the array... is this possible?

dragonb · March 18th, 2002, 03:17 PM

yea, that would work well, since the 26 is constant.
But, when you go to print it out, then you need code to traverse the array and the lists, where as if they are both linked lists, then there is a lot of similarity, and it can be done pretty nice with recursion.
I'll look into the other problem...

dragonb

<quote>dragon... that sounds like a pretty good idea... but I'm pretty new to lists, so I'm wondering if I wanted to print out all of the data in the list.... wouldn't that be a little more complicated? or could I just print the 26 letter list and would that take care of everything else?. besides that... since the list of length 26 is constant... is it possible to build a list of an element in an array?... I mean - I could build an array of 26 (a-z) and then build a list of each element in the array... is this possible?</quote>

zskillz · March 18th, 2002, 03:57 PM

dragon... i just reread my post and it might not be clear....

i meant... can i build a list off of an array element.... or perhaps I could declare the array as an array of list elements.... then build the lists off of that...

i bet that would work

-Z

qball · March 18th, 2002, 09:45 PM

Quote:

(using java) I'm reading in a comma delimited file and creating an object from each line.

why? defeats purpose of comma delimited (how do you alphabatize the commas?)...

Quote:

The rules of the assignment are that I have to alphabetize the objects and put them in a linked list as I'm reading them in.

zskillz · March 19th, 2002, 01:35 AM

q -
hopefully this will put all your qualms to rest

http://www.cs.colostate.edu/~cs200/a...signment3.html

-Z

qball · March 19th, 2002, 11:23 PM

homework.

tho this is interesting:

Quote:

Assignments that behave the same as the compiled code whose implementations stray from these guidelines may be docked points during grading.

that's harsh.

http://developer.java.sun.com/develo...106/index.html