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 2 of 2

Thread: Using Quicksort on a Vector of Integers?

  1. #1
    Junior Member
    Join Date
    Oct 2012
    Posts
    2
    My Mood
    Confused
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Question Using Quicksort on a Vector of Integers?

    Hi, I implemented in my code a scanner suppose to open a file containing a vector (that you created if you didn't have one already). The program is then suppose to sort it when it opens it and ask the user if he wants to see it (and eventually save it).
    I tried to implement the quicksort() method but something's wrong and I can't figure out what... I tried to change the type comparable to integer but didn't change anything.
    Can you help me?

    Thanks!

    Here's the code:





    import java.util.*;
    import java.io.*;  // for input/output streams
    import java.util.Vector;  
     
     
    //Added :  sort element at open file  &&   quisort : need to modify it to call vector && check the constructor, need to add one
     
     
    public class LabNum2 extends Vector<Integer> {
     
      // public boolean isEmpty() ** inherited from Vector **
      // public String toString() ** inherited from Vector **
      // public int size()   ** inherited from Vector **
      // public void clear() ** inherited from Vector **
     
     
     /* Implements the quicksort algorithm & sorts Vectors of objects that implement the Comparable interface.
        The sort is based on Comparable.compare(obj) method.*/
     
      static void swap(Vector v, int i, int j)  {
        Comparable x = (Comparable)v.elementAt(i);
        v.setElementAt(v.elementAt(j), i);
        v.setElementAt(x, j);
      } 
     
      static void quickSort(Vector v, int x, int y)  {
        if (y-x < 0) {
          return;
        }
        int m, pivot, other;
        m = (y+x)/2;
        if (((Comparable)v.elementAt(x)).compareTo(v.elementAt(y)) < 0) {
          pivot = x;
          other = y;
        }
        else {
          pivot = y;
          other = x;
        }
        if (((Comparable)v.elementAt(pivot)).compareTo(v.elementAt(m)) < 0) {
          if (((Comparable)v.elementAt(m)).compareTo(v.elementAt(other)) < 0) {
            pivot = m;
          }
          else {
            pivot = other;
          }
        }
     
        swap(v, x, pivot);
     
        int i, j;
        i = x + 1;
        j = y - 1;
        while (true) {
          while (((Comparable)v.elementAt(x)).compareTo(v.elementAt(i)) < 0) {
            i++;
          }
          while (((Comparable)v.elementAt(x)).compareTo(v.elementAt(j)) > 0) {
            j--;
          }
          if (i >= j) {
            break;
          }
          swap(v, i, j);
          i++;
          j--;
        }
        swap(v, x, j);
        if (j - x < y -i) {
          quickSort(v, x, j-1);
          quickSort(v, i, y);
        }
        else {
          quickSort(v, i, y);
          quickSort(v, x, j-1);
        }
      } 
     
     
     
     
      public static void sort(Vector v)  {
        quickSort(v, 0, v.size()-1);
     
      } 
     
      public static void main(String[] args)  {
        String input = " ";
        String nameInput=  " ";
        Scanner scanner = new Scanner(System.in);
        Vector<Integer> v = new Vector<Integer>();
     
     
         System.out.println("Hi, would you like to load a vector from a file?");
            input = scanner.nextLine();
            if (input.charAt(0)=='y' || input.charAt(0)=='Y') {
              System.out.println("Enter the name used last time(don't forget the .dat extension at the end");
              nameInput = scanner.nextLine();                             
                try {
                    FileInputStream fis = new FileInputStream(nameInput);
                    ObjectInputStream ois = new ObjectInputStream(fis);
                    v = (Vector<Integer>) ois.readObject();   // read an Object, cast to proper type
                    ois.close();
                    fis.close();   // we're done reading from these streams                
                    //quicksort(v, 0 , v.size()-1);   //PROBLEM
                    sort(v);
                }
                catch (Exception e) {
                    System.out.println("Sorry, I can't read a vector from that file:" + e);
                    e.printStackTrace();
                }
            }
            //
            else {
              System.out.println("Please add 10 digits to the vector");
              for (int i=v.capacity(); i>0; i--){
                input = scanner.nextLine();
                v.add(Integer.parseInt(input));  //be able to input multi-digit number and correct the bug that arises when the last number entered is a multi-figit number
              }
                }
     
            System.out.println("The vector has been uploaded and sorted! Would you like to see it?");  
              input = scanner.nextLine();
              try{
              if (input.charAt(0)=='y' || input.charAt(0)=='Y')
     
                System.out.print(v + "\n");
              }
              catch (Exception e){
                System.out.println("Wrong input");
              }
     
              System.out.println("Would you like to save the Vector into a file?");
              input = scanner.nextLine();
              if (input.charAt(0)=='y' || input.charAt(0)=='Y') {            
                System.out.println("Choose a name for the file (remember to add .dat at the end)");
                nameInput = scanner.nextLine();          
                try {
                  FileOutputStream fos = new FileOutputStream(nameInput);
                  ObjectOutputStream oos = new ObjectOutputStream(fos);
                  oos.writeObject(v);
                  oos.close();
                  fos.close();
                }
                catch (Exception e) {
                  System.out.println("Sorry, I cannot write a vector to that file:" + e);
                }
              }
    }
    }


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: Using Quicksort on a Vector of Integers?

    Where does the program's behavior start to differ from what you expect it to do? You should use a debugger or print statements to figure that out.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Quicksort
    By wholegrain in forum Java Theory & Questions
    Replies: 7
    Last Post: February 12th, 2012, 08:31 PM
  2. QuickSort method
    By D3158 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 15th, 2011, 09:17 PM
  3. [SOLVED] Writing Integers to .txt File; Returning Random Characters Instead of Integers
    By verbicidalmaniac in forum File I/O & Other I/O Streams
    Replies: 2
    Last Post: March 8th, 2011, 09:42 PM
  4. Replies: 2
    Last Post: December 22nd, 2010, 09:21 AM
  5. Determine the two smallest integers from a set of user input integers
    By bpontin in forum Loops & Control Statements
    Replies: 4
    Last Post: October 17th, 2010, 06:38 PM