Я немного растерялся.Я пытался проверить быструю сортировку, и все, кажется, работает нормально, за исключением того, что, когда у меня много повторяющихся элементов массива, я получаю неожиданный результат.
- Код фактически сортирует массив.
- Код фактически сортирует массив в течение периода времени, который ожидается от быстрой сортировки.
- Когда массив сортируется илив обратном порядке я получаю ожидаемую неэффективность (это, конечно, когда в качестве основного элемента задан первый элемент)
- Я использую метод Random library
nextInt для заполнения массива.
Когда я уменьшаю диапазон данных (который, следовательно, помещает больше дубликатов в массив), быстрая сортировка выполняется быстрее.
1 миллион элементов (диапазон 0–1 миллион): 155 мс
1 миллион элементов (диапазон 0–2): 118 мс
30 миллионов элементов (диапазон 0–1 миллион): 3085 мс
30 миллионов элементов (диапазон 0-2): 1021 мс
Я пробовал это много раз, так что не похоже, что это из-за рандомизации.Разница становится еще смелее с большими данными.
Я не смог найти объяснения, почему это может произойти.
Вот мой код:
public void qsort2median(int array [], int lowest, int highest)
{
int pivot = array[(lowest+highest)/2];
int left = lowest;
int right = highest;
while (left <= right){
while (array[left] < pivot){
left ++;
}
while (array[right] > pivot){
right--;
}
if (left <= right){
int temp = array [left];
array[left] = array[right];
array[right] = temp;
left ++;
right--;
}
}
if (lowest < right) {
qsort2median(array, lowest, right);
}
if (left < highest) {
qsort2median(array, left, highest);
}
}
и вот как я его запускаю:
int [] arraytest = new int [1000000];
int [] arraytest1 = new int [1000000];
Quicksort qsorttest = new Quicksort();
qsorttest.randomArrayGenerator(arraytest,2);
System.arraycopy(arraytest,0,arraytest1,0,arraytest.length);
int endpoint = arraytest.length-1;
//RUN FIRST ARRAY
long startTime = System.currentTimeMillis();
qsorttest.qsort2median(arraytest,0,endpoint);
long endTime = System.currentTimeMillis();
long duration = (endTime - startTime);
System.out.println("Quicksort with Median Element pivot ran in: " + duration);
и вот мой randomArrayGenerator метод:
void randomArrayGenerator(int [] array, int n){
Random generator = new Random();
System.out.println();
System.out.println(array.length);
for (int i = 0; i < array.length; i++){
array[i]= generator.nextInt(n);
}
}
Спасибо за любой вклад.
По состоянию на понедельник я все еще пытаюсь это выяснить.