This discussion is archived
8 Replies Latest reply: Dec 3, 2007 2:12 PM by 807600 RSS

merge sorting vectors

807600 Newbie
Currently Being Moderated
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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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.