Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 9 of 9

Thread: sorting

  1. #1
    Junior Member kite98765's Avatar
    Join Date
    Jan 2010
    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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:
    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"));


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: sorting

    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).
    Last edited by helloworld922; January 30th, 2010 at 12:03 AM.

  3. The Following User Says Thank You to helloworld922 For This Useful Post:

    chronoz13 (January 30th, 2010)

  4. #3
    Senile Half-Wit Freaky Chris's Avatar
    Join Date
    Mar 2009
    Location
    Wales, Bangor & England, Warwickshire
    Posts
    820
    My Mood
    Cynical
    Thanks
    7
    Thanked 104 Times in 90 Posts

    Default Re: sorting

    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,
    answer.equals("y") || answer.equals("Y")

    can become
    answer.equalsIgnoreCase("Y")

    Chris
    chris[at]javaprogrammingforums[dot]com

    Prifysgol Bangor University, North Wales

  5. #4
    Junior Member kite98765's Avatar
    Join Date
    Jan 2010
    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Talking Re: sorting

    Quote Originally Posted by helloworld922 View Post
    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

  6. #5
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: sorting

    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.

  7. The Following User Says Thank You to helloworld922 For This Useful Post:

    kite98765 (February 4th, 2010)

  8. #6
    Junior Member kite98765's Avatar
    Join Date
    Jan 2010
    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: sorting

    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:

    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:
    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++;
    		}
    	              }
    Last edited by kite98765; February 3rd, 2010 at 07:37 PM.

  9. #7
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,267
    Thanks
    176
    Thanked 821 Times in 764 Posts
    Blog Entries
    5

    Default Re: sorting

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

  10. The Following User Says Thank You to copeg For This Useful Post:

    kite98765 (February 4th, 2010)

  11. #8
    Member
    Join Date
    Jan 2010
    Location
    Oxford, UK
    Posts
    30
    Thanks
    2
    Thanked 7 Times in 7 Posts

    Default Re: sorting

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

    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.

  12. #9
    Junior Member kite98765's Avatar
    Join Date
    Jan 2010
    Posts
    9
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default Re: sorting

    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:
    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;
    	                              }
                                                }
    	                 }

Similar Threads

  1. Selection Sorting of Data type (Char)
    By chronoz13 in forum Algorithms & Recursion
    Replies: 1
    Last Post: December 20th, 2009, 07:28 PM
  2. Selection Sorting
    By chronoz13 in forum Algorithms & Recursion
    Replies: 5
    Last Post: December 10th, 2009, 10:08 AM
  3. Sorting Algorithms
    By Dalisra in forum Java Programming Tutorials
    Replies: 1
    Last Post: November 10th, 2009, 08:24 PM
  4. [SOLVED] help with sorting...(comparator)
    By mdstrauss in forum Collections and Generics
    Replies: 2
    Last Post: July 26th, 2009, 06:25 AM
  5. [SOLVED] Java program to sort arrays containing dates
    By scottyadam in forum Collections and Generics
    Replies: 1
    Last Post: March 9th, 2009, 06:08 PM