<?php

/**
 * Verwisselt twee elementen in een array. De waarde op plek $index1 wordt
 * verwisseld met de waarde op plek $index2
 * 
 * @param array   $array  De array
 * @param int     $index1 De index van het eerste te verwisselen element
 * @param int     $index2 De index van het tweede te verwisselen element
 * 
 * @author Uitgeverij Instruct
 * 
 */ 
function swap(array &$array, int $index1, int $index2) : void {
  $temp = $array[$index2];
  $array[$index2] = $array[$index1];
  $array[$index1] = $temp;
}

/**
 * Voert partitionering uit op een deellijst van $list, 
 * vanaf start_index tot en met end_index.
 * 
 * Bij deze partitionering wordt eerst een pivot gekozen
 * Daarna worden alle elementen die kleiner zijn dan of gelijk aan de pivot
 * links daarvan geplaatst. En alle elementen groter dan de pivot worden
 * rechts ervan geplaatst.
 * 
 * @param  array  $list        Een array met getallen
 * @param  int    $start_index De index van het eerste te verwisselen element
 * @param  int    $end_index   De index van het tweede te verwisselen element
 * 
 * @return int    De index van de pivot
 * 
 * @author Uitgeverij Instruct
 * 
 */ 
function partition(array &$list, int $start_index, int $end_index) : int {
    $pivot = $list[$start_index];
    $border_index = $start_index + 1;
    for($i = $border_index; $i <= $end_index; $i++) {
        if($list[$i] <= $pivot) {
            swap($list, $i, $border_index);
            $border_index++;
        }
    }
    swap($list, $start_index, $border_index - 1);
    return $border_index - 1;
}

/**
 * Sorteert een array met getallen met QuickSort
 * 
 * @param  array  $list         Een array met getallen
 * @param  int    $start_index  De ondergrens (index) van het te sorteren deel van de array
 * @param  int    $end_index    De bovengrens (index) van het te sorteren deel van de array
 * 
 * @return int    De index van de pivot
 * @throws Exception "index out of bounds" als ingevoerde grenzen fout zijn
 * 
 * @author Uitgeverij Instruct
 * 
 */ 
function quick_sort(array &$list, int $start_index = 0, int $end_index = -1) : void {
    //Controleer de invoer
    $size = count($list);
    if($end_index === -1) { 
        $end_index = $size - 1; 
    }
    
    if($start_index < 0 || $end_index >= $size || $start_index > $end_index) {
        throw new Exception("index out of bounds");
    }
        
    //Het stopcriterium
    if($end_index === $start_index){ 
        return;
    }
    
    //Voer partitie uit op basis van pivot
    $pivot_index = partition($list, $start_index, $end_index);
    
    //Als er nog een lijst links van de pivot over is: sorteer deze
    if($start_index < $pivot_index - 1) { 
        quick_sort($list, $start_index, $pivot_index - 1);
    }
    //Als er nog een lijst rechts van de pivot over is: sorteer deze
    if($pivot_index + 1 < $end_index) {
        quick_sort($list, $pivot_index + 1, $end_index);
    }
}

//Test
$list1 = array(3,4,1,2,7,3,9,5);
quick_sort($list1);
print_r($list1);