?
Solved

QuickSort and stack

Posted on 1999-01-26
8
Medium Priority
?
2,396 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

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

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses
Course of the Month10 days, 16 hours left to enroll

770 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