454,654 Members | 1,519 Online Need help? Post your question and get tips & solutions from a community of 454,654 IT Pros & Developers. It's quick & easy.

# Need the correction on Quick sort code

 P: 7 Any body could help to correct following code of quick sort would be appreciated. When I run this code I found the items in the collection are not sorted in ascending order. //Quick Sort Algorithm Expand|Select|Wrap|Line Numbers     /**      * Quick sort is a divide and conquer algorithm which relies on a partition       * operation: to partition an array an element called a pivot is selected.       * All elements smaller than the pivot are moved before it and all greater       * elements are moved after it. This can be done efficiently in linear time       * and in-place. The lesser and greater sublists are then recursively sorted.       * Efficient implementations of quick sort (with in-place partitioning) are       * typically unstable sorts and somewhat complex, but are among the fastest       * sorting algorithms in practice.           *       * @param vec as Vector of MyVector type.      * @param left of type int represent left end index of vector.      * @param right of type int represent right end index of vector.      */     public static void quickSort(MyVector vec,int left,int right){         if(right-left+1<=10){             insertionSort(vec,left,right);         }         else{             medianOf3(vec,left,right);             int leftPtr=partition(vec,left,right);             quickSort(vec,left,leftPtr-1);             quickSort(vec,leftPtr+1,right);         }     }         /**      * medianOf3 helps to sort the elements at left,middle and right of vector.      *       * @param vec as Vector of MyVector type.      * @param left of type int represent left end index of vector.      * @param right of type int represent right end index of vector.      */     public static void medianOf3(MyVector vec,int left,int right){         int middle = (left+right)/2;         if(((Comparable)vec.elementAt(left)).compareTo(vec.elementAt(middle))>0){             swap(vec,left,middle);         }         if(((Comparable)vec.elementAt(middle)).compareTo(right)>0){             swap(vec,middle,right);         }         if(((Comparable)vec.elementAt(left)).compareTo(vec.elementAt(middle))>0){             swap(vec,left,middle);         }     }           /**      * partition method help the do partition of vector into half where      * one half contains all the elements less than pivot element and other      * half contains all the elements greater than pivot element.      *       * @param vec as Vector of MyVector type.      * @param left of type int represent left end index of vector.      * @param right of type int represent right end index of vector.      * @return index of type int as partition point.      */     public static int partition(MyVector vec,int left,int right){         Object pivot = vec.elementAt((left+right)/2);         while(true){             while(((Comparable)vec.elementAt(++left)).compareTo(pivot)<0);             while(((Comparable)vec.elementAt(--right)).compareTo(pivot)>0);             if(left>right){                 break;             }             else{                 swap(vec,left,right);             }         }         return left;     }     Mar 31 '12 #1
3 Replies

 P: 79 where have you defined the class Expand|Select|Wrap|Line Numbers MyVector as used in the code Apr 2 '12 #2

 P: 7 Expand|Select|Wrap|Line Numbers /**  * MyVector class contains all the methods which help to manipulate MyVector  * Object and it also implements Cloneable Interface in order to implement the   * clone() method.  * @author Sunil Tyata  * @version 2012.02.14  */ public class MyVector implements Cloneable{     protected Object[] data;     protected int size;     private static final int INITIAL_CAPACITY=25;         /*      * Constructor for MyVector without andy parameter. But It initialize an      * Array of Object Class.       */     public MyVector(){         data = new Object[INITIAL_CAPACITY];         size=0;     }         /*      * append method appending the element at the end of the vector      * @param as element of Object type to add on data array.      */     public void append(Object element){         if(size==data.length)             expand();         data[size] = element;         size++;     }         /*      * clear method make the vector collection empty      */        public void clear(){         for(int i=0;i=size)             return null;         return data[index];     }           /*      * indexOf method find the index of the element.      * @param as element of Object type used for finding index value.      * @return of int type as position of element in data array.      */       public int indexOf(Object element){         for(int i=0;i=size)             return false;         if(size==data.length)             expand();         for(int i=size;i>index;i--){             data[i] = data[i-1];         }         data[index] = element;         ++size;         return true;     }         /*      * isEmpty method check whether the vector is empty.      * @return of boolean type which makes sure that vector is empty.      */         public boolean isEmpty(){         return size<=0;     }          /*      * expand method helps of expand the size of fixed array of arbitrary size.      */     private void expand(){         Object[] temp = new Object[2*data.length];         for(int i=0;i=size)             return null;         Object o = data[index];         for(int i=index;i=size)             return false;         data[index] = element;         return true;     }         /*      * size method get the number of elements in the current vector.       * @return as int type indicating size of vector.      */     public int size(){        return size;      }//size()  get the number of elements in the current vector             /*      * ensureCapacity method make sure the vector gets at least the given       * capacity element.      * @param as minCapacity of type int used to check capacity.      */     public void ensureCapacity(int minCapacity){         if(minCapacity<=data.length)             return;         Object[] temp = new Object[minCapacity];         data = temp;//this really imp line where temp disappear at the end of the method.                     //but befor that temp is referred by data.     }         /*      * clone method returns a cloned copy of this vector.      * @return as MyVector type which is actually a clone of original vector.      */     public MyVector clone(){         MyVector vecCopy = new MyVector();         vecCopy.ensureCapacity(this.size);           for(int i=0;i=toIndex)             return;         if(fromIndex<0)             fromIndex =0;         if(toIndex>=size)             toIndex = size;           int num=toIndex-fromIndex;           for(int i=fromIndex;ii;j--,i++){             Object tempElement = data[i];             data[i] = data[j];             data[j] = tempElement;         }     }         /*      * add all the elements in vector2 to the end of this vector      * @param as vector2 of MyVector type which is one of the part of mering       * vector.      */     public void merge(MyVector vector2){         for(int i=0;i

 P: 79 its difficult to understand the code you have posted...you can follow this link to understand the quick sort http://www.roseindia.net/java/beginn...uickSort.shtml Apr 4 '12 #4 