Quicksort не работает

Question

Это все мой код для моего метода quicksort, он работает с набором из 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

Допущение:

• держит 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

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

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

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

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

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