Quick Sort Iterative

Quick sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

									void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int Partition(int* data, int left, int right)
{
	int x = data[right];
	int i = (left - 1);

	for (int j = left; j <= right - 1; ++j)
	{
		if (data[j] <= x)
		{
			++i;
			Swap(&data[i], &data[j]);
		}
	}

	Swap(&data[i + 1], &data[right]);

	return (i + 1);
}

void QuickSortIterative(int* data, int count) {
	int startIndex = 0;
	int endIndex = count - 1;
	int top = -1;
	int* stack = (int*)malloc(sizeof(int) * count);

	stack[++top] = startIndex;
	stack[++top] = endIndex;

	while (top >= 0)
	{
		endIndex = stack[top--];
		startIndex = stack[top--];

		int p = Partition(data, startIndex, endIndex);

		if (p - 1 > startIndex)
		{
			stack[++top] = startIndex;
			stack[++top] = p - 1;
		}

		if (p + 1 < endIndex)
		{
			stack[++top] = p + 1;
			stack[++top] = endIndex;
		}
	}

	free(stack);
}

Example

									int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
QuickSortIterative(data, 7);

Output