8 Replies Latest reply: Dec 3, 2007 4:12 PM by 807600 RSS

    merge sorting vectors

    807600
      I just have a question about sorting and searching vectors.
      Is it possible to use merge sort to sort a list where each node of the linkedlist is a vector where each vector contains different types of data(string, long).
      so if that was confusing, there are going to be a bunch of vectors that have a bunch of strings and a long in each vector. And each individual vector(with all that information) is going to be a separate node in the linked list.
      This is my code that does that:
      import java.util.*;
      import java.awt.*;
      import exceptions.*;
      import javax.swing.*;
      
      public class cpAppletInfo extends JApplet 
      {
        
          //    initialization of Vectors
          public void paint( Graphics g )
          {
          DifferentInputException exception = new DifferentInputException();
          JOptionPane pane = new JOptionPane();
          Scanner input = new Scanner( System.in );
          LinkedList thing = new LinkedList();
          String userName;
          String first;
          String last;
          String ss;
          String pass;
          String rePass;
          String eMail;
          super.paint( g );
          
          String field = pane.showInputDialog( "How many fields do you want to enter?" );
          int field1 = Integer.parseInt( field );
          for( int count = 0; count < field1; count++ )
          {
          Vector userInfo = new Vector();
          
          
          userName = pane.showInputDialog( "Enter your user name: " );
          userInfo.addElement(new String(userName));
          
          first = pane.showInputDialog( "Enter your first name: " );
          userInfo.addElement(new String(first));
          
          last = pane.showInputDialog( "Enter your last name: " );
          userInfo.addElement(new String(last));
          
          ss = pane.showInputDialog( "Enter your social security number: " );
          Long newSS = Long.parseLong( ss );
          userInfo.addElement(new Long(newSS));
          
          pass = pane.showInputDialog( "Enter your pass word: " );
          userInfo.addElement(new String(pass));
          
          rePass = pane.showInputDialog( "Retype your password: " );
          if( !rePass.equalsIgnoreCase(pass) )
          {
              throw new DifferentInputException();    
          } 
          else
          userInfo.addElement(new String(rePass));
          
          eMail = pane.showInputDialog( "Enter your e-mail address: " );
          userInfo.addElement(new String(eMail));
      
          thing.addLast(userInfo);
          thing.addLast("\n");
          }
          
          
          pane.showMessageDialog( null, thing );
          }
          
        
      }
      Now is there a way to use merge sort to sort the linked list? Not the vectors, the whole list so that each vector is placed in a certain order but the information inside the vector is untouched.
        • 1. Re: merge sorting vectors
          807600
          Have you taken a look at Collections.sort ? AFAIR, it uses some kind of stable merge-sort. There shouldn't be any problem sorting Vectors in a list.

          laginimaineb.
          • 2. Re: merge sorting vectors
            807600
            You're using Vectors badly. Basically you're mixing data like that because you're emulating a class. You should just define a class that represents user data. Then you can make that class implement Comparable, or create a Comparator for it. After that, it's trivial to use Collections.sort to sort a List of them.
            • 3. Re: merge sorting vectors
              807600
              I agree that i am not using vectors effectively, but that is the way that my instructor wanted me to use it. So i am stuck with this weird vector in list thing...
              and as far as i am concerned, i am not allowed to use the collections, i have to build my own merge sort and search for my list.
              • 4. Re: merge sorting vectors
                807600
                You should have mentioned these restrictions at the outset.

                Anyway you can build a merge sort. You'll probably get an iterator for your linked lists and merge them. And I believe there's a subList() method in List that you'll find helpful. Also size(). Unless you can't use those either.
                • 5. Re: merge sorting vectors
                  807600
                  sorry about not mentioning that.
                  I did build a mergesort... for an array of integers, what i am really confused about is how does he want us to sort the vectors. They are not numbers so definitely not in ascending or descending orders, we didn't learn about comparators so they probably won't work. I dont' understand how to even set the conditions of the sort. alphabetical? any random order?
                  when i asked him to clarify, he said something about he didn't care how i do it, but i can't use collections...*sigh* trust me, my instructor is a bit weird at times.

                  my mergesort for array of integers:
                  import java.util.*; 
                  public class sortArray 
                  {
                       private int[] thing;
                  
                      public sortArray( int size )
                       {
                            thing = new int[size]; 
                            for (int next = 0 ; next < size; next++)
                            {
                                 Scanner input = new Scanner( System.in );
                                 int add;
                                 int next1 = next + 1;
                                 System.out.println( "Enter integer number " + next1 );
                                 add = input.nextInt();
                                 thing[next] = add;
                            }
                       }
                  
                       public void sort()                  
                      {  
                            sortThingy( 0, thing.length - 1 );                            
                      }                                                
                      
                      public void sortThingy( int lowest, int highest ) 
                       {
                            if ( ( highest - lowest) >= 1 )
                            {
                                 int middle1 = ( lowest + highest ) / 2;
                                 int middle2 = middle1 + 1;
                  
                                 sortThingy( lowest, middle1 );          
                              sortThingy( middle2, highest );        
                              merge ( lowest, middle1, middle2, highest ); 
                            }
                       }
                  
                       private void merge( int left, int middle1, int middle2, int right )  
                       {  
                          int leftPart = left;               
                          int rightPart = middle2;           
                          int mergedParts = left;  
                          int[] merged = new int[ thing.length ];       
                          
                                     
                          while ( leftPart <= middle1 && rightPart <= right )  
                          {  
                                  
                             if ( thing[ leftPart ] <= thing[ rightPart ] )          
                                merged[ mergedParts++ ] = thing[ leftPart++ ];   
                             else                                                    
                                merged[ mergedParts++ ] = thing[ rightPart++ ];  
                          }                                              
                         
                                                         
                          if ( leftPart == middle2 )                                
                                                      
                             while ( rightPart <= right )                           
                                merged[ mergedParts++ ] = thing[ rightPart++ ];  
                          else                           
                             while ( leftPart <= middle1 )                          
                                merged[ mergedParts++ ] = thing[ leftPart++ ];   
                      
                          
                          for ( int i = left; i <= right; i++ )    
                             thing[ i ] = merged[ i ];            
                       
                       } // end method merge
                       public int binarySearch( int searchElement )  
                       {  
                          int low = 0;                  
                          int high = thing.length - 1; 
                          int middle = ( low + high + 1 ) / 2;       
                          int location = -1;         
                      
                          do   
                          {   
                            
                                     
                                  if ( searchElement == thing[ middle ] )                   
                               location = middle;  
                      
                               else if ( searchElement < thing[ middle ] )          
                               high = middle - 1;  
                               else                  
                               low = middle + 1;     
                      
                               middle = ( low + high + 1 ) / 2;
                                 }
                           while ( ( low <= high ) && ( location == -1 ) );             
                      
                          return location+1;  
                       }   
                       public String subarray( int low, int high )  
                       {  
                          StringBuffer temporary = new StringBuffer();  
                      
                          // output spaces for alignment  
                          for ( int i = 0; i < low; i++ ) 
                             temporary.append( "   " ); 
                     
                          // output elements left in array 
                          for ( int i = low; i <= high; i++ ) 
                             temporary.append( " " + thing[ i ] ); 
                     
                          return temporary.toString(); 
                       } // end method subarray 
                     
                       // method to output values in array 
                       public String toString() 
                       { 
                          return subarray( 0, thing.length - 1 ); 
                       } // end method toString
                  
                       public static void main(String[] args) 
                       {
                           Scanner input = new Scanner( System.in );
                            int searchFor;
                            int position;
                            System.out.println( "How many integers would you like your array to have?" );
                            int size1 = input.nextInt();
                            sortArray sortThing = new sortArray( size1 );
                  
                            sortThing.sort();
                  
                            System.out.println( "Here you go: " + "\n" + sortThing );
                  
                            System.out.println( "Which number would you like to look for?" );
                            
                            searchFor = input.nextInt(); // read an int from user  
                          System.out.println();   
                          
                          position = sortThing.binarySearch( searchFor );  
                      
                             // return value of -1 indicates integer was not found  
                          if ( position == 0 )  
                              System.out.println( "The integer " + searchFor + " was not found.\n" );  
                          else  
                              System.out.println( "The integer " + searchFor + " is in position " + position + ".\n" );  
                      
                              
                             
                           
                       }
                  }
                  Edited by: Razaac on Dec 2, 2007 8:33 AM
                  • 6. Re: merge sorting vectors
                    807600
                    Razaac wrote:
                    I did build a mergesort... for an array of integers, what i am really confused about is how does he want us to sort the vectors. They are not numbers so definitely not in ascending or descending orders, we didn't learn about comparators so they probably won't work. I dont' understand how to even set the conditions of the sort. alphabetical? any random order?
                    Well, obviously you can't sort the vectors unless you have some way to compare them to determine which comes first. Without an ordering, "sorted" becomes meaningless.
                    when i asked him to clarify, he said something about he didn't care how i do it, but i can't use collections...*sigh* trust me, my instructor is a bit weird at times.
                    "Weird" may be putting it nicely.

                    If your teacher (who is looking increasingly like an idiot) didn't specify one, then you should make one yourself. Either that or give up. It's simply impossible to sort without an ordering -- it doesn't mean anything. So I'd just suggest sorting alphabetically by last name, then by first name. If two vectors hold the same first and last name, you can either say they're equal with respect to sorting (that's allowed in the real world; who knows what's allowed in the magical parallel universe your teacher lives in), or keep choosing attributes of the data that you feel are appropriate.
                    • 7. Re: merge sorting vectors
                      807600
                      alright, that sounds good.
                      I'll try to do that.
                      Do you know any tutorial on any site that might help me to get started?
                      • 8. Re: merge sorting vectors
                        807600
                        About writing your own sort? I can't think of any. Typically you use the API's sort.

                        I'd suggest reading the API docs for java.util.List and java.util.Comparator.