Dual-Pivot QuickSort - PullRequest
Новая
       21

Dual-Pivot QuickSort

0 голосов
/ 17 октября 2019

Я пытаюсь использовать алгоритм быстрой сортировки с двойным поворотом, чтобы составить список чисел из текстового файла, отсортированного по убыванию. В настоящее время у меня есть это в порядке возрастания и не могу понять, как это переключить. Ниже приведен код для сортировки по возрастанию. Я думаю, что это просто знак где-то, но я не уверен, где. 

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);
    }

}

1 Ответ

0 голосов
/ 18 октября 2019

Я пытался настроить ваш код, чтобы сделать его сортировку по убыванию, но не удалось. Однако я написал QuickSort DualPivot, который вы можете изменить порядок так легко. Вот кодЭто нисходящий порядок, чтобы изменить порядок, просто следуйте комментарию внутри кода. Этот код очень прост и организован. 

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] + ", ");

   }
}

Ссылка: https://algs4.cs.princeton.edu/23quicksort/

...