QuickSort vs MergeSort, что я делаю не так?

Question

Я пытаюсь реализовать несколько алгоритмов сортировки в Java, чтобы сравнить производительность.Из того, что я прочитал, я ожидал, что quickSort будет быстрее, чем mergeSort, но в моем коде это не так, поэтому я предполагаю, что должна быть проблема с моим алгоритмом quickSort:

public class quickSortExample{
public static void main(String[] args){
    Random gen = new Random();
    int n = 1000000;
    int max = 1500000;
    ArrayList<Integer> d = new ArrayList<Integer>();
    for(int i = 0; i < n; i++){
        d.add(gen.nextInt(max));
    }
    ArrayList<Integer> r;
    long start, end;

    start = System.currentTimeMillis();
    r = quickSort(d);
    end = System.currentTimeMillis();
    System.out.println("QuickSort:");
    System.out.println("Time: " + (end-start));
    //System.out.println(display(d));
    //System.out.println(display(r));
}

public static ArrayList<Integer> quickSort(ArrayList<Integer> data){
    if(data.size() > 1){
        int pivotIndex = getPivotIndex(data);
        int pivot = data.get(pivotIndex);
        data.remove(pivotIndex);
        ArrayList<Integer> smallers = new ArrayList<Integer>();
        ArrayList<Integer> largers = new ArrayList<Integer>();
        for(int i = 0; i < data.size(); i++){
            if(data.get(i) <= pivot){
                smallers.add(data.get(i));
            }else{
                largers.add(data.get(i));
            }
        }
        smallers = quickSort(smallers);
        largers = quickSort(largers);
        return concat(smallers, pivot, largers);
    }else{
        return data;
    }
}

public static int getPivotIndex(ArrayList<Integer> d){
    return (int)Math.floor(d.size()/2.0);
}

public static ArrayList<Integer> concat(ArrayList<Integer> s, int p, ArrayList<Integer> l){
    ArrayList<Integer> arr = new ArrayList<Integer>(s);
    arr.add(p);
    arr.addAll(l);

    return arr;
}

public static String display(ArrayList<Integer> data){
    String s = "[";
    for(int i=0; i < data.size(); i++){
        s += data.get(i) + ", ";
    }
    return (s+"]");
}

}

Results (on1 миллион целых чисел от 0 до 1500000):

mergeSort (реализовано также с arrayList): 1,3 с (в среднем) (0,7 с с int [] вместо)

quickSort: 3 с (в среднем)

Это просто плохой выбор моего пивота или в алгоритме тоже есть какие-то недостатки.

Кроме того, есть более быстрый способ кодировать его с помощью int [] вместо ArrayList()?(Как вы объявляете размер массива для массивов больших и меньших размеров?)

PS: Теперь я могу реализовать его на месте, чтобы он занимал меньше памяти, но это не главноеthis.

EDIT 1: я заработал 1 сек, изменив метод concat.Спасибо!

Answer 1

PS: Теперь я могу реализовать его на месте, чтобы он занимал меньше памяти, но суть не в этом.

Это не просто использовать меньшеобъем памяти.Вся эта дополнительная работа, которую вы выполняете в рутине «concat» вместо правильной быстрой сортировки на месте, почти наверняка стоит так дорого.Если вы все равно можете использовать дополнительное пространство, вы всегда должны кодировать сортировку слиянием, потому что она будет иметь тенденцию делать меньше сравнений, чем QuickSort.сделать еще один проход по подспискам, делая больше сравнений.Если вы произвели обмен на месте, все в одном массиве, то после того, как вы приняли решение об обмене двумя местами, вы не примете решение снова.

Answer 2

Я думаю, что главная проблема с вашей быстрой сортировкой, как вы говорите, заключается в том, что она не выполнена на месте.

Два главных виновника - smallers и largers.Размер по умолчанию для ArrayList равен 10. При первоначальном вызове quickSort хорошая сводка будет означать, что мелкие и крупные увеличатся до 500 000.Поскольку ArrayList только удваивается в размере, когда он достигает емкости, его размер нужно будет изменить примерно в 19 раз.

Поскольку вы создаете новый размер меньше и больше с каждым уровнем рекурсии, который вы собираетесь выполнять примерно на 2* (19 + 18 + ... + 2 + 1) изменяет размер.Это примерно 400 изменяет размеры объектов ArrayList, которые должны быть выполнены до того, как они будут объединены.Процесс конкатенации, вероятно, выполнит аналогичное количество изменений размера.

В общем, это много дополнительной работы.

Упс, только что заметил data.remove(pivotIndex).Выбранный сводный индекс (середина массива) также будет вызывать дополнительные операции с памятью (даже если середина обычно является лучшим выбором, чем начало или конец или массив).Это значит, что arraylist скопирует весь блок памяти в «правую» часть разворота на один шаг влево в массиве поддержки.

Быстрая заметка о выбранной сводке, поскольку целые числа, которые вы сортируете, равномернораспределяется между n и 0 (если Random соответствует своему названию), вы можете использовать это для выбора хороших опорных точек.То есть первый уровень быстрой сортировки должен выбрать max * 0.5 в качестве своей оси.Для второго уровня с меньшими значениями следует выбрать максимум * 0,25, а для второго уровня с более крупными следует выбрать максимум * 0,75 (и т. Д.).

Answer 3

Основы ООП и структуры данных в Java Ричард Винер, Льюис Дж. Пинсон перечисляет быструю сортировку следующим образом, которая может быть или не быть быстрее (я подозреваю, что это так), чем ваша реализация ...

public static void quickSort (Comparable[] data, int low, int high) {
    int partitionIndex;
    if (high - low > 0) {
        partitionIndex = partition(data, low, high);
        quickSort(data, low, partitionIndex - 1);
        quickSort(data, partitionIndex + 1, high);
    }
}

private static int partition (Comparable[] data, int low, int high) {
    int k, j;
    Comparable temp, p;
    p = data[low]; // Partition element
    // Find partition index(j).
    k = low;
    j = high + 1;

    do {
        k++;
    } while (data[k].compareTo(p) <= 0 && k < high);

    do {
        j--;
    } while (data[j].compareTo(p) > 0);

    while (k < j) {
        temp = data[k];
        data[k] = data[j];
        data[j] = temp;

        do {
            k++;
        } while (data[k].compareTo(p) <= 0);

        do {
            j--;
        } while (data[j].compareTo(p) > 0);
    }
    // Move partition element(p) to partition index(j).
    if (low != j) {
        temp = data[low];
        data[low] = data[j];
        data[j] = temp;
    }
    return j; // Partition index
}

Answer 4

Я думаю, что ваш алгоритм довольно неэффективен, потому что вы используете промежуточные массивы = больше памяти + больше времени для выделения / копирования. Вот код на C ++, но идея та же: вы должны поменять местами элементы, а не копировать их в другие массивы

template<class T> void quickSortR(T* a, long N) {

  long i = 0, j = N;        
  T temp, p;

  p = a[ N/2 ];     


  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );



  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

Answer 5

Технически, Mergesort имеет лучшее временное поведение ( Θ (nlogn) наихудший и средний случаи), чем Quicksort ( Θ (n ^ 2) наихудший случай, Θ(nlogn) средний регистр).Так что вполне возможно найти входы, для которых Mergesort превосходит Quicksort.В зависимости от того, как вы выбираете свои опорные точки, вы можете сделать наихудший случай редким.Но для простой версии Quicksort в «наихудшем случае» будут отсортированы (или почти отсортированы) данные, что может быть довольно распространенным вводом.

Вот что Википедия говорит о двух:

В типичных современных архитектурах эффективные реализации быстрой сортировки обычно превосходят сортировку слиянием для сортировки массивов на основе ОЗУ.С другой стороны, сортировка слиянием является стабильной сортировкой, она лучше распараллеливается и более эффективна при обработке медленных последовательных носителей с медленным доступом. [Цитата нужна] Сортировка слиянием часто является лучшим выбором для сортировки связанного списка: в этой ситуации этоОтносительно легко реализовать сортировку слиянием таким образом, что она требует только Θ (1) дополнительного пространства, а медленная производительность произвольного доступа связанного списка приводит к тому, что некоторые другие алгоритмы (например, быстрая сортировка) работают плохо, а другие (такие, каккак heapsort) совершенно невозможно.

Answer 6

Я согласен, что причиной является ненужное копирование. Далее следует еще несколько заметок.

Выбор сводного индекса плох, но здесь это не проблема, потому что ваши числа случайны.

(int)Math.floor(d.size()/2.0) эквивалентно d.size()/2.

data.remove(pivotIndex); - это ненужное копирование n/2 элементов. Вместо этого вы должны проверить в следующем цикле i == pivotIndex и пропустить этот элемент. (Ну, то, что вам действительно нужно сделать - это сортировка по месту, но я просто предлагаю простые улучшения.)

Поместить все элементы, равные pivot, в одну (меньшую) часть - плохая идея. Представьте, что происходит, когда все элементы массива равны. (Опять же, не проблема в этом случае.)

for(i = 0; i < s.size(); i++){
    arr.add(s.get(i));
}

эквивалентно arr.addAll(s). И конечно же, ненужное копирование здесь снова. Вы можете просто добавить все элементы из правой части в левую вместо создания нового списка.

(Как вы объявляете размер массива для массивов больших и меньших размеров?)

Я не уверен, правильно ли я вас понял, но вы хотите array.length?

Итак, я думаю, что даже без реализации сортировки на месте вы можете значительно улучшить производительность.