/*-----------------------------------------------------------------------------
 *				HTBLA-Leonding
 *-----------------------------------------------------------------------------
 * Exercise Number: S07
 * Title:			Quick sort implementation
 * Author:			Marc Tismonar
 *-----------------------------------------------------------------------------
 * Description:
 * Implements the quick sort algorithm
 *-----------------------------------------------------------------------------
*/

#include "quick_sort.h"

/* LIST VARIANT */

static int partition_list(IntList list, int low, int high, criterion_fn criterion) {
    int pivot_value = list_get_at(list, high);
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (criterion(list_get_at(list, j), pivot_value)) {
            i++;
            list_swap(list, i, j);
        }
    }
    list_swap(list, i + 1, high);
    return (i + 1);
}

static void quick_sort_list_helper(IntList list, int low, int high, criterion_fn criterion) {
    if (low < high) {
        int pivot_idx = partition_list(list, low, high, criterion);

        quick_sort_list_helper(list, low, pivot_idx - 1, criterion);
        quick_sort_list_helper(list, pivot_idx + 1, high, criterion);
    }
}

/**
 * Sorts the given list according to the quick sort algorithm.
 * 
 * @param list The list to be sorted.
 * @param criterion The pointer to the function that implements the sorting criterion.
 * That function accepts two integer parameters and returns a boolean value.
 */
void quick_sort_list(IntList list, criterion_fn criterion) {
    if (!list_is_valid(list) || criterion == 0) {
        return;
    }
    
    int size = list_get_size(list);
    if (size <= 1) {
        return;
    }
    
    quick_sort_list_helper(list, 0, size - 1, criterion);
}

/* ARRAY VARIANT */

/**
 * Sorts the given array according to the quick sort algorithm.
 * 
 * @param array The array to be sorted.
 * @param length The length of the array.
 * @param criterion The pointer to the function that implements the sorting criterion.
 * That function accepts two integer parameters and returns a boolean value.
 */
void quick_sort_array(int array[], int length, criterion_fn criterion) {
    
}