#include <stdio.h>

int
partition(int *nums, int low, int high)
{
	int pivot = nums[high];
	int i = low - 1;
	for (int j = low; j < high; ++j) {
		if (nums[j] <= pivot) {
			int tmp = nums[j];
			nums[j] = nums[++i];
			nums[i] = tmp;
		}
	}

	nums[high] = nums[++i];
	nums[i] = pivot;
	return i;
}

int
*quick(int *nums, int low, int high)
{
	if (low >= high) {
		return nums;
	}

	int i = partition(nums, low, high);
	nums = quick(nums, low, i - 1);
	nums = quick(nums, i + 1, high);
	return nums;
}

int
*bubble(int *nums, int len)
{
	for (int i = 0; i < len; ++i) {
		for (int j = i; j < len - 1 - i; ++j) {
			if (nums[j] > nums[j + 1]) {
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}
		}
	}
	return nums;
}

int
main()
{
	int nums[5] = {0, 4, 2, 1, 3};
	int len = sizeof(nums) / sizeof(int);
	/* int *res = bubble(nums, len); */
	int *res = quick(nums, 0, 4);
	for (int i = 0; i < len; ++i) {
		printf("%d\n", res[i]);
	}
	return 0;
}