sorting_algorithms/106-bitonic_sort.c at master · Suitret/sorting_algorithms · GitHub

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
#include "sort.h"
#include <stdio.h>
#include <stdlib.h>

/**
 * bitonic_sort - Sorts using bitonic sort algorithm
 *
 * @array: The array to be sorted
 * @size: Number of elements in @array
 */
void bitonic_sort(int *array, size_t size)
{
	if (array && size > 1)
		bitonicSort(array, 0, size, 1, size);
}

/**
 * compAndSwap - Compares and swaps elements
 *
 * @a: The array to be sorted
 * @i: The first index
 * @j: The second index
 * @dir: The direction (1 = ascending & 0 = descending)
 * @size: Number of elements in @array
*/
void compAndSwap(int a[], int i, int j, int dir, int size)
{
	int temp;

	if (dir == (a[i] > a[j]))
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
		print_array(a, size);
	}
}

/**
 * bitonicMerge - Performs merging
 *
 * @a: The array to be sorted
 * @low: The starting index
 * @cnt: The number of elements to be sorted
 * @dir: The direction (1 = ascending & 0 = descending)
 * @size: Number of elements in @a
*/
void bitonicMerge(int a[], int low, int cnt, int dir, int size)
{
	int i, k;

	if (cnt > 1)
	{
		k = cnt / 2;
		for (i = low; i < low + k; i++)
			compAndSwap(a, i, i + k, dir, size);

		bitonicMerge(a, low, k, dir, size);
		bitonicMerge(a, low + k, k, dir, size);
	}
}

/**
 * bitonicSort - Performs merging
 *
 * @a: The array to be sorted
 * @low: The starting index
 * @cnt: The number of elements to be sorted
 * @dir: The direction (1 = ascending & 0 = descending)
 * @size: Number of elements in @a
*/
void bitonicSort(int a[], int low, int cnt, int dir, int size)
{
	int k;

	if (cnt > 1)
	{
		k = cnt / 2;
		bitonicSort(a, low, k, 1, size);
		bitonicSort(a, low + k, k, 0, size);
		bitonicMerge(a, low, cnt, dir, size);
	}
}