Introduction
I found lots of samples online having quick sort with recursion but didn't find any algorithm having quick sort without recursion. This article will help you understand quick sort without recursion.
Using the Code
The following code shows quick sort without recursion. This has been implemented using stack concept LIFO.
using System;
using System.Collections.Generic;
using System.Text;
namespace QuickSort
{
class Program
{
public static void Main(string[] args)
{
int[] arr = { 4, 3,2, 1, -1, 99, 12, 33, 99, 10};
q_sort(ref arr);
foreach (int i in arr)
{
Console.WriteLine(i);
}
}
public static void q_sort(ref int[] input)
{
System.Collections.Stack stack = new System.Collections.Stack();
int pivot;
int pivotIndex = 0;
int leftIndex = pivotIndex + 1;
int rightIndex = input.Length - 1;
stack.Push(pivotIndex);
stack.Push(rightIndex);
int leftIndexOfSubSet, rightIndexOfSubset;
while (stack.Count > 0)
{
rightIndexOfSubset = (int)stack.Pop();
leftIndexOfSubSet = (int)stack.Pop();
leftIndex = leftIndexOfSubSet + 1;
pivotIndex = leftIndexOfSubSet;
rightIndex = rightIndexOfSubset;
pivot = input[pivotIndex];
if (leftIndex > rightIndex)
continue;
while (leftIndex < rightIndex)
{
while ((leftIndex <= rightIndex) && (input[leftIndex] <= pivot))
leftIndex++;
while ((leftIndex <= rightIndex) && (input[rightIndex] >= pivot))
rightIndex--;
if (rightIndex >= leftIndex)
SwapElement(ref input, leftIndex, rightIndex);
}
if (pivotIndex <= rightIndex)
if( input[pivotIndex] > input[rightIndex])
SwapElement(ref input, pivotIndex, rightIndex);
if (leftIndexOfSubSet < rightIndex)
{
stack.Push(leftIndexOfSubSet);
stack.Push(rightIndex - 1);
}
if (rightIndexOfSubset > rightIndex)
{
stack.Push(rightIndex + 1);
stack.Push(rightIndexOfSubset);
}
}
}
private static void SwapElement(ref int[] arr, int left, int right)
{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
}
Feel free to ask any questions by emailing me at varun_jain786@yahoo.com or write comments in the forum below.
History
- 18th September, 2008: Initial post