Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

QuickSort and stack

Posted on 1999-01-26
8
Medium Priority
?
2,403 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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 400 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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

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. …
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

598 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