Sorting 2 dynamic stacks with quicksort

Question

Ivan_9 0 Newbie Poster

9 Years Ago

Hi, could somebody help me how to write a function that sort elements in two dynamic stacks(contained in an external file) by the quicksort method?I think I have written the other functions correctly but I find hard time on this one.Please help me if you can, I will appreciate it very much :)

    #include <iostream>
    #include <stdlib.h>
    #include <fstream>

    using namespace std;

    struct elem {
        int key;
        elem *next;
    } *stack;

    void push(stack& S, int n) {
        stack p = S;
        S = new elem;
        S->key = n;
        S->next = p;
    }
    int pop(stack& S) {
        int n;
        stack p = S;
        n = S->key;
        S = S->next;
        delete p;
        return n;
    }
    void file_input()
    {
        int a;
        ifstream file_1;
        file_1.open("file.txt", ios::in);
        if (file_1)
        {
            while (!file_1.eof())
            {
                file_1 >> a;
                push(s1, a);
            }
            file_1.close();
            cout << endl << "Done" << endl << endl;
        }
        else                          
            cout << "Error" << endl;
}

c++

Edited 9 Years Ago by Ivan_9

5 Contributors
26 Replies
2K Views
2 Weeks Discussion Span
Latest Post 8 Years Ago Latest Post by David W

David W 131 Practically a Posting Shark

8 Years Ago

Here is a link to an other quick sort example that you might like to see ...
(I tried the pseudo-code suggested by Dani's @Invisal ... but this looks even more interesting ... as it has optimizations to output list's that are already sorted ... or ... already reverse sorted ... in O(n) time.

http://stackoverflow.com/questions/14805936/optimal-quicksort-for-single-linked-list

Edited 8 Years Ago by David W

David W 131 Practically a Posting Shark

8 Years Ago

OK ... try this ...
See source credit for the (original C version of) quick sort in the program comments ...

// test_stack_with_quick_sort.cpp //

#include <iostream>
#include <fstream>
#include <climits> // re. INT_MIN //


using namespace std;


const char* FNAME = "keys.txt";

/*
4 3 2 1 0 9 8 7 6 5
*/


struct Element
{
    int key;
    Element* next;

    Element( int key=0, Element* next=0 ) : key(key), next(next) {}
} ;



struct Stack
{
    Element* start;
    Element* end;
    int len;

    Stack() : start(0), end(0), len(0) {} // default ctor...
    ~Stack() { clear(); }

    Stack( const Stack& stk ) // copy ctor...
    {
        len = 0;
        end = start = 0;
        if( stk.len )
        {
            Element* cur = stk.start;
            end = start = new Element( cur->key );
            ++len;
            cur = cur->next;

            while( cur )
            {
                Element* new_pe = new Element( cur->key );
                end->next = new_pe;
                end = new_pe;
                ++len;
                cur = cur->next;
            }
        }
    }

    Stack& operator = ( const Stack& stk ) // overlooaded operator =
    {
        if( this != &stk )
        {
            len = 0;
            end = start = 0;
            if( stk.len )
            {
                Element* cur = stk.start;
                end = start = new Element( cur->key );
                ++len;
                cur = cur->next;

                while( cur )
                {
                    Element* new_pe = new Element( cur->key );
                    end->next = new_pe;
                    end = new_pe;
                    ++len;
                    cur = cur->next;
                }
            }
        }
        return *this;
    }

    void push_front( int key )
    {
        Element* new_pe = new Element( key );
        if( len )
        {
            new_pe->next = start;
            start = new_pe;
        }
        else
        {
            start = end = new_pe;
        }
        ++len;
    }

    void push_back( int key )
    {
        Element* new_pe = new Element( key );
        if( len )
        {
            end->next = new_pe;
            end = new_pe;
        }
        else
        {
            start = end = new_pe;
        }
        ++len;
    }

    void clear()
    {
        while( start )
        {
            Element* cur = start;
            start = start->next;
            delete cur;
        }
        end = 0;
        len = 0;
    }

    void pop_front()
    {
        if( len )
        {
            Element* cur = start;
            start = start->next;
            delete cur;
            --len;
        }
    }

    int size() const { return len; }

    bool empty() const { return len == 0; }

    int front() const { if( len) return start->key; else return INT_MIN; }
    int back()  const { if( len) return end->key;   else return INT_MIN; }

    bool load_from( const char* fname  )
    {
        ifstream fin( fname );
        if( fin )
        {
            int key;
            while( fin >> key )
            {
                push_front( key );
            }
            fin.close();
            return true;
        }
        //else
        cerr << "There was a problem opeinug file " << fname << endl;
        return false;
    }

    void print( ostream& os ) const
    {
        Element* cur = start;
        while( cur )
        {
            os << cur->key << ' ';
            cur = cur->next;
        }
        os << "(len = " << len << ')';
    }


    /*
        http://stackoverflow.com/questions/14805936/optimal-quicksort-for-single-linked-list
    */

    // This version was edited/updated to C++ code from the C version found at the above link //
    void quick_sort( Element* head, Element* tail, Element*& rtn )
    {
        int nlo, nhi;
        Element *lo, *hi, *q, *p;

        // Invariant:  Return head sorted with 'tail' appended. //
        while( head != 0 )
        {
            nlo = nhi = 0;
            lo = hi = 0;
            q = head;
            p = head->next;

            // Start optimization for O(n) behavior on sorted and reverse-of-sorted lists //
            while( p != 0 && p->key < head->key )
            {
                head->next = hi;
                hi = head;
                ++ nhi;
                head = p;
                p = p->next;
            }

            // If entire list was ascending, we're done. //
            if( p == 0 )
            {
                rtn = head;
                head->next = hi;
                q->next = tail;
                return;
            }


            // End optimization ... can be deleted if desired. //

            // Partition and count sizes. //
            while( p != 0 )
            {
                q = p->next;
                if( p->key < head->key )
                {
                    p->next = lo;
                    lo = p;
                    ++ nlo;
                }
                else
                {
                    p->next = hi;
                    hi = p;
                    ++ nhi;
                }
                p = q;
            }

            // Recur to establish invariant for sublists of head,
            // choosing shortest list first to limit stack. //
            if( nlo < nhi )
            {
                quick_sort( lo, head, rtn );
                rtn = head->next;
                head = hi; // Eliminated tail-recursive call. //
            }
            else
            {
                quick_sort( hi, tail, head->next );
                tail = head;
                head = lo; // Eliminated tail-recursive call. //
            }
        }
        // Base case of recurrence. Invariant is easy here. //
        rtn = tail;
    }

    void quick_sort()
    {
        if( len > 1 )
        {
            quick_sort( start, 0, start );

            // update new 'end' //
            Element* cur = start;
            while( cur && cur->next )
                cur = cur->next;
            end = cur;
        }
    }

} ;





int main()
{
    Stack stk;

    if( stk.load_from( FNAME ) )
    {
        stk.print( cout );
    }
    cout << endl;

    stk.quick_sort();

    while( !stk.empty() )
    {
        cout << stk.front() << ' ';
        stk.pop_front();
    }
}

Edited 8 Years Ago by David W

David W 131 Practically a Posting Shark

8 Years Ago

Oops ...

There was a bug in the above code.

Please use the version below ...

and also see the added debug / compile option switches

and corrected comments

and more descriptive variable names.

// test_stack_with_quick_sort_fixed.cpp //

#include <iostream>
#include <fstream>
#include <climits> // re. INT_MIN //


using namespace std;

#define addInOpts 1   // set to 0 to turn off, set to 1 to turn on //

#define qsortDebug 1  // set to 0 to turn off, set to 1 to turn on //



const char* FNAME = "keys.txt";

/*
4 3 2 1 0 9 8 7 6 5
*/

class Stack;
// Note the forward declaration  ...
// so can give Stack 'friend class status' in class Element
// and thus to give the Stack class 
// free access to the private parts of class Element. //


class Element
{
public:
    Element( int key=0, Element* next=0 ) : key(key), next(next) {}
private:
    int key;
    Element* next;
    friend class Stack;
} ;



class Stack
{
private:
    Element* start;
    Element* end;
    int len;
public:
    Stack() : start(0), end(0), len(0) {} // default ctor...
    ~Stack() { clear(); }

    Stack( const Stack& stk ) // copy ctor...
    {
        len = 0;
        end = start = 0;
        if( stk.len )
        {
            Element* cur = stk.start;
            end = start = new Element( cur->key );
            ++len;
            cur = cur->next;

            while( cur )
            {
                Element* new_pe = new Element( cur->key );
                end->next = new_pe;
                end = new_pe;
                ++len;
                cur = cur->next;
            }
        }
    }

    Stack& operator = ( const Stack& stk ) // overlooaded operator =
    {
        if( this != &stk )
        {
            len = 0;
            end = start = 0;
            if( stk.len )
            {
                Element* cur = stk.start;
                end = start = new Element( cur->key );
                ++len;
                cur = cur->next;

                while( cur )
                {
                    Element* new_pe = new Element( cur->key );
                    end->next = new_pe;
                    end = new_pe;
                    ++len;
                    cur = cur->next;
                }
            }
        }
        return *this;
    }

    void push_front( int key )
    {
        Element* new_pe = new Element( key );
        if( len )
        {
            new_pe->next = start;
            start = new_pe;
        }
        else
        {
            start = end = new_pe;
        }
        ++len;
    }

    void push_back( int key )
    {
        Element* new_pe = new Element( key );
        if( len )
        {
            end->next = new_pe;
            end = new_pe;
        }
        else
        {
            start = end = new_pe;
        }
        ++len;
    }

    void clear()
    {
        while( start )
        {
            Element* cur = start;
            start = start->next;
            delete cur;
        }
        end = 0;
        len = 0;
    }

    void pop_front()
    {
        if( len )
        {
            Element* cur = start;
            start = start->next;
            delete cur;
            --len;
        }
    }

    int size()   const { return len; }
    bool empty() const { return len == 0; }

    int front() const { if( len) return start->key; else return INT_MIN; }
    int back()  const { if( len) return end->key;   else return INT_MIN; }

    bool load_from( const char* fname  )
    {
        ifstream fin( fname );
        if( fin )
        {
            int key;
            while( fin >> key )
            {
                push_back( key );
            }
            fin.close();
            return true;
        }
        // else
        cerr << "There was a problem opening file "
             << fname << '\n';
        return false;
    }

    void print( ostream& os ) const
    {
        Element* cur = start;
        while( cur )
        {
            os << cur->key << ' ';
            cur = cur->next;
        }
        os << "(len = " << len << ')';
    }


    /*
        http://stackoverflow.com/questions/14805936/optimal-quicksort-for-single-linked-list
        Code here was edited/comments-corrected from the C version found at the above link.
    */
    void quick_sort( Element* head, Element* tail, Element** rtn )
    {
        int nlo, nhi;
        Element *lo, *hi, *cur, *next;

        // Invariant:  Return head sorted with 'tail' appended. //
        while( head != 0 )
        {
            nlo = nhi = 0;
            lo = hi = 0;
            cur = head;
            next = head->next;

#if addInOpts

            // Start optimization for O(n) behavior on sorted lists and
            // reverse-of-sorted lists ...
            // changes (leading) reverse order to sorted order
            while( next != 0 && next->key <= head->key )
            {
                head->next = hi;
                hi = head;
                ++ nhi;
                head = next;
                next = next->next;
            }
#if qsortDebug

            if( nhi > 0 )
            {
                cout << "nhi = " << nhi << ";  list is ";
                for( Element* tmp = hi; tmp != 0; tmp = tmp->next )
                    cout << tmp->key << ' ';
                cout << '\n';
            }

#endif
            // If entire above passed in list was in descending order ...
            // (it was all reversed to ascending order and ... )
            // this next block of code gets skipped //
            if( next == 0 )
            {
                *rtn = head;
                head->next = hi;
                cur->next = tail;
#if qsortDebug
                cout << "Next was 0: list is ";
                for( Element* tmp = *rtn; tmp != 0; tmp = tmp->next )
                    cout << tmp->key << ' ';
                cout << '\n';
#endif
                return;
            }

#endif
            // End optimization ... can be deleted if desired. //

            // Partition and count sizes. //
            while( next != 0 )
            {
                cur = next->next;
                if( next->key <= head->key )
                {
                    next->next = lo;
                    lo = next;
                    ++ nlo;
                }
                else
                {
                    next->next = hi;
                    hi = next;
                    ++ nhi;
                }
                next = cur;
            }

            // Recur to establish invariant for sublists of head,
            // choosing shortest list first to limit stack. //
            if( nlo < nhi )
            {
                quick_sort( lo, head, rtn );
                rtn = &head->next;
                head = hi; // Eliminated tail-recursive call. //
            }
            else
            {
                quick_sort( hi, tail, &head->next );
                tail = head;
                head = lo; // Eliminated tail-recursive call. //
            }
        }
        // Base case of recurrence. Invariant is easy here. //
        *rtn = tail;
    }

    void quick_sort()
    {
        if( len > 1 )
        {
            quick_sort( start, 0, &start );

            // update new 'end' //
            Element* cur = start;
            while( cur && cur->next )
                cur = cur->next;
            end = cur;
        }
    }

} ;





int main()
{
    Stack stk;

    if( stk.load_from( FNAME ) )
    {
        stk.print( cout );
        cout << endl;


        stk.quick_sort();

        // now testing if 'front' and 'end' were updated ok //
        stk.push_back( 100 );
        stk.push_front( -100 );

        cout << "After push_back(100) and then push_front(-100) ...\n";
        stk.print( cout );
        cout << endl;

        while( !stk.empty() )
        {
            cout << stk.front() << ' ';
            stk.pop_front();
        }
    }

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

Edited 8 Years Ago by David W

David W 131 Practically a Posting Shark

8 Years Ago

Can your Stack class have,
beside the usual ...
push (front)
pop (front)
front
back ...

can it also have iterators ...
Iter it;
++ it method and it ++ method
Iter begin() method
Iter end() method
and methods with calls like ...
erase( it_previous, it )
get_key_at( it )
?

If so ... the quick sort could be a function
(a function that calls another function)
that is not part of the Stack class.

If that is that what you need ...
please supply ALL the original spec's so that we can see UPFRONT
all the limitations assigned ....
and so that there are NO more bunny trails.

Edited 8 Years Ago by David W

David W 131 Practically a Posting Shark

8 Years Ago

Another oops ... found in code above. Please edit/update as per code below ...

    Stack& operator = ( const Stack& stk ) // overlooaded operator =
    {
        if( this != &stk )
        {
            //len = 0;
            //end = start = 0;
            clear(); // to prevent memory leak //
            if( stk.len )
            {
                Element* cur = stk.start;
                end = start = new Element( cur->key );
                ++len;
                cur = cur->next;
                while( cur )
                {
                    Element* new_pe = new Element( cur->key );
                    end->next = new_pe;
                    end = new_pe;
                    ++len;
                    cur = cur->next;
                }
            }
        }
        return *this;
    }

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster · Answer 1 · 2015-11-11T11:14:59+00:00

Is it required to write your own stack? If not, you could use a std::vector to store your data in and then sort it with std::sort . For an example see:
http://www.cplusplus.com/reference/algorithm/sort/

Ivan_9 0 Newbie Poster · Answer 2 · 2015-11-13T09:41:38+00:00

Yes it's required and I'm not able to use std::vector :(

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster · Answer 3 · 2015-11-13T11:30:36+00:00

In that case have a look at this site:
http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx

Ivan_9 0 Newbie Poster · Answer 4 · 2015-11-22T09:50:36+00:00

How about my "file imput" function, how can I fix it?Please help me.

David W 131 Practically a Posting Shark · Answer 5 · 2015-11-23T21:30:14+00:00

David W 131 Practically a Posting Shark

8 Years Ago

This may help you to get started ...

test_stack.cpp (3.84 KB)

// test_Stack.cpp //



#include <iostream>
#include <fstream>
#include <climits> // re. INT_MIN
//#include <cstdlib> // <stdlib.h> // NOT In C++ //


using namespace std;


const char* FNAME = "keys.txt";

/*
1 2 3 4 5 6 7 8 9
*/


struct Element
{
    int key;
    Element* next;
    
    Element( int key=0, Element* next=0 ) : key(key), next(next) {}
} ;



struct Stack
{
    Element* start;
    Element* end;
    int size;
    
    Stack() : start(0), end(0), size(0) {}
    
    void push_back( int key )
    {
        Element* new_pe = new Element( key );
        if( size )
        {
            end->next = new_pe;
            end = new_pe;
        }
        else
        {
            start = end = new_pe;
        }
        ++size;
    }

    void push_front( int key )
    {
        Element* new_pe = new Element( key );
        if( size )
        {
            new_pe->next = start;
            start = new_pe;
        }
        else
        {
            start = end = new_pe;
        }
        ++size;
    }
    
    
    
    void clear()
    {
        while( start != 0  )
        {
            Element* cur = start;
            start = start->next;
            delete cur;
        }
        end = 0;
        size = 0;
    }

    ~Stack() { clear() ; }


    // copy ctor ...
    Stack( const Stack& stk )
    {
        size = 0;
        end = start = 0;
        if( stk.size )
        {
            Element* cur = stk.start;
            end = start = new Element( cur->key );
            ++size;
            cur = cur->next;

            while( cur )
            {
                Element* new_pe = new Element( cur->key );
                end->next = new_pe;
                end = new_pe;
                ++size;
                cur = cur->next;
            }
        }
    }

    // overlooaded operator =
    Stack& operator = ( const Stack& stk )
    {
        if( this != &stk )
        {
            size = 0;
            end = start = 0;
            if( stk.size )
            {
                Element* cur = stk.start;
                end = start = new Element( cur->key );
                ++size;
                cur = cur->next;

                while( cur )
                {
                    Element* new_pe = new Element( cur->key );
                    end->next = new_pe;
                    end = new_pe;
                    ++size;
                    cur = cur->next;
                }
            }
        }
        return *this;
    }

    void pop_front()
    {
        if( size )
        {
            Element* cur = start;
            start = start->next;
            delete cur;
            --size;
        }
    }
    
    int front() const { if( size) return start->key; else return INT_MIN; }
    int back() const { if( size) return end->key; else return INT_MIN; }
    
    bool empty() const { return size == 0; }
    
    
    bool load_from( const char* fname  )
    {
        ifstream fin( fname );
        if( fin )
        {
            int key;
            while( fin >> key )
            {
                push_front( key );
            }
            fin.close();
            return true;
        }
        //else
        cerr << "There was a problem opeinug file " << fname << endl;
        return false;
    }
    
    void print( ostream& os ) const
    {
        Element* cur = start;
        while(  cur )
        {
            os << cur->key << ' ';
            cur = cur->next;
        }
        os << "(size = " << size << ')';
    }
} ;





int main()
{
    Stack stk;
    if( stk.load_from( FNAME ) )
    {
        stk.print( cout );
    }
    cout << endl;
    
    while( !stk.empty() )
    {
        cout << stk.front() << ' ';
        stk.pop_front();
    }
}

keys.txt (0.02 KB)

1 2 3 4 5 6 7 8 9

Edited 8 Years Ago by David W

Ivan_9 0 Newbie Poster · Answer 6 · 2015-11-24T15:54:44+00:00

Ok, thank you all for the support, I did the program except the quicksort function.I find it very difficult so I will appreciate every kind of help.My function should be written like this(this is a bubblesort function from another project)

void bubblesort(elem *&S)
{
     elem *T;
     int n, flag;
     if (S==NULL) return;
     do
     {
         flag=0;
         T = S;
         while (T->next)
         {
             if (T->next->key < T->key) 
             {
                 n=T->key;
                 T->key=T->next->key;
                 T->next->key=n;
                 flag=1;
             }
             T = T->next;
         }
     } while (flag);
}

David W 131 Practically a Posting Shark · Answer 7 · 2015-11-25T05:29:35+00:00

What you have here is really some code for the start to single-link linked list.
I do not think a quick-sort type sort is practical on a single-link linked list ... a merge sort makes more sense

Ivan_9 0 Newbie Poster · Answer 8 · 2015-11-25T08:38:39+00:00

In my coursework it says that I have to sort the dynamic stacks by the Quicksort method.Everyone has got a random sort method and I've got the qucksort, without it I won't finish my course..

David W 131 Practically a Posting Shark · Answer 9 · 2015-11-25T15:01:07+00:00

Then do not use a linked list structure for your stack ...

Instead ...use a dynamic array, with a push_back and a pop_back ...
as the basis for your stack ...

But why do you wish to sort a stack ???

David W 131 Practically a Posting Shark · Answer 10 · 2015-11-25T15:48:04+00:00

... how to write a function that sort elements in two dynamic stacks (contained in an external file) by the quicksort method?

So ... it seems your problem really boils down to this:

Read in a supplied file containing several integers ...
(say it is called: " Integers1.txt")
into some (user designed - like a dynamic array?) container
and quicksort those integers.

Then output those sorted int's into a file called: "SortedIntegers1.txt".

Do this for a 2nd supplied file ...
(say it is called: "Integers2.txt")

That fact that, here, it was the contents of a stack that was dumped into a file does NOT really have any bearing on sorting those numbers.

Ivan_9 0 Newbie Poster · Answer 11 · 2015-11-25T19:25:03+00:00

The problem is that I'm not allowed to sort integers in array or anything like that.Im obliged to sort the numbers IN the stak with the QUICKSORT method.That's the condition in my coursework.I put an example how it should be done with BUBBLESORT and that's the only right way(best by using other temp stack).

David W 131 Practically a Posting Shark · Answer 12 · 2015-11-26T00:29:19+00:00

Could you provide the full original spec's for your problem?

I supect you are missing something there ...

But in any case,
in order to begin to help you effectively,
one really needs full disclosure of what was expected ...
(by the spec's to which you were instructed to comply.)

invisal 381 Search and Destroy · Answer 13 · 2015-11-26T02:05:25+00:00

I don't get this question. Do you want to do a QuickSort on Linked List or Stack? Because based on your example, it is a linked list. Although you can use linked list to implement stack, but you must obey the stack properly. In Stack, you can either do pop() or push(). You cannot iterate over your stack without using pop() and when you use pop() you remove an element out of your stack.

If you want to do QuickSort on Linked List, it is easy. First, use the first element of linked list as pivot. Then iterate your linked list. Once you hit the node that is smaller than pivot. Remove it and add it back. By the end of this process, you perfectly partition your linked list into two segments. Then, you do QuickSort on the left side of the pivot and QuickSort on the right side of the pivot.

Here is the pseudo code:

   QuickSort()
         QuickSort(head, null)

   QuickSort(Node start, Node end):
          if start = end the terminate the function
          pivot = start
          current = start.next;

          // do the partition
          while current != end
               next = current.next

               if pivot.key > current.key then
                     delete current node
                     insert current node before the pivot node

               current = next

          // do QuickSort on the left and right side of the pivot
          QuickSort(start, pivot)
          QuickSort(pivot.next, end)

rubberman 1,355 Nearly a Posting Virtuoso Featured Poster · Answer 14 · 2015-11-26T02:17:06+00:00

You want to use a vector, and a bsearch-based insertion sort for this, so that the vector is always kept sorted. I wrote such code in C++ for a commercial application development framework (SDK) years ago (in the 1990's). Based upon the bsearch (binary search) algorithm, it would find the proper spot to insert the item, and then move the elements below down and stick the new one in that spot. It would detect if the array needed to be resized, and do that automatically. At that time, the STL collection classes were still a dream, or I would have used a std::vector instead of rolling my own. It handles the resizing and insertion stuff quite nicely, pushing the data down and resizing as needed. That would have saved me a couple of days coding effort! :-)

An additional tidbit - I also did head/tail optimizations for large arrays. Since we were dealing with collections of up to 100,000+ elements, that made a huge performance improvement, especially when dealing with inserting already sorted data, such as from a database query that utilized an "order by" clause.

Ivan_9 0 Newbie Poster · Answer 15 · 2015-11-26T08:28:58+00:00

invisal, I need a function that sort the elements of dynamic stack by the Quicksort method.I gave an example with Bubblesort how the function should be written.No vectors, no lists, no arrays to sort the elements there, just dynamic stacks and that's why it is hard.

rubberman 1,355 Nearly a Posting Virtuoso Featured Poster · Answer 16 · 2015-11-27T15:28:00+00:00

@Ivan_9. Quicksort and bsearch are two parts of the same whole. Quicksort uses bsearch algorithms to determine where to put the next element in the array. Knuth Vol.3 "Sorting and Searching" goes into this in detail. In any case, the common system qsort function will sort your array very nicely. You basically only need a comparison function to pass to the qsort() function, as well as some other elements, such as the address of the beginning of the array, the number of elements in the array, the size of each element, and a pointer to the compare function. Bingo, you are done!

If you have to "roll your own" quicksort function, then you REALLY need to understand what is going on here. Here is the Wikipedia article about quicksort. It is quite good. https://en.wikipedia.org/wiki/Quicksort

Personally, I prefer Knuth. :-)

FWIW, I have implemented these algorithms from scratch in C, C++, Java, and SmallTalk.

rubberman 1,355 Nearly a Posting Virtuoso Featured Poster · Answer 17 · 2015-11-27T15:34:30+00:00

As an aside, many years ago (in the late 1980's) I did exactly what you are doing, to implement quicksort to deal with highly dynamic arrays of data. I would keep track of the last sorted size of the array, the number of items removed or added, and when the sum of those exceeded some pre-determined count, the array would be resorted. IE, new items were simply added to the bottom of the array. Removed items would result in the followning contents being moved up one element (memmove() is good for that - very efficient), and the old end-of-sorted element count decrement by one if the item was in that section of the array. Searches had to look using the old "end-of-sorted" elements value, and if not found, look from the "end-of-sorted" point to the actual end of the array. Not good for real-time systems, which was my domain back then. That is why I went to the insertion sort method. The time to insert an element was computable based upon the number of elements in the array.

rubberman 1,355 Nearly a Posting Virtuoso Featured Poster · Answer 18 · 2015-11-27T15:41:20+00:00

And dealing with real-time systems, please DO NOT get me started on Rate Monotonic Analysis methods! :LOL:! If you do, you will be tortured with a VERY long lecture on the subject...

invisal 381 Search and Destroy · Answer 19 · 2015-11-27T16:24:19+00:00

@Ivan_9. Quicksort and bsearch are two parts of the same whole. Quicksort uses bsearch algorithms to determine where to put the next element in the array.

@rubberman
To be clear, QuickSort does not use binary search algorithm to determine where to put the next element in the array. It use partition. Furthermore, QuickSort does not have any relationship with Binary Search. However, QuickSort is almost identifical to Binary Search Tree. To sort an array, QuickSort choose a pivot and divide the array into two sub array which the left side is smaller than the pivot and the right side is greater than pivot. The concept of pivot in QuickSort is the same as the root of the subtree in Binary Search Tree where the left subtree is lesser than its parent and right subtree has greater value than its parent.

Interestingly, because of identical process of Binary Search Tree and QuickSort, we can use some of the well-studied property of QuickSort and apply to Binary Search Tree. For example, QuickSort does approximately 1.39 logn comparision for random ordered array. Therefore, the average depth of the random built of binary search tree is also 1.39logn.

Put that aside, none of us truly or really attempt to answer the OP. His question is how to use QuickSort to sort a stack without the help of other data structure. Obviously, if other data structure is allowed to use, we can just throw all the stack element in to the array and perform the QuickSort on the array and push all element back to stack. If we are allowed to use more than 2 stacks, it would be very easy. The question also restrict that we only need to use 2 stacks.

Moreover, I kind of doubt his assignment understanding. It would be nice if he can post the exact problem that his professor gave to him.

Ivan_9 0 Newbie Poster · Answer 20 · 2015-11-27T18:38:10+00:00

I understood how the quicksort method work, but I find it hard to write the sort function for dynamic stack with all the pointers, push(), pop().

Ivan_9 0 Newbie Poster · Answer 21 · 2015-11-28T21:20:38+00:00

Thank you very much, but I need a quicksort function that works with that dynamic stack insted of the class in your code

struct elem {
        int key;
        elem *next;
    } *stack;
    void push(stack& S, int n) {
        stack p = S;
        S = new elem;
        S->key = n;
        S->next = p;
    }
    int pop(stack& S) {
        int n;
        stack p = S;
        n = S->key;
        S = S->next;
        delete p;
        return n;
    }