-1

I have an array (3, 8, 10, 6, 15, 20, 16, 4, 18, 9). To get the middle element of the array I need to add the left most index which is 0 and the right most which is 9 (0+9) = 9 then divide 9/2 which then gives me 4. Now the pivot = a[4] which is 15. My problem is that since every element in the array that is left of 15 cant be swapped over since it is less than 15 but there are elements on the right that need to be swapped. I think I'm doing it wrong where I need to swap the elements with the pivot.

user3001301
  • 115
  • 1
  • 2
  • 9
  • 1
    There are some variations, each of which will handle this differently - it could involve swapping the 15 with the first element and then back to the middle, or just ignoring it (moving the left pointer past it) - consult your text book, or a resource of your choice. – Bernhard Barker May 08 '14 at 02:52
  • As the comment above says, there're many ways to handle this. Frequently-used 2 algorithms: Lomuto's Partitioning Algorithm and Hoare's Partitioning Algorithm, see [this answer](http://stackoverflow.com/questions/21358400/c-randomized-pivot-quicksort-improving-the-partition-function/21358567#21358567): – jfly May 08 '14 at 03:16

1 Answers1

0

You can read it here link 

function quicksort(array $arr, $left, $right)
{
    $i = $left;
    $j = $right;
    $separator = $arr[floor(($left + $right) / 2)];

    while ($i <= $j) {
        while ($arr[$i] < $separator) {
            $i++;
        }

        while($arr[$j] > $separator) {
            $j--;
        }

        if ($i <= $j) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $tmp;
            $i++;
            $j--;
        }
    }

    if ($left < $j) {
        $arr = quicksort($arr, $left, $j);
    }

    if ($right > $i) {
        $arr = quicksort($arr, $i, $right);
    }

    return $arr;
}

// Example:
$arr = array(3, 8, 10, 6, 15, 20, 16, 4, 18, 9);
$result = quicksort($arr, 0, (sizeof($arr)-1));
print_r($result);
amla
  • 79
  • 2
  • 11