Быстрая сортировка неправильно сортирует массив длинных значений - PullRequest
Новая
       50

Быстрая сортировка неправильно сортирует массив длинных значений

0 голосов
/ 08 апреля 2019

Я пытаюсь реализовать алгоритм быстрой сортировки для сортировки массива, определенного как long * array.Он сортирует большинство значений, но не все.Я чувствую, что должна быть проблема с диапазоном используемых значений, но я не могу ее идентифицировать. 

void swap(long *a, long *b)
{
    long temp = *a;
    *a = *b;
    *b = temp;
}

long partition(long * arr, long low, long high) {
  long pivot = arr[high];
  long i = low;
  for (long j = low; j < (high - 1); j++) {
    if (arr[j] < pivot) {
      swap(&arr[i], &arr[j]);
      i++;
    }
  }
  swap(&arr[i], &arr[high]);
  return i;
}

void quickSort(long * arr, long low, long high) {
  if (low < high) {
    long p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
  }
}

Я звоню quickSort с quickSort(array, 0, size - 1).Вот вывод при сортировке случайного массива из 15 длинных значений: 

-482641087233232037
-3864131317804163752
-3090751678944217314
-2010933995968724040
1597984395262413786
2533582178445507721
2959320811908600883
5433974314367983925
-8110790053026736838
4549802945312878540
2821133411822490835
-2345840024589719123
606083409223366793
-4897849740314804917
-8410623358012228580

Starting quicksort.

-8410623358012228580
-3090751678944217314
-3864131317804163752
-2345840024589719123
-2010933995968724040
-8110790053026736838
-482641087233232037
606083409223366793
1597984395262413786
2821133411822490835
2533582178445507721
2959320811908600883
4549802945312878540
5433974314367983925
-4897849740314804917
...