sorting

Hello,
I am writing a program where we use a Bubble Sort to alphabetize words and their corresponding defintions. So far, i have entering of the words and their definitions going for me, but I can't quite figure out the Bubble Sort. Here's what I have:

Code :

---

public class BubbleSort {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner indata = new Scanner(System.in);
		ArrayList <String> entry = new ArrayList <String>();
		ArrayList <String> definition = new ArrayList <String>();
		int selection = 0;
		String store, del, choice, answer;
                                                                                                     do{
					System.out.print("Please enter a word: ");
					store = indata.next();
					entry.add(store);
					store = indata.nextLine();
					System.out.print("Please enter a brief definition of " + store + ": ");
					store = indata.nextLine();
					definition.add(store);
					System.out.println();
					System.out.println("Would you like to enter another word?(Y/N)");
					answer = indata.next();
					System.out.println();
				}while(answer.equals("y") || answer.equals("Y"));

---

Gah! Bubble sort? If this is for a class, please tell your professor that there is absolutely no use for it. It's very inefficient and hard to implement. If you are doing this for yourself, I would strongly recommend switching to Insertion Sort. It has O(n^2) worst case performance (in theory the same as bubble sort, but in reality bubble sort is slower). If you are required to have some sort of "bubbling up" effect, use heap sort. Heap sort is O(nlog(n)) performance (even better than insertion sort), but is a more advanced algorithm to implement.

edit:

Oops... bubble sort isn't actually slower than selection sort because I forgot selection sort was "dumb" (O(n^2) all the time) and bubble sort was "semi-intelligent" (O(n) like insertion sort best case scenario, but still slower than insertion sort because of truncation errors from big-O notation).

If you must do a bubble sort, google it. I'm sure wiki pedia will tell you how tp implement it, if not implement it for you!

Also,

Code :

---

answer.equals("y") || answer.equals("Y")

---

can become

Code :

---

answer.equalsIgnoreCase("Y")

---

Chris

Quote:

---

Originally Posted by helloworld922

Gah! Bubble sort? If this is for a class, please tell your professor that there is absolutely no use for it. It's very inefficient and hard to implement. If you are doing this for yourself, I would strongly recommend switching to Insertion Sort. It has O(n^2) worst case performance (in theory the same as bubble sort, but in reality bubble sort is slower than even selection sort, which is slower than insertion sort). If you are required to have some sort of "bubbling up" effect, use heap sort. Heap sort is O(nlog(n)) performance (even better than insertion sort), but is a more advanced algorithm to implement.

---

My professor, after reading your posting, that you can "kiss [his] ass." He also said that the Big O notation for insertion sort is the SAME as bubble sort. He said, "It's wannabes like you that lead students in the wrong direction. They need to learn how to crawl before they can walk."

If you would like to ensue this further, you can have his email, which he proposed I give you if you would like it.

On the other hand, I lol'd. XD

:P Ok, well it's his class and not mine.
Here's what wikipedia has to say about bubble sort: Bubble sort

If you still want to help implementing the algorithm, just ask.

Help would be awesome. I have the right code, it just needs some tweaking. It sorts the first three words, then totally forgets sorting the next one, then sorts the next three words, like so:

Code :

---

1. Add a word and definition
2. Dislay the word list
3. Search for a word and display it's definition
4. Delete a word
5. Quit
1
You've decided to add a word and defintion.
Please enter a word: Pie
Please enter a brief definition of Pie: a pastry with an outer crust and inner filling
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Milk
Please enter a brief definition of Milk: a dairy beverage produced by cows
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Sprint
Please enter a brief definition of Sprint: to run at a rapid pace
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Leap
Please enter a brief definition of Leap: to jump a large distance
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Clarinet
Please enter a brief definition of Clarinet: a musical instrument in the woodwind category
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Tennis
Please enter a brief definition of Tennis: a game played with a racket to hit a ball, and a rubber tennis ball
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Ticket
Please enter a brief definition of Ticket: ususally a slip of paper allowing a person admission into an event
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Freezer
Please enter a brief definition of Freezer: a large appliance used to keep food frozen to preserve them for long periods of time
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Cantalope
Please enter a brief definition of Cantalope: a small round fruit, with an outer greenish skin and orange interior
 
Would you like to enter another word?(Y/N)
y
 
Please enter a word: Balloon
Please enter a brief definition of Balloon: a latex cylinder shaped object that can be filled with a substance, such as aair
 
Would you like to enter another word?(Y/N)
n
 
1. Add a word and definition
2. Dislay the word list
3. Search for a word and display it's definition
4. Delete a word
5. Quit
2
You've decided to display the word list.
1. Leap
2. Milk
3. Pie
4. Clarinet
5. Sprint
6. Tennis
7. Ticket
8. Freezer
9. Cantalope
10. Balloon

---

Here's my algorithm, which is a Bubble Sort:

Code :

---

while(done == false){
		done = true;
		for(int f = 0; f < entry.size() - 1 - pass; f++){
			if(entry.get(f).compareTo (entry.get(f + 1)) > 0){
				temp = entry.get(f);
				temp1 = definition.get(f);
				temp2 = entry.get(f + 1);
				temp3 = definition.get(f + 1);
				entry.set((f + 1), temp);
				definition.set((f + 1), temp1);
				entry.set((f), temp2);
				definition.set((f), temp3);
				done = false;
			}
		                       pass++;
		}
	              }

---

Discussions of efficiency aside, take a close look at the pass variable, and whether its really necessary

I think the 'pass' variable is playing a useful role, but the boolean 'done' is not. Why not try:

Code :

---

while(pass<entry.length-1)
{
//algorithm
}

---

I like bubble sort, but only for sentimental reasons. While teaching myself C, I decided to try writing some sorting algorithms before reading anything about them. The first thing I wrote turned out to be bubble sort. :)

Hey all,
Thanks for the help, but it was the pass variable that was screwing it up. The second I removed all of the pass variables in the program, it runs perfectly. Thanks guys!
It looks like this:

Code :

---

while(done == false){
		done = true;
		for(int f = 0; f < entry.size() - 1; f++){
		        if(entry.get(f).compareTo (entry.get(f + 1)) > 0){
			temp = entry.get(f);
			temp1 = definition.get(f);
			temp2 = entry.get(f + 1);
			temp3 = definition.get(f + 1);
			entry.set((f + 1), temp);
			definition.set((f + 1), temp1);
			entry.set((f), temp2);
			definition.set((f), temp3);
			done = false;
	                              }
                                            }
	                 }

---