By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,654 Members | 1,519 Online
Bytes IT Community
+ Ask a Question
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
  1.     /**
  2.      * Quick sort is a divide and conquer algorithm which relies on a partition 
  3.      * operation: to partition an array an element called a pivot is selected. 
  4.      * All elements smaller than the pivot are moved before it and all greater 
  5.      * elements are moved after it. This can be done efficiently in linear time 
  6.      * and in-place. The lesser and greater sublists are then recursively sorted. 
  7.      * Efficient implementations of quick sort (with in-place partitioning) are 
  8.      * typically unstable sorts and somewhat complex, but are among the fastest 
  9.      * sorting algorithms in practice.     
  10.      * 
  11.      * @param vec as Vector of MyVector type.
  12.      * @param left of type int represent left end index of vector.
  13.      * @param right of type int represent right end index of vector.
  14.      */
  15.     public static void quickSort(MyVector vec,int left,int right){
  16.         if(right-left+1<=10){
  17.             insertionSort(vec,left,right);
  18.         }
  19.         else{
  20.             medianOf3(vec,left,right);
  21.             int leftPtr=partition(vec,left,right);
  22.             quickSort(vec,left,leftPtr-1);
  23.             quickSort(vec,leftPtr+1,right);
  24.         }
  25.     }
  26.  
  27.  
  28.     /**
  29.      * medianOf3 helps to sort the elements at left,middle and right of vector.
  30.      * 
  31.      * @param vec as Vector of MyVector type.
  32.      * @param left of type int represent left end index of vector.
  33.      * @param right of type int represent right end index of vector.
  34.      */
  35.     public static void medianOf3(MyVector vec,int left,int right){
  36.         int middle = (left+right)/2;
  37.         if(((Comparable)vec.elementAt(left)).compareTo(vec.elementAt(middle))>0){
  38.             swap(vec,left,middle);
  39.         }
  40.         if(((Comparable)vec.elementAt(middle)).compareTo(right)>0){
  41.             swap(vec,middle,right);
  42.         }
  43.         if(((Comparable)vec.elementAt(left)).compareTo(vec.elementAt(middle))>0){
  44.             swap(vec,left,middle);
  45.         }
  46.     }
  47.  
  48.  
  49.  
  50.     /**
  51.      * partition method help the do partition of vector into half where
  52.      * one half contains all the elements less than pivot element and other
  53.      * half contains all the elements greater than pivot element.
  54.      * 
  55.      * @param vec as Vector of MyVector type.
  56.      * @param left of type int represent left end index of vector.
  57.      * @param right of type int represent right end index of vector.
  58.      * @return index of type int as partition point.
  59.      */
  60.     public static int partition(MyVector vec,int left,int right){
  61.         Object pivot = vec.elementAt((left+right)/2);
  62.         while(true){
  63.             while(((Comparable)vec.elementAt(++left)).compareTo(pivot)<0);
  64.             while(((Comparable)vec.elementAt(--right)).compareTo(pivot)>0);
  65.             if(left>right){
  66.                 break;
  67.             }
  68.             else{
  69.                 swap(vec,left,right);
  70.             }
  71.         }
  72.         return left;
  73.     }
  74.  
  75.  
Mar 31 '12 #1
Share this Question
Share on Google+
3 Replies


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

P: 7
Expand|Select|Wrap|Line Numbers
  1. /**
  2.  * MyVector class contains all the methods which help to manipulate MyVector
  3.  * Object and it also implements Cloneable Interface in order to implement the 
  4.  * clone() method.
  5.  * @author Sunil Tyata
  6.  * @version 2012.02.14
  7.  */
  8. public class MyVector implements Cloneable{
  9.     protected Object[] data;
  10.     protected int size;
  11.     private static final int INITIAL_CAPACITY=25;
  12.  
  13.  
  14.     /*
  15.      * Constructor for MyVector without andy parameter. But It initialize an
  16.      * Array of Object Class. 
  17.      */
  18.     public MyVector(){
  19.         data = new Object[INITIAL_CAPACITY];
  20.         size=0;
  21.     }
  22.  
  23.  
  24.     /*
  25.      * append method appending the element at the end of the vector
  26.      * @param as element of Object type to add on data array.
  27.      */
  28.     public void append(Object element){
  29.         if(size==data.length)
  30.             expand();
  31.         data[size] = element;
  32.         size++;
  33.     }
  34.  
  35.  
  36.     /*
  37.      * clear method make the vector collection empty
  38.      */   
  39.     public void clear(){
  40.         for(int i=0;i<size;i++){
  41.             data[i] = null;
  42.         }
  43.         size = 0;
  44.     }
  45.  
  46.  
  47.     /*
  48.      * contains method check whether the vector contains the element
  49.      * @param as element of Object type to add on data array.
  50.      * @return of boolean type if data array contain element on it.
  51.      */
  52.     public boolean contains(Object element){
  53.         for(int i=0;i<size;++i){
  54.             if(element.equals(data[i]))
  55.                 return true;
  56.         }
  57.         return false;
  58.     }
  59.  
  60.  
  61.     /*
  62.      * elementAt method appending the element at the end of the vector
  63.      * @param as index of int type used to find the element in data array.
  64.      * @return of Object type as element from data array if exist.
  65.      */
  66.  
  67.     public Object elementAt(int index){
  68.         if(index<0 || index>=size)
  69.             return null;
  70.         return data[index];
  71.     }
  72.  
  73.  
  74.  
  75.     /*
  76.      * indexOf method find the index of the element.
  77.      * @param as element of Object type used for finding index value.
  78.      * @return of int type as position of element in data array.
  79.      */
  80.  
  81.     public int indexOf(Object element){
  82.         for(int i=0;i<size;i++){
  83.             if(element.equals(data[i]))
  84.                 return i;
  85.         }
  86.         return -1;
  87.     }
  88.  
  89.  
  90.     /*
  91.      * insertAt method inserts the element at the given index.
  92.      * @param as index of type int shows the position where to insert element
  93.      * @param as element of type Object which is going to insert in data array.
  94.      * @return of boolean type which makes sure that insertion is successful.
  95.      */
  96.     public boolean insertAt(int index, Object element){
  97.         if(index<0 || index>=size)
  98.             return false;
  99.         if(size==data.length)
  100.             expand();
  101.         for(int i=size;i>index;i--){
  102.             data[i] = data[i-1];
  103.         }
  104.         data[index] = element;
  105.         ++size;
  106.         return true;
  107.     }
  108.  
  109.  
  110.     /*
  111.      * isEmpty method check whether the vector is empty.
  112.      * @return of boolean type which makes sure that vector is empty.
  113.      */    
  114.     public boolean isEmpty(){
  115.         return size<=0;
  116.     }
  117.  
  118.  
  119.      /*
  120.      * expand method helps of expand the size of fixed array of arbitrary size.
  121.      */
  122.     private void expand(){
  123.         Object[] temp = new Object[2*data.length];
  124.         for(int i=0;i<size;i++){
  125.             temp[i] = data[i];
  126.         }
  127.  
  128.         data = temp;//temp is just a temporary object type array
  129.                     //temp will disappare after the completion of expand method
  130.                     //here data = temp : temp is reffered to data here.
  131.     }
  132.  
  133.  
  134.  
  135.     /*
  136.      * removeAt method remove the element at the given index.
  137.      * @param as index of type int shows the position of element
  138.      * @return as Object type which is the element to be removed.
  139.      */
  140.     public Object removeAt(int index){
  141.         if(index<0 || index>=size)
  142.             return null;
  143.         Object o = data[index];
  144.         for(int i=index;i<size-1;++i){
  145.             data[i]=data[i+1];
  146.         }
  147.         --size;
  148.         return o;
  149.     }
  150.  
  151.  
  152.     /*
  153.      * remove method remove the element from the vector.
  154.      * @param as element of type Object.
  155.      * @return as boolean type which indicates element has been removed.
  156.      */
  157.     public boolean remove(Object element){
  158.         return removeAt(indexOf(element))!=null;
  159.     }
  160.  
  161.  
  162.     /*
  163.      * replace method replace the element at the given index with the given 
  164.      * element.
  165.      * @param as index of type int shows the position where to replace element
  166.      * @param as element of type Object which is going to insert in data array.
  167.      * @return of boolean type which makes sure that replacement is successful.
  168.      */
  169.     public boolean replace(int index,Object element){
  170.         if(index<0 || index>=size)
  171.             return false;
  172.         data[index] = element;
  173.         return true;
  174.     }
  175.  
  176.  
  177.     /*
  178.      * size method get the number of elements in the current vector. 
  179.      * @return as int type indicating size of vector.
  180.      */
  181.     public int size(){
  182.        return size; 
  183.     }//size()  get the number of elements in the current vector    
  184.  
  185.  
  186.     /*
  187.      * ensureCapacity method make sure the vector gets at least the given 
  188.      * capacity element.
  189.      * @param as minCapacity of type int used to check capacity.
  190.      */
  191.     public void ensureCapacity(int minCapacity){
  192.         if(minCapacity<=data.length)
  193.             return;
  194.         Object[] temp = new Object[minCapacity];
  195.         data = temp;//this really imp line where temp disappear at the end of the method.
  196.                     //but befor that temp is referred by data.
  197.     }
  198.  
  199.  
  200.     /*
  201.      * clone method returns a cloned copy of this vector.
  202.      * @return as MyVector type which is actually a clone of original vector.
  203.      */
  204.     public MyVector clone(){
  205.         MyVector vecCopy = new MyVector();
  206.         vecCopy.ensureCapacity(this.size);
  207.  
  208.         for(int i=0;i<size;++i){
  209.             vecCopy.data[i] = this.data[i];
  210.         }
  211.         vecCopy.size = this.size;
  212.         return vecCopy;
  213.     }
  214.  
  215.  
  216.     /*
  217.      * returns a string representation of this vector, containing the String
  218.      * representation of each element. Actually, toString() method overrides
  219.      * the toString() method of Object class. 
  220.      * @return as String type comprises of different information like size, 
  221.      * capacity and all the elements of vector.
  222.      */
  223.     public String toString(){
  224.  
  225.         String str = "+++...+++\n"
  226.                     +"the current vector contain the following\n";
  227.                str+="Size = "+size+"\n";
  228.                str+="capacity = "+data.length+"\n";
  229.  
  230.                for(int i=0;i<size;++i){
  231.  
  232.                    str+=i+":"+data[i]+"\t";
  233.                    if((i+1)%5==0)
  234.                        str+="\n";
  235.                }
  236.  
  237.                str+="+++...+++";
  238.                return str;
  239.  
  240.     }
  241.  
  242.  
  243.     /*
  244.      * removeRange method removes from this vector all of the elements whose 
  245.      * index is between fromIndex, inclusive and toIndex, exclusive
  246.      * @param as fromIndex of type int shows the position where to start.
  247.      * @param as toIndex of type int shows the position where to end.
  248.      */    
  249.     public void removeRange(int fromIndex,int toIndex){
  250.         if(fromIndex>=toIndex)
  251.             return;
  252.         if(fromIndex<0)
  253.             fromIndex =0;
  254.         if(toIndex>=size)
  255.             toIndex = size;
  256.  
  257.         int num=toIndex-fromIndex;
  258.  
  259.         for(int i=fromIndex;i<size-num;++i){
  260.             data[i]=data[i+num];
  261.         }
  262.  
  263.         for(int j=size-num;j<size;++j)
  264.             data[j] = null;
  265.         size = size-num;
  266.     }
  267.  
  268.  
  269.     /*
  270.      * reverse method removes from this vector all of the elements whose 
  271.      * index is between fromIndex, inclusive and toIndex, exclusive
  272.      */    
  273.     public void reverse(){
  274.         for(int i=0,j=size-1;j>i;j--,i++){
  275.             Object tempElement = data[i];
  276.             data[i] = data[j];
  277.             data[j] = tempElement;
  278.         }
  279.     }
  280.  
  281.  
  282.     /*
  283.      * add all the elements in vector2 to the end of this vector
  284.      * @param as vector2 of MyVector type which is one of the part of mering 
  285.      * vector.
  286.      */
  287.     public void merge(MyVector vector2){
  288.         for(int i=0;i<vector2.size;++i){
  289.             this.append(vector2.data[i]);
  290.         }
  291.     }
  292.  
  293. }
  294.  
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.
Apr 2 '12 #3

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

Post your reply

Sign in to post your reply or Sign up for a free account.