-
Notifications
You must be signed in to change notification settings - Fork 2
/
107-quick_sort_hoare.c
83 lines (78 loc) · 1.4 KB
/
107-quick_sort_hoare.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
#include "sort.h"
/**
* swap - swap two int
* @a: int
* @b: int
* Return: (void) Swaped int
*/
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
/**
* partition - Partition an array and using pivot
* @array: Array
* @low: int
* @high: int
* @size: size of array (size_t)
* Return: index of pivote (int)
*/
int partition(int *array, int low, int high, size_t size)
{
int pivot = array[high];
int i = low, j = high;
while (1)
{
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i < j)
{
swap(&array[i], &array[j]);
print_array(array, size);
i++;
j--;
}
else
{
if (i != j)
return (j);
return (j - 1);
}
}
}
/**
* hoare_qsort - Sorting Recursively an Array
* @array: Array to be sorted
* @low: The lowest value of the array
* @high: highest value of the array
* @size: Size of The Array
* Return: void
*/
void hoare_qsort(int *array, int low, int high, size_t size)
{
int i;
if (low < high)
{
i = partition(array, low, high, size);
if (i > low)
hoare_qsort(array, low, i, size);
hoare_qsort(array, i + 1, high, size);
}
}
/**
* quick_sort_hoare - Quick Sort Algorithme using hoare partition
* @array: Array to sort
* @size: Size of The Array
* Return: Sorted Array (void)
*/
void quick_sort_hoare(int *array, size_t size)
{
if (array == NULL || size < 2)
return;
hoare_qsort(array, 0, size - 1, size);
}