Solved

QuickSort and stack

Posted on 1999-01-26
8
2,353 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

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

919 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

21 Experts available now in Live!

Get 1:1 Help Now