Solved

# QuickSort and stack

Posted on 1999-01-26
2,361 Views
How can I use quick sort with a stack? I could not figure out how to use nonrecursive version of quicksort with a stack for sorting integers. Please can somebody point me to an algorithm or program?
0
Question by:jcardenas
• 3
• 2
• 2
• +1

LVL 1

Expert Comment

ID: 1185215
Check out the the implementation at
http://www.snippets.org/RG_QSORT.C

I hope this isn't a homework assignment for a programming class...
0

LVL 22

Expert Comment

ID: 1185216
>> I hope this isn't a homework assignment for a programming class...
Do you how many times this question comes up in the progessional programming world?  Less than never...    First of all, no one would ask for such a thing unless they were already familair with the solution--i.e. like a teacher.  Second, no one needs such a thing in the real world.
0

LVL 1

Expert Comment

ID: 1185217
>Do you how many times this question comes up in the >progessional programming world?  Less than never...

While I agree in the context of this question, I disagree overall.  This topic very much comes up if the language you are using does not provide recursion (.i.e. Fortran) or if you are in a limited memory situation that is common to many embedded systems.

It's a big professional programming world out there and I bet there are more than a few non-trivial programs that rely on iterative qsort to get the job done.
0

LVL 22

Expert Comment

ID: 1185218
But fortran questions don't come up in C++ and recursive algorithms, like Q-Sort, tend to use less memory when implimented recursively compared to no-recursive implimentations(not always).

>> there are more than a few non-trivial
>> programs that rely on iterative qsort to get the job done
Definitely, but how may had programing specs that said that the sort had to be done with a non-recursive Q-stort and (this is the clincher) using a stack?
0

Author Comment

ID: 1185219
Friends, I am teacher. This question is an example for my students. I am using an american text for my class.

The spanish text don´t has this exercises.I the snippets solution is good, but we are looking for a easy algorithm to write a nonrecursive version of QuickSort using a stack for sorting integers.

Regards from Colombia,South America

Jairo A. Cardenas
0

LVL 22

Expert Comment

ID: 1185220
How can you possibly expect your students to do this if you can't?
0

Accepted Solution

bbarnette earned 100 total points
ID: 1185221
Assuming you have a Partitioning function and a Swap function the Non_recursive QuickSort algorithm posted below is one I used not to long ago. The call to GetStackTop only references  the integer value. Hope this helps.

void stackClass::QuickSort(stackItemType A[], int F, int L)
// Non_recursively sorts the items in an array into ascending order.
// Precondition: A[F..L] is an array.
// Postcondition: A[F..L] is sorted.
// Calls: Partition, GetStackTop, Pop, Push.
{  int Pivot;
stackClass Q; // first stack
stackClass QS;// second stack
bool Success;
L = Top;//limit sort to data entered, do not sort empty elements

// sort entire stack
while(L > 0)
{
// get the value of 1st stacktop(F)
Q.GetStackTop(F,Success);
// get the value of 2nd stacktop(L)
QS.GetStackTop(L,Success);

if(F < L)
{
// pop the value of stacktop on 1st stack
Q.Pop(Success);
// pop the value of stacktop on 2nd stack
QS.Pop(Success);

// partitions the array into two stacks
// for sorting
Partition(A,F,L,Pivot);

Q.Push(F,Success);
QS.Push(Pivot-1,Success);

// push new item of 1st stack
Q.Push(Pivot+1, Success);
// push new item of 2nd stack
QS.Push(L, Success);

}
else
{
Q.Pop(Success);
QS.Pop(Success);

}
}// end while()
}// end QuickSort()
0

Author Comment

ID: 1185222
This a good implementation using ADT. For my students this a good example.

Thanks from Colombia,

Jairo
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

### Suggested Solutions

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.