D
D
Dreaded2018-05-14 16:43:55
PHP
Dreaded, 2018-05-14 16:43:55

Where is the error in the implementation of QuickSort?

I'm trying to implement the QuickSort sorting algorithm myself. I've been sitting here for an hour and I can't figure out what I'm doing wrong here?

function quicksort(&$array, $first, $last) {
  
  $left = $first;
  $right = $last;
  $pivot = $array[rand($first, $last)];

  do {
    while($array[$left] < $pivot)
      $left++;
    
    while($array[$right] > $pivot)
      $right--;
    
    if ($left <= $right) {
      $temp = $array[$left];
      $array[$left] = $array[$right];
      $array[$right] = $temp;
      $left++;
      $right--;
    }
  }
  while ($left <= $right);

  quicksort($array, $first, $right);
  quicksort($array, $left, $last);
}

Answer the question

In order to leave comments, you need to log in

1 answer(s)
R
Roman, 2018-05-14
@Dreaded

Your conditions are not checked

quicksort($array, $first, $right);
quicksort($array, $left, $last);

But you must
if ($r > $left) {
//Если условие true, совершаем рекурсию
//Передаем массив, исходное начало и текущий конец
my_sort($array, $left, $r); 
}

if ($l < $right) {
//Если условие true, совершаем рекурсию
//Передаем массив, текущие начало и конец
my_sort($array, $l, $right);
}

https://habr.com/sandbox/33297/

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question