Quicksort не работает с массивом больше 100 - PullRequest
Новая
       40

Quicksort не работает с массивом больше 100

1 голос
/ 04 июня 2019

Я пытался реализовать нормальный негибридный алгоритм быстрой сортировки, и он работает для массивов размером до 100 полей.Я получаю исключение «переполнение стека», с которым большинство из вас, вероятно, знакомы.Вот мой исходный код: 

import java.util.Arrays;

public class Quicksort {

    public int[] zahlenliste;

    public Quicksort(int[] zahlenliste) {
        sort(zahlenliste);
    }

    public void sort(int[] zahlenliste) {

        if (zahlenliste == null || zahlenliste.length == 0) {
            return;
        }

        this.zahlenliste = zahlenliste;

        quickSort(0, zahlenliste.length - 1);
    }

    public void quickSort(int begin, int end) {
        if (begin >= end) {
            return;
        }
        int lower = begin;
        int higher = end;

        // Choose a pivot
        // int pivot = zahlenliste[lower + (higher - lower) / 2];

        int pivot = zahlenliste[lower + (higher - lower) / 2];

        while (lower <= higher) {
            while (zahlenliste[lower] < pivot) {
                lower++;
            }
            while (zahlenliste[higher] > pivot) {
                higher--;
            }
            if (lower < higher) {
                swap(zahlenliste, lower, higher);
            }

            lower++;
            higher--;
        }

        if (begin < higher) {
            quickSort(begin, lower);
        }

        if (lower < end) {
            quickSort(lower, end);
        }

    }

    public static int[] swap(int[] zahlenliste, int begin, int end) {
        int temp = zahlenliste[begin];
        zahlenliste[begin] = zahlenliste[end];
        zahlenliste[end] = temp;
        return zahlenliste;

    }

}

Я знаю, что есть реализации быстрой сортировки, где вы выбираете более подходящий стержень методом медианы-три или используете сортировку вставкой со списками меньше 10. Однако я хочу реализовать всеиз них сравнивать их на огромных массивах.Поэтому было бы неплохо, если бы у кого-нибудь было решение заставить простую быструю сортировку сортировать большие массивы.

1 Ответ

1 голос
/ 04 июня 2019

Исправления, отмеченные в комментариях 

    public void quickSort(int begin, int end) {
        if (begin >= end) {
            return;
        }
        int lower = begin;
        int higher = end;

        int pivot = zahlenliste[lower + (higher - lower) / 2];

        while (lower <= higher) {
            while (zahlenliste[lower] < pivot) {
                lower++;
            }
            while (zahlenliste[higher] > pivot) {
                higher--;
            }
            if (lower <= higher) {                  // fix
                swap(zahlenliste, lower, higher);
                lower++;                            // fix
                higher--;                           // fix
            }
        }

        if (begin < lower-1) {                      // fix
            quickSort(begin, lower-1);              // fix
        }

        if (lower < end) {
            quickSort(lower, end);
        }
    }

    // fix (void)
    public void swap(int[] zahlenliste, int begin, int end) {
        int temp = zahlenliste[begin];
        zahlenliste[begin] = zahlenliste[end];
        zahlenliste[end] = temp;
    }

Пример обычной быстрой сортировки на основе разделов Hoare. Он также использует рекурсию только для меньшего (или равного по размеру) раздела, а затем переходит к началу цикла для большего (или равного по размеру) раздела: 

    public static void qsort(long[] a, int lo, int hi)
    {
        while(lo < hi){
            int  md = lo+(hi-lo)/2;
            int  ll = lo-1;
            int  hh = hi+1;
            long p = a[md];
            long 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++;
            // only use recursion on smaller partition,
            // then loop back for larger partition
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }
...