Dual-Pivot QuickSort

Question

I am trying to use a dual-pivot quickSort algorithm to make a list of numbers from a text file sort in descending order. I currently have it in ascending and can't figure out how to switch it. Below is the code to get it to sort ascending. I think it is just a sign somewhere but i'm not sure where.

private void quickSort(int[] A, int left, int right){
    int temp;
    if(right-left>=1){
        int lp = A[left];
        int rp = A[right];
        if(lp>rp){
            temp = lp;
            lp = rp;
            rp = temp;

            temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }
        int l = left+1;
        int g = right-1;
        int k = l;
        while(k<=g){
            if(A[k]<lp){
               temp = A[k];
               A[k] = A[l];
               A[l] = temp;
                l++;
            }
            else{
                if(A[k]>rp){
                    while(A[g]>lp && k<g)
                        g--;
                    temp = A[k];
                    A[k]= A[g];
                    A[g] = temp;
                    g--;
                    if(A[k]<lp){
                        temp = A[k];
                        A[k] = A[l];
                        A[l] = temp;
                        l++;
                    }

                }
            }
            k++;
        }
        l--;
        g++;
        temp = A[left];
        A[left] = A[l];
        A[l] = temp;

        temp = A[right];
        A[right] = A[g];
        A[g] = temp;
        quickSort(A,left,l-1);
        quickSort(A,l+1,g-1);
        quickSort(A,g+1,right);
    }

}

score 0 · Answer 1 · answered Oct 18 '19 at 12:36

I tried to adjust your code to make it a descending order sorting but couldn't succeed. However I wrote a DualPivot QuickSort which you can change the order so easily. Here is the code. It is Descending order, to change the order just follow the comment inside the code. This code is much simple and organised.

public class DualPivotQS
{

   private static void sort(int[] a, int lo, int hi)
   {
      if (hi <= lo)
         return;
      int lt = lo, gt = hi;
      int v = a[lo];
      int i = lo + 1;
      while (i <= gt)
      {

         if (v > a[i])          //   change here to change order
            swap(a, lt++, i++);
         else if (v < a[i])     //   change here to change order
            swap(a, i, gt--);
         else
            i++;
      }

      // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
      sort(a, lo, lt - 1);
      sort(a, gt + 1, hi);

   }

   private static void swap(int[] a, int i, int j)
   {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
   }

   public static void main(String[] args)
   {
      int[] num = { 5, 5, 0, 1, 7, 2, 99, 23, 56, 44, 32, 104, 4, 7, 8, 2, 7 };

      sort(num, 0, num.length - 1);

      for (int i = 0; i < num.length; i++)
         System.out.print(num[i] + ", ");

   }
}

Reference: https://algs4.cs.princeton.edu/23quicksort/

Dual-Pivot QuickSort

1 Answers1