-
Notifications
You must be signed in to change notification settings - Fork 0
/
106-bitonic_sort.c
73 lines (66 loc) · 1.79 KB
/
106-bitonic_sort.c
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
#include <stdio.h>
#include "sort.h"
/**
* compare_swap - Swaps two elements if they're out of order.
* @array: Pointer to the array.
* @i: Index of the first element.
* @j: Index of the second element.
* @dir: Sorting direction (ascending or descending).
**/
void compare_swap(int *array, size_t i, size_t j, int dir)
{
int temp;
if ((array[i] > array[j] && dir == 1) || (array[i] < array[j] && dir == 0))
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
printf("Swapping: %d, %d\n", array[i], array[j]);
}
}
/**
* bitonic_merge - Merges two subarrays into a bitonic sequence.
* @array: Pointer to the array.
* @low: Index of the first element of the first subarray.
* @cnt: Number of elements in each subarray.
* @dir: Sorting direction (ascending or descending).
**/
void bitonic_merge(int *array, size_t low, size_t cnt, int dir)
{
size_t k, i;
if (cnt > 1)
{
k = cnt / 2;
for (i = low; i < low + k; i++)
compare_swap(array, i, i + k, dir);
bitonic_merge(array, low, k, dir);
bitonic_merge(array, low + k, k, dir);
}
}
/**
* bitonic_sort_recursive - Recursively sic sort algorithm.
* @array: Pointer to the array.
* @low: Index of the first element of the subarray.
* @cnt: Number of elements in the subarray.
* @dir: Sorting direction (ascending or descending).
**/
void bitonic_sort_recursive(int *array, size_t low, size_t cnt, int dir)
{
size_t k;
if (cnt > 1)
{
k = cnt / 2;
bitonic_sort_recursive(array, low, k, 1);
bitonic_sort_recursive(array, low + k, k, 0);
bitonic_merge(array, low, cnt, dir);
}
}
/**
* bitonic_sort - Sorts an array using the Bitonic sort algorithm.
* @array: Pointer to the array.
* @size: Number of elements in the array.
**/
void bitonic_sort(int *array, size_t size)
{
bitonic_sort_recursive(array, 0, size, 1);
}