12,950,618 members (61,953 online)
alternative version

#### Stats

52.8K views
32 bookmarked
Posted 18 Sep 2008

# Quick Sort Without Recursion

, 18 Sep 2008 CPOL
 Rate this:
Quick Sort Without Recursion

## 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);//Push always with left and right
stack.Push(rightIndex);

int leftIndexOfSubSet, rightIndexOfSubset;

while (stack.Count > 0)
{
rightIndexOfSubset = (int)stack.Pop();//pop always with right and left
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++;	//increment right to find the greater
//element than the pivot

while ((leftIndex <= rightIndex) && (input[rightIndex] >= pivot))
rightIndex--;//decrement right to find the
//smaller element than the pivot

if (rightIndex >= leftIndex)   //if right index is
//greater then only swap
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

## Share

 Software Developer (Senior) United States
Sr Developer (Passionate Developer)
varun_jain786@yahoo.com

## You may also be interested in...

 First Prev Next
 My vote of 5 Nandaaa15-Aug-13 21:31 Nandaaa 15-Aug-13 21:31
 Cool, Gave you a Five... TheArchitectmc∞25-Mar-10 1:11 TheArchitectmc∞ 25-Mar-10 1:11
 Array.Sort and Functional Quicksort Tuomas Hietanen2-Oct-08 3:28 Tuomas Hietanen 2-Oct-08 3:28
 Memory usage? JasonDiplomat22-Sep-08 15:21 JasonDiplomat 22-Sep-08 15:21
 Yo here, it is.... Member 287207519-Sep-08 4:11 Member 2872075 19-Sep-08 4:11
 What about speed? s.illyuhin19-Sep-08 2:18 s.illyuhin 19-Sep-08 2:18
 ref Jean-Paul Mikkers18-Sep-08 22:32 Jean-Paul Mikkers 18-Sep-08 22:32
 Re: ref BillHines22-Sep-08 7:51 BillHines 22-Sep-08 7:51
 Re: ref Jean-Paul Mikkers22-Sep-08 8:28 Jean-Paul Mikkers 22-Sep-08 8:28
 Re: ref BillHines22-Sep-08 10:22 BillHines 22-Sep-08 10:22
 Last Visit: 31-Dec-99 18:00     Last Update: 25-May-17 21:38 Refresh 1