Как исправить алгоритм быстрой сортировки для больших значений n? (а когда массив не случайный)

Question

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

Я уже пробовал использовать другую версию быстрой сортировки. Тот, который использует цикл 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] && 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;
    }

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

Answer 1

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

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

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