Solved

QuickSort and stack

Posted on 1999-01-26
8
2,347 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
 
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
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 

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

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

707 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now