# Using Quicksort on a Vector of Integers?

• November 14th, 2012, 12:12 AM
mescoff
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? :confused:

Thanks!

Here's the code:

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); } } } }```
• November 14th, 2012, 07:25 AM
KevinWorkman
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.