Need the correction on Quick sort code

[javasuniltyata]

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

    /**
     * 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;
    }
 
 

[abhishekbrave]

where have you defined the class

MyVector

as used in the code

[javasuniltyata]

/**
 * 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;i++){
            data[i] = null;
        }
        size = 0;
    }
 
 
    /*
     * contains method check whether the vector contains the element
     * @param as element of Object type to add on data array.
     * @return of boolean type if data array contain element on it.
     */
    public boolean contains(Object element){
        for(int i=0;i<size;++i){
            if(element.equals(data[i]))
                return true;
        }
        return false;
    }
 
 
    /*
     * elementAt method appending the element at the end of the vector
     * @param as index of int type used to find the element in data array.
     * @return of Object type as element from data array if exist.
     */
 
    public Object elementAt(int index){
        if(index<0 || index>=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;i++){
            if(element.equals(data[i]))
                return i;
        }
        return -1;
    }
 
 
    /*
     * insertAt method inserts the element at the given index.
     * @param as index of type int shows the position where to insert element
     * @param as element of type Object which is going to insert in data array.
     * @return of boolean type which makes sure that insertion is successful.
     */
    public boolean insertAt(int index, Object element){
        if(index<0 || index>=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;i++){
            temp[i] = data[i];
        }
 
        data = temp;//temp is just a temporary object type array
                    //temp will disappare after the completion of expand method
                    //here data = temp : temp is reffered to data here.
    }
 
 
 
    /*
     * removeAt method remove the element at the given index.
     * @param as index of type int shows the position of element
     * @return as Object type which is the element to be removed.
     */
    public Object removeAt(int index){
        if(index<0 || index>=size)
            return null;
        Object o = data[index];
        for(int i=index;i<size-1;++i){
            data[i]=data[i+1];
        }
        --size;
        return o;
    }
 
 
    /*
     * remove method remove the element from the vector.
     * @param as element of type Object.
     * @return as boolean type which indicates element has been removed.
     */
    public boolean remove(Object element){
        return removeAt(indexOf(element))!=null;
    }
 
 
    /*
     * replace method replace the element at the given index with the given 
     * element.
     * @param as index of type int shows the position where to replace element
     * @param as element of type Object which is going to insert in data array.
     * @return of boolean type which makes sure that replacement is successful.
     */
    public boolean replace(int index,Object element){
        if(index<0 || index>=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<size;++i){
            vecCopy.data[i] = this.data[i];
        }
        vecCopy.size = this.size;
        return vecCopy;
    }
 
 
    /*
     * returns a string representation of this vector, containing the String
     * representation of each element. Actually, toString() method overrides
     * the toString() method of Object class. 
     * @return as String type comprises of different information like size, 
     * capacity and all the elements of vector.
     */
    public String toString(){
 
        String str = "+++...+++\n"
                    +"the current vector contain the following\n";
               str+="Size = "+size+"\n";
               str+="capacity = "+data.length+"\n";
 
               for(int i=0;i<size;++i){
 
                   str+=i+":"+data[i]+"\t";
                   if((i+1)%5==0)
                       str+="\n";
               }
 
               str+="+++...+++";
               return str;
 
    }
 
 
    /*
     * removeRange method removes from this vector all of the elements whose 
     * index is between fromIndex, inclusive and toIndex, exclusive
     * @param as fromIndex of type int shows the position where to start.
     * @param as toIndex of type int shows the position where to end.
     */    
    public void removeRange(int fromIndex,int toIndex){
        if(fromIndex>=toIndex)
            return;
        if(fromIndex<0)
            fromIndex =0;
        if(toIndex>=size)
            toIndex = size;
 
        int num=toIndex-fromIndex;
 
        for(int i=fromIndex;i<size-num;++i){
            data[i]=data[i+num];
        }
 
        for(int j=size-num;j<size;++j)
            data[j] = null;
        size = size-num;
    }
 
 
    /*
     * reverse method removes from this vector all of the elements whose 
     * index is between fromIndex, inclusive and toIndex, exclusive
     */    
    public void reverse(){
        for(int i=0,j=size-1;j>i;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<vector2.size;++i){
            this.append(vector2.data[i]);
        }
    }
 
}
 

I used above MyVector class for other different sorting algrithms they worked well I thing the error must be within quickSort method. Thank you. Hoping for ultimate answer.

I hope you got my reply.

[abhishekbrave]

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