-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpancakeSort_generic.c
More file actions
104 lines (86 loc) · 2.84 KB
/
pancakeSort_generic.c
File metadata and controls
104 lines (86 loc) · 2.84 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#define length_of_array(array) sizeof(array) / sizeof(array[0])
// #define DEBUG
#if defined DEBUG
static int reverse_times = 0;
#endif
// #define REC_IMP
#ifndef REC_IMP
#define NO_REC_IMP
#endif
// generic
int reverse_array(void *array, size_t len, size_t elem_byte_size,
int (*swap_function)(const void *a, const void *b)) {
size_t i;
for (i = 0; i < len / 2; i++) {
swap_function(((char *)array + i * elem_byte_size),
((char *)array + (len - i - 1) * elem_byte_size));
}
return 0;
}
// generic
int find_max_elem(void *array, size_t len, size_t elem_byte_size,
int (*compare_function)(const void *a, const void *b)) {
size_t max_elem = 0;
size_t i;
for (i = 0; i < len; i++) {
if (compare_function((char *)array + max_elem * elem_byte_size,
(char *)array + i * elem_byte_size) < 0) {
max_elem = i;
}
}
return max_elem;
}
int compare_int(const void *a, const void *b) { return *(int *)a - *(int *)b; }
int swap_int(const void *a, const void *b) {
int temp = *(int *)a;
*(int *)a = *(int *)b;
*(int *)b = temp;
return 0;
}
#if defined NO_REC_IMP
// generic
int pancakeSort(void *unsorted_array, size_t len, size_t elem_byte_size,
int (*compare_function)(const void *a, const void *b),
int (*swap_function)(const void *a, const void *b)) {
size_t max_elem;
size_t unsorted_len = len;
for (; unsorted_len > 0; unsorted_len--) {
max_elem = find_max_elem(unsorted_array, unsorted_len, elem_byte_size,
compare_int);
reverse_array(unsorted_array, max_elem + 1, elem_byte_size, swap_int);
reverse_array(unsorted_array, unsorted_len, elem_byte_size, swap_int);
}
return 0;
}
#endif
#if defined REC_IMP
// generic
int pancakeSort(void *unsorted_array, size_t len, size_t elem_byte_size,
int (*compare_function)(const void *a, const void *b),
int (*swap_function)(const void *a, const void *b)) {
if (len == 1) {
return 0;
}
size_t max_elem =
find_max_elem(unsorted_array, len, elem_byte_size, compare_function);
reverse_array(unsorted_array, max_elem + 1, elem_byte_size, swap_function);
reverse_array(unsorted_array, len, elem_byte_size, swap_function);
pancakeSort(unsorted_array, len - 1, elem_byte_size, compare_function,
swap_function);
return 0;
}
#endif
int main() {
int array1[] = {5, 2, 1, 0, 3, 2, 9}; // {5,2,1,0,3,2*,9} => {0,1,2,2*,3,5,9}
size_t i;
printf("before sort: ");
for (i = 0; i < length_of_array(array1); i++)
printf("%d ", array1[i]);
printf("\n");
pancakeSort(array1, length_of_array(array1), sizeof(int) / sizeof(char),
compare_int, swap_int);
printf("after sort: ");
for (i = 0; i < length_of_array(array1); i++)
printf("%d ", array1[i]);
}