Results 1 to 4 of 4
  1. #1
    rhm54 is offline Member
    Join Date
    Jan 2008
    Posts
    12
    Rep Power
    0

    Default Help with Sorting Program

    Alright guys I am lost. I thought that I had this correct but I have done something terribly wrong. The bubble sort simply spits out the orginal string and the merge sort goes on forever and the bucket sort doesn't seem to do anything. Please help!

    Java Code:
    package com.shadowconcept.mcdougal;
    
    import java.io.*;
    
    public class Sort {
      	
      public static void main(String[] args) {
      	  
    	  /* Retrieves the filename of dataset from the command-line arguments */
    	  if (args.length != 1) {
    		  System.err.println("Usage:java Sort filename.txt");
    		  System.exit(1);
    	  }
      
    	  /* Reading data from the file system */
    	  try {
    		  int[] data = null;
    		  String line;
    		  FileReader input = new FileReader(args[0]);
    		  BufferedReader bufRead = new BufferedReader(input);
    		  line = bufRead.readLine();
    		  while (line != null) {
    			  if (line.length() > 0) {
    				  String[] tokens = line.split(" ");
    				  data = concat(data, str2int(tokens));
    			  }
    			  line = bufRead.readLine();
    		  }
    		  bufRead.close();
    		  
    		  
    		  
    		/* Create an instance of Sort class */
    		  
    		  
    		  Sort s = new Sort();
    		  
    		  /* Perform bubble sort on dataset and display the result */
    		  int bubblesorted[] = s.bubble(data);
    		  s.dispList(bubblesorted);
    		  
    		  /* Perform merge sort on dataset and display the result */
    		  //s.dispList(s.merge(data));
    		  
    		  /* Perform bucket sort on dataset and display the result */
    		  s.dispList(s.bucket(data)); 
    		  
    	  } catch (IOException e) {
    		  e.printStackTrace();
    	  } // end of try ... catch
    	  
      } // end of main
    
        
      public static int[] bubble(int[] list) {
          int[] sortedList = null;
          System.out.println("Run bubble sort");
            int i = list.length ;
            for (int pass=1; pass < i; pass++) { 
                // count how many passes through the array
                  for (int j=0; i < i-pass; i++) {
                    if (list[j] > list[j+1]) {
                        // This swaps the elements in the array around
                        int temp = list[j]; 
                        list[j] = list[j+1]; 
                        list[j+1] = temp;
                    }
                }
            }
          sortedList = list;
          return sortedList;
      }
      
      public static int[] merge(int[] list)
      {
    	  System.out.println("Run merge sort");
            if(list.length == 0)
                  return list;
       
             int list1Size = list.length/2;  //this truncates any remainder.
             int list2Size = list.length/2 + list.length%2; 
    
             int[] firsthalf = new int[list1Size ];
             int[] secondhalf = new int[list2Size ];
    
             //using the listSizes, and the list parameter, fill the two arrays.
    
             int[] result1 = merge(firsthalf ); 
             int[] result2 = merge(secondhalf ); 
    
             
            int index1 = 0;
            int index2 = 0;
    
            int[] sortedList = new int[list.length];
            int i = 0;
    
            
            while(index1 < result1.length && index2 < result2.length)
            {
                //if one of the two arrays has already been copied completely, then grab the next item from the other.
                if(index1 == result1.length || index2 == result2.length)
                {
                      if(index1 == result1.length)
                      {
                          sortedList[i] = result2[index2];
                          index2++;
                      }
                      else
                      {
                          sortedList[i] = result1[index1];
                          index1++;
                      }
                }
                else
                {
                     //otherwise, we need to figure out which item is smaller, and move that one to the next empty array position.
                     if(result1[index1] < result2[index2])
                     {
                          sortedList[i] = result1[index1];
                          index1++;
                     }
                     else
                     {
                          sortedList[i] = result2[index2];
                          index2++;
                     }
                }
                i++;
            }
             
            return sortedList;
      }
      
      public static int[] bucket(int[] list) {
    	  int[] sortedList = new int[list.length];
          
          if(list.length > 0)
          {
               int max = 0;
               int min = list[0];
         
               //loop through and grab max and min values
               for(int i=0; i<list.length; i++)
               {
                    if(list[i] < min)
                         min = list[i];      
                    if(list[i] > max)
                         max = list[i];
               }
              
    
               int step = (max - min) / 5;
               if((max - min) % 5 != 0)
                   step = step + 1;
    
              int[][] buckets = new int[5][];
             
              //bucket allocation
              for(int i=0; i< list.length;i++)
              {
                     int bucketIndex = list[i]/step;
                     if(list[i] == max)
                          bucketIndex--;
    
                    buckets[bucketIndex] = concat(buckets[bucketIndex], list);
              }
    
              //sort the buckets and throw then into the sortedList array.
              for(int i=0; i<5; i++)
              {
                     int[] temp = bubble(buckets[i]);
                     sortedList = concat(sortedList, temp);
              }
    
          }
          return sortedList;
    
      }
      
      /* The dispList will display all elements in the list */
      public static void dispList(int[] list) {
    	  for (int i = 0 ; i < list.length ; i++) {
    	    System.out.print(list[i] + " ");
      	}
      	System.out.print("\n");
      } // end of dispList
      
      public static int[] concat(int[] A, int[]B) {
    	  if (A != null && B != null) {
    	  	int[] C = new int[A.length + B.length];
    	  	System.arraycopy(A, 0, C, 0, A.length);
    	  	System.arraycopy(B, 0, C, A.length, B.length);
    	  	return C;
      	} else if (A != null) {
    	  	return A;
      	} else if (B != null) {
    	  	return B;
      	}
      	return null;
      }
      
      public static int[] str2int(String[] A) {
    	  int[] B = new int[A.length];
    	  for (int i=0 ; i < A.length ; i++) {
    		  B[i] = Integer.parseInt(A[i]);
    		}
    		return B;
      }
      
    } // end of Sort class

    These is the numbers that I am sorting. They are in the file 100.txt

    63 31 37 94 41 64 72 70 40 33 9 38 84 15 32 91 53 7 96 5 49 41 65 83 37 11 39 51 43 52 99 46 91 59 95 4 10 32 53 31 90 59 70 56 69 62 19 38 27 34 20 23 60 84 36 8 96 23 40 42 34 9 100 95 74 14 86 89 38 33 72 8 59 56 13 36 79 19 73 67 60 40 23 89 79 54 68 19 71 57 61 75 39 91 97 90 48 71 83 61

  2. #2
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    I think you should learn about other sorts. I personally have never used BubbleSort, but I have used others like SelectionSort, InsertionSort, QuickSort and MergeSort. I recommend MergeSort. It's pretty cool once you understand how it works. Basically, it splits up the data in half, and does it over and over again through recursion, and then sorts the simplest set. Here:

    2 4 5 1 9 3 8 7
    __________________________
    2 4 5 1 | 9 3 8 7
    __________________________
    2 4 | 5 1 | 9 3 | 8 7|
    _________________________
    Now, sort each part
    __________________________
    2 4 | 1 5 | 3 9 | 7 8 |

    etc.



    Maybe you already know about MergeSort, and my reply doesn't really help you with your problem, so I'm sorry if that's the case.

  3. #3
    CaptainMorgan's Avatar
    CaptainMorgan is offline Moderator
    Join Date
    Dec 2007
    Location
    NewEngland, US
    Posts
    835
    Rep Power
    8

    Default

    Welcome to the Java Forums rhm

    For starters, 1 out of 3, have a look at this one particular line for your Bubble Sort:
    Java Code:
                  for (int j=0; i < i-pass; i++) {
    ... it should be:
    Java Code:
                  for (int j=0; [B]j[/B] < i-pass; [B]j[/B]++) {
    ... and it should work.

    If I had more time I would go into your MergeSort.. even though it looks a bit ugly.. no offense. I definitely would break that up into smaller components and attempt that again. If someone doesn't assist by the time I finish work tomorrow I'll give it a go. For the bucket tho, that's one I've never implemented... so maybe someone can assist with that one or I'll learn it!

    See you around!
    Vote for the new slogan to our beloved Java Forums! (closes on September 4, 2008)
    Want to voice your opinion on your IDE/Editor of choice? Vote now!
    Got a little Capt'n in you? (drink responsibly)

  4. #4
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    Wow i just realized that you had merge in your code. Sorry for the useless post, i had been reading code all day and i didn't feel like reading it haha.

Similar Threads

  1. sorting problem...
    By mark-mlt in forum New To Java
    Replies: 4
    Last Post: 04-17-2008, 02:15 PM
  2. sorting problem
    By mcal in forum New To Java
    Replies: 1
    Last Post: 02-14-2008, 08:13 AM
  3. Sorting members in Eclipse
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 12-04-2007, 11:25 AM
  4. Heap Sorting
    By kesav2005 in forum New To Java
    Replies: 1
    Last Post: 11-13-2007, 04:04 PM
  5. sorting JTable
    By mansi_3001 in forum Advanced Java
    Replies: 3
    Last Post: 08-10-2007, 06:29 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •