Быстрая сортировка не работает

Question

Это весь мой код для моего метода быстрой сортировки, он работает с набором из 21 числа, но не с моим реальным набором данных, который составляет около 100000.Я понятия не имею, что не так, я возился два часа, и это скоро должно произойти!Любая помощь была бы очень кстати

public static void hybridQuicksort( int[] a, int start, int end )
{
    final int MIN = 13;
    if ( end - start >= MIN )
    {
        int pivot = findPivot( a, start, end );
        pivot = partition ( a, start, end, pivot );
        hybridQuicksort( a, start, pivot - 1 );
        hybridQuicksort( a, pivot + 1, end);
    }
    else
    {
        insertionSort( a, start, end );
    }
}

//partitions the array based on the pivot
public static int partition( int[] a, int start, int end, int pivot )
{
    int up = start + 1;
    int down = end;

    while ( up <= down )
    {

        while ( a[up] <= pivot)
            up++;

        while ( a[down] > pivot)
            down--;

        if ( up <= down )
            swap( a, up, down );
    }

    swap( a, start, down );

    return up;
}

//finds the first, middle, middle of first and middle, middle of middle and last
//and last numbers and sets their median as the pivot
public static int findPivot( int[] a, int start, int end )
{
    //swap the 4 numbers to the start of the array, leaving the first as is
    swap( a, start + 1, end - 1 );
    swap( a, start + 2, (start + end) / 2);
    swap( a, start + 3, end / 4);
    swap( a, start + 4, (end / 2) + (end / 4) );

    //sort the 5 numbers
    insertionSort( a, 0, 5 );

    //swap the median to the front, that's the pivot
    swap( a, start, start + 2 );
    //return the pivot
    return a[start];
}

Answer 1

Предположение:

• a вмещает 10 000 образцов,
• старт составляет 500

• конец равен 1000

  //swap the 4 numbers to the start of the array, leaving the first as is
  swap( a, start + 1, end - 1 );
  swap( a, start + 2, end / 2);
  swap( a, start + 3, end / 4);
  swap( a, start + 4, (end / 2) + (end / 4) );
  

конец /4 равен 250

.. вы меняете местами значения из-за пределов вашего сортировочного подмножества.

Answer 2

Это не похоже на проблему с домашним заданием.Если бы это была домашняя задача, автор написал бы от семи до десяти строк кода с доказательством эффективности и сдал бы его.Этот парень пытается быть модным, и это кусает его за зад.Вы можете сказать это по тому, как он переходит к сортировке по вставке для так называемых "малых" интервалов.(Подсказка:размер порогового интервала составляет более половины размера тестовых данных.Дайте вашему алгоритму немного места для повторения, если вы хотите хорошо его протестировать.) Во-вторых, он проделывает дополнительную работу, чтобы найти идеальный стержень.Такого рода сложность сопряжена с определенными издержками.

Это любитель за работой.То, что ему нужно, - это не просто ответ.Ему нужен подход к решению сложных проблем.Быстрая сортировка - это всего лишь средство для такого обучения.

Вот мой подход.

Хитрость заключается в том, чтобы написать Quicksort как Quicksort, заставить его работать, а затем беспокоиться о необычных специальных трюках.Уберите шум о сортировке вставок с небольшими интервалами.Просто предположите, что любой интервал размером ноль или единица уже отсортирован (что является вашим базовым вариантом), а затем поработайте над тем, чтобы ваш код секционирования работал, используя левый конец интервала в качестве точки опоры (как в классической оригинальной быстрой сортировке), и вы могли бы рассмотреть возможность печати результатов ваших данных после одного прохода секционирования, чтобы показать себе, что это работает.Таким образом, вы разовьете навыки тестирования.В любом случае, как только у вас будет работающая быстрая сортировка, вы сможете выполнять такие вещи, как отдельный выбор pivot в функции и играть с реализацией.

Удачи и наслаждайтесь своим проектом.Однако не забывай:Нам нужны тайминги, и особенно сравнения времени с процедурой сортировки в стандартной библиотеке!