-
Notifications
You must be signed in to change notification settings - Fork 0
/
106-bitonic_sort.c
91 lines (81 loc) · 1.93 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include "sort.h"
/**
* swap - Swaps two integers in an array.
* @array: Array of integers.
* @i: First index.
* @j: Second index.
*/
void swap(int *array, size_t i, size_t j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* bitonic_compare - Compares and sorts a bitonic sequence.
* @array: Array.
* @low: Starting index.
* @count: Number of elements to be considered.
* @dir: Direction (1 means increasing, 0 means decreasing).
*/
void bitonic_compare(int *array, size_t low, size_t count, int dir)
{
size_t i, j, k;
for (k = count / 2; k > 0; k /= 2)
{
for (i = low; i < low + count - k; i++)
{
j = i + k;
if ((array[i] > array[j]) == dir)
{
swap(array, i, j);
print_array(array, count);
}
}
}
}
/**
* bitonic_merge - Recursively sorts a bitonic sequence.
* @array: Array.
* @low: Starting index.
* @count: Number of elements to be considered.
* @dir: Direction (1 for increasing, 0 for decreasing).
*/
void bitonic_merge(int *array, size_t low, size_t count, int dir)
{
if (count > 1)
{
size_t k = count / 2;
bitonic_compare(array, low, count, dir);
bitonic_merge(array, low, k, dir);
bitonic_merge(array, low + k, k, dir);
}
}
/**
* bitonic_sort_recursive - Main recursive function for bitonic sort.
* @array: Array.
* @low: Starting index.
* @count: Number of elements to be considered.
* @dir: Direction (1 for increasing, 0 for decreasing).
*/
void bitonic_sort_recursive(int *array, size_t low, size_t count, int dir)
{
if (count > 1)
{
size_t k = count / 2;
bitonic_sort_recursive(array, low, k, 1);
bitonic_sort_recursive(array, low + k, k, 0);
bitonic_merge(array, low, count, dir);
}
}
/**
* bitonic_sort - Sorts an array of integers using bitonic sort algorithm.
* @array: Array of integers.
* @size: Size of the array.
*/
void bitonic_sort(int *array, size_t size)
{
if (!array || size < 2)
return;
bitonic_sort_recursive(array, 0, size, 1);
}