Tuesday, September 16, 2014

Quicksort!

The algorithm is very easy to understand. I used C++ due to the lack of updated Java complier on our cluster.

Be careful on the boundaries of each recursion.
      

    void qsort (int col, int left, int right)
          {
              int i = left, j = right;
              vector tmp;
              double pivot = output[(left + right)/2][col];
  
              //sort
              while (i <= j)
              {
                 while (output[i][col] < pivot && i < right)
                 {
                     i++;
                 }
                 while (output[j][col] > pivot && j > left)
                 {
                     j--;
                 }
 
                 if(i <= j)
                 {
                     tmp = output[i];
                     output[i] = output[j];
                     output[j] = tmp;
                     if(i < right)
                         i++;
                     if(j > left)
                         j--;
                 }
              }
             if (left < j)
             {
                 qsort(col,left,j);
             }
             if (i < right)
             {
                 qsort(col,i,right);

             }
         }

No comments:

Post a Comment