72 lines
2.2 KiB
C
72 lines
2.2 KiB
C
/*-----------------------------------------------------------------------------
|
|
* 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) {
|
|
|
|
}
|