Solved

QuickSort and stack

Posted on 1999-01-26
8
2,361 Views
Last Modified: 2012-05-04
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
Comment
Question by:jcardenas
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 1

Expert Comment

by:ATucker
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

by:nietod
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

by:ATucker
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
DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

 
LVL 22

Expert Comment

by:nietod
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

by:jcardenas
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

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

Accepted Solution

by:
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

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

Thanks from Colombia,


Jairo
0

Featured Post

ScreenConnect 6.0 Free Trial

Explore all the enhancements in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI, app configurations and chat acknowledgement to improve customer engagement!

Question has a verified solution.

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

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++.

773 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question