Click here to Skip to main content
Click here to Skip to main content

Quick Sort Without Recursion

, 18 Sep 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Varun Jain 786
Software Developer (Senior)
United States United States
Sr Developer (Passionate Developer)
varun_jain786@yahoo.com
 
http://sites.google.com/site/varunjain786main/
http://www.linkedin.com/in/varunjain786

Comments and Discussions

 
GeneralMy vote of 5 PinmemberNandaaa15-Aug-13 22:31 
QuestionHow about this algorithm? PinmemberMember 142664114-Aug-13 10:24 
QuestionCool, Gave you a Five... PinmemberTheArchitectmc25-Mar-10 2:11 
GeneralArray.Sort and Functional Quicksort PinmemberTuomas Hietanen2-Oct-08 4:28 
QuestionMemory usage? PinmemberJasonDiplomat22-Sep-08 16:21 
GeneralYo here, it is.... PinmemberMember 287207519-Sep-08 5:11 
QuestionWhat about speed? Pinmembers.illyuhin19-Sep-08 3:18 
Generalref PinmemberJean-Paul Mikkers18-Sep-08 23:32 
GeneralRe: ref PinmemberBillHines22-Sep-08 8:51 
GeneralRe: ref PinmemberJean-Paul Mikkers22-Sep-08 9:28 
GeneralRe: ref PinmemberBillHines22-Sep-08 11:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 18 Sep 2008
Article Copyright 2008 by Varun Jain 786
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid