Quick Sort Iterative

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

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

static 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);
}

static void QuickSortIterative(int* data, int count) {
	int startIndex = 0;
	int endIndex = count - 1;
	int top = -1;
	int* stack = new 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;
		}
	}

	delete stack;
}

Example

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

Output