66 lines
No EOL
2 KiB
C
66 lines
No EOL
2 KiB
C
/*-----------------------------------------------------------------------------
|
|
* HTBLA-Leonding
|
|
*-----------------------------------------------------------------------------
|
|
* Exercise Number: S07
|
|
* Title: Insertion sort implementation
|
|
* Author: Marc Tismonar
|
|
*-----------------------------------------------------------------------------
|
|
* Description:
|
|
* Implements the insertion sort algorithm
|
|
*-----------------------------------------------------------------------------
|
|
*/
|
|
|
|
#include "insertion_sort_binary_search.h"
|
|
#include "binary_search.h"
|
|
|
|
/**
|
|
* Sorts the given list according to the insertion sort algorithm using binary.
|
|
*
|
|
* @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 insertion_sort_binsearch_list(IntList list, criterion_fn criterion) {
|
|
if (!list_is_valid(list) || criterion == 0) {
|
|
return;
|
|
}
|
|
|
|
int size = list_get_size(list);
|
|
if (size <= 1) {
|
|
return;
|
|
}
|
|
|
|
for (int i = 1; i < size; i++) {
|
|
int current = list_get_at(list, i);
|
|
|
|
IntList temp = list_obtain();
|
|
for (int k = 0; k < i; k++) {
|
|
list_insert(temp, list_get_at(list, k));
|
|
}
|
|
|
|
int pos = binary_search_list_limited(temp, i, criterion, current);
|
|
|
|
if (pos < 0) {
|
|
pos = -pos;
|
|
}
|
|
|
|
if (pos < i) {
|
|
list_remove_at(list, i);
|
|
list_insert_at(list, pos, current);
|
|
}
|
|
|
|
list_release(&temp);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Sorts the given array according to the insertion sort algorithm using binary search.
|
|
*
|
|
* @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 insertion_sort_binsearch_array(int array[], int length, criterion_fn criterion) {
|
|
|
|
} |