From e05f27daad51b0fa411842cd21a6893c4c01664f Mon Sep 17 00:00:00 2001 From: El-BG-1970 Date: Thu, 4 Nov 2021 14:02:53 +0100 Subject: hybrid sorting algorithm --- agenda_entry.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-) (limited to 'agenda_entry.c') diff --git a/agenda_entry.c b/agenda_entry.c index d3fc466..f21ac2a 100644 --- a/agenda_entry.c +++ b/agenda_entry.c @@ -69,7 +69,24 @@ char *format_entry(entry e) { } void sort_entry_array(entry *arr, int n) { - merge_sort_entry_array(arr, n); + if (n == 1) return; + + merge_sort_entry_array(arr,n); + return; + + int halfway = n/2; + if (n <= 32) { + insertion_sort_entry_array(arr, n); + } else { + if (halfway <= 32) { + insertion_sort_entry_array(arr, halfway); + insertion_sort_entry_array(arr+halfway, n - halfway); + } else { + sort_entry_array(arr, halfway); + sort_entry_array(arr+halfway, n - halfway); + } + merge_entry_array(arr, halfway, n); + } } void merge_sort_entry_array(entry *arr, int n) { @@ -82,6 +99,22 @@ void merge_sort_entry_array(entry *arr, int n) { merge_entry_array(arr, halfway, n); } +void insertion_sort_entry_array(entry *arr, int n) { + if (n == 1) return; + + int j = 0; + entry sw; + for (int i = 1; i < n; i++) { + j = i - 1; + while (j >= 0 && smaller(arr[j+1].date, arr[j].date)) { + sw = arr[j]; + arr[j] = arr[j+1]; + arr[j+1] = sw; + j--; + } + } +} + void merge_entry_array(entry *arr, int halfway, int n) { int i = 0, j = halfway; -- cgit v1.2.3