Блог

Мой алгоритм быстрой сортировки терпит неудачу при больших значениях n, и только если массив не является случайным. Я пробовал использовать алгоритм на различных массивах. Он отлично работает, когда я использую случайный массив чисел (для любого значения n), но для массива, который содержит те же значения или значения в порядке возрастания или убывания, он не работает. И это тоже, только когда n примерно превышает 6000. (Это отлично работает, когда n <5000)

Я уже пробовал использовать другую версию quicksort. Тот, который использует цикл while вместо рекурсии, и он работает отлично. И, как я уже говорил, мой алгоритм дает сбой только тогда, когда n больше 6000 для нерандомизированного массива, для 5000 или ниже он работает хорошо.

 void quicksort(int a[], int low, int high) {

        if (low < high) {

            int index = partition(a, low, high); // error 
            quicksort(a, low, index - 1);  // error
            quicksort(a, index   1, high);

        }

    }

int partition(int arr[], int low, int high) {

        int pivot = arr[high];

        int i = low - 1;
        //int j = low;
        for (int j = low; j < high; j  ) {
            // If current element is smaller than or 
            // equal to pivot 
            if (arr[j] <= pivot) {
                i  ;

                // swap arr[i] and arr[j] 
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i   1];
        arr[i   1] = arr[high];
        arr[high] = temp;
        return (i   1);
    }

  

Выше я привел свой алгоритм быстрой сортировки. Тот, который завершается неудачей при n> 6000 (и когда массив не является случайным).

И ниже приведен код, который работал для всех значений n и для любого типа массива.

 

     public void quicksort(int[] data, int low, int high)
   {  // 1 or 0 items are sorted by default
      if(high - low < 1)
         return;

      int left = low;
      int right = high;
      int pivot = data[low   (high - low) / 2];  

      while(left <= right)
      {  // Increment left pointer until left >= pivot
         while(data[left] < pivot)
            left  ;

         // Increment right pointer until right <= pivot
         while(data[right] > pivot)
            right--;

         // If left < right; swap values
         if(left <= right)
         {  int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
            left  ;
            right--;
         }

      }
      // quick_sort 'lesser values'
      quicksort(data, low, right);

      // quick_sort 'greater values'
      quicksort(data, left, high);
   }

       static int partition(int[] array, int low, int high) {
        int j, temp, i = low   1;
        Random random = new Random();
        int x = random.nextInt(high - low)   low;
        temp = array[low];
        array[low] = array[x];
        array[x] = temp;
        for (j = low   1; j <= high; j  ) {
            if (array[j] <= array[low] amp;amp; j != i) {
                temp = array[j];
                array[j] = array[i];
                array[i  ] = temp;
            } else if (array[j] <= array[low]) {
                i  ;
            }
        }
        temp = array[i - 1];
        array[i - 1] = array[low];
        array[low] = temp;
        return i - 1;
    }

  

Терминал показывает ошибку конкретно в двух строках. (Строки, которые я пометил как ошибку в первом методе быстрой сортировки).

Если данные уже упорядочены, то использование arr [high] (или arr[low]) приводит к наихудшим затратам стекового пространства O (n), что приводит к переполнению стека. Во втором примере используется средний элемент (arr[low (high-low) / 2]), который в лучшем случае будет иметь накладные расходы на пространство стека для уже отсортированных данных или данных, уже отсортированных в обратном порядке.

Обходной путь для ограничения накладных расходов на пространство стека значением O (log (n)) заключается в том, чтобы после выполнения разделения проверить, какая часть меньше, и использовать рекурсию только для меньшей части, затем выполнить обратный цикл для обработки большей части (обновите low или high по мере необходимости, чтобы исключить отсортированную меньшую часть перед повторным циклом).

 public static void quicksort(int[] arr, int low, int high)
{
    while (low < high) {
        int index = partition(arr, low, high);
        if((index-low) <= (high-index)){       // avoid stack overflow
            quicksort(arr, low, index - 1);    //
            low = index 1;                     //
        }else{                                 //
            quicksort(arr, index   1, high);   //
            high = index-1;                    //
        }                                      //
    }
}

public static int partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j  ) {
        if (arr[j] <= pivot) {
            i  ;
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    int tmp = arr[i   1];
    arr[i   1] = arr[high];
    arr[high] = tmp;
    return (i   1);
}
  

Если интересно, схема разделения Hoare быстрее:

 public static void qsort(int[] a, int lo, int hi)
{
    while(lo < hi){
        int md = lo (hi-lo)/2;
        int ll = lo-1;
        int hh = hi 1;
        int p = a[md];
        int t;
        while(true){
            while(a[  ll] < p);
            while(a[--hh] > p);
            if(ll >= hh)
                break;
            t     = a[ll];
            a[ll] = a[hh];
            a[hh] = t;
        }
        ll = hh  ;
        if((ll - lo) <= (hi - hh)){
            qsort(a, lo, ll);
            lo = hh;
        } else {
            qsort(a, hh, hi);
            hi = ll;
        }
    }
}