sorting_algorithms/3-quick_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
84
85
86
#include "sort.h"
#include <stddef.h>

/**
 * quick_sort - Sorts an array using the quick sort algorithm.
 * @array: The array to sort.
 * @size: The size of the array.
 *
 * description:  This function sorts the array in ascending order.
 * Return: a void type
 */

void quick_sort(int *array, size_t size)
{
	intermediate_value_for_sorting_here(array, 0, (int)size - 1);
}

/**
 * quick_sort_ - Sorts an array using the quick sort algorithm.
 * @a: The array to sort.
 * @beg: The begining of the array.
 * @end: The end of the array.
 *
 * description -  This function sorts the array in ascending order.
 * Return: a void type
 */
void intermediate_value_for_sorting_here(int *a, int beg, int end)
{
	int loc;

	if (beg < end)
	{
		loc = partition(a, beg, end);
		intermediate_value_for_sorting_here(a, beg, loc - 1);
		intermediate_value_for_sorting_here(a, loc + 1, end);
	}
}

/**
 * partition - a function for the quick sort
 * @a: The array to sort.
 * @beg: The begining of the array.
 * @end: The end of the array.
 *
 * description: partition function
 * Return:  a void type
 */
int partition(int a[], int beg, int end)
{
	int left, right, temp, loc, flag;

	loc = left = beg;
	right = end;
	flag = 0;
	while (flag != 1)
	{
		while ((a[loc] <= a[right]) && (loc != right))
			right--;
		if (loc == right)
			flag = 1;
		else if (a[loc] > a[right])
		{
			temp = a[loc];
			a[loc] = a[right];
			a[right] = temp;
			loc = right;
			print_array(a, (size_t)end);
		}
		if (flag != 1)
		{
			while ((a[loc] >= a[left]) && (loc != left))
				left++;
			if (loc == left)
				flag = 1;
			else if (a[loc] < a[left])
			{
				temp = a[loc];
				a[loc] = a[left];
				a[left] = temp;
				loc = left;
				print_array(a, (size_t)end);
			}
		}
	}
	return (loc);
}