-
Notifications
You must be signed in to change notification settings - Fork 0
/
3-quick_sort.c
78 lines (73 loc) · 1.55 KB
/
3-quick_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
#include "sort.h"
/**
*swap - the positions of two elements into an array
*@array: array
*@item1: array element
*@item2: array element
*/
void swap(int *array, ssize_t item1, ssize_t item2)
{
int tmp;
tmp = array[item1];
array[item1] = array[item2];
array[item2] = tmp;
}
/**
*lomuto_partition - lomuto partition sorting scheme implementation
*@array: array
*@first: first array element
*@last: last array element
*@size: size array
*Return: return the position of the last element sorted
*/
int lomuto_partition(int *array, ssize_t first, ssize_t last, size_t size)
{
int pivot = array[last];
ssize_t current = first, finder;
for (finder = first; finder < last; finder++)
{
if (array[finder] < pivot)
{
if (array[current] != array[finder])
{
swap(array, current, finder);
print_array(array, size);
}
current++;
}
}
if (array[current] != array[last])
{
swap(array, current, last);
print_array(array, size);
}
return (current);
}
/**
*qs - qucksort algorithm implementation
*@array: array
*@first: first array element
*@last: last array element
*@size: array size
*/
void qs(int *array, ssize_t first, ssize_t last, int size)
{
ssize_t position = 0;
if (first < last)
{
position = lomuto_partition(array, first, last, size);
qs(array, first, position - 1, size);
qs(array, position + 1, last, size);
}
}
/**
*quick_sort - prepare the terrain to quicksort algorithm
*@array: array
*@size: array size
*/
void quick_sort(int *array, size_t size)
{
if (!array || size < 2)
return;
qs(array, 0, size - 1, size);
}