Quicksort a dynamic deque

Can you please share the code that you have created so far?

So basically "Deque.h" contains standard functions pop_l(),pop_r(),push_l(),push_r(). I am pretty much stuck. I am sorry if i am not posting this code correctly. I am new here.

#include<iostream>
#include"Deque.h"
#include<fstream>
using namespace std;
int max(Deque d);
void search(Deque d,Deque &d2, int num, int funct);
int partition(Deque d,int l, int r);
void saveInFile(ofstream& toStream, Deque d);
void main()
{
      ifstream fp("integers.txt");
      ofstream fp2;
      fp2.open("integers2.txt");
      Deque deq,deq2;
      int temp;
      int x;
      while(fp >> x)
      {
            deq.push_r(x);
      }
      
}

int max(Deque d)
{
      int x;
      int max(0);
      while(d.pop_l(x))
      {
            if(x%7==0)
            {
                  if(x>max)
                  {
                        max = x;
                  }
            }
      }
      return max;
}

void search(Deque d,Deque &d2, int num, int funct)
{
      int x;
      while(d.pop_l(x))
      {
            if(x%num==0 && x<funct)
            {
                  d2.push_l(x);
            }
      }
}

void saveInFile(ofstream& toStream, Deque d)
{
      int x;
      toStream<<"Searched elements: ";
      while(d.pop_l(x))
      {
            toStream<<x<<" ";
      }
}

int partition(Deque d,int l, int r)
{

}

The actual header :
#include<cstddef>
class Deque
{
private:
      struct elem
{
      int key;
      elem *next;
} *_left,*_right;

      void copy(Deque const& d)
      {
            if (d.empty())
            return;
            push_r(d._left->key);
            elem *copy = d._left->next;
            while (copy != NULL) {
            push_r(copy->key);
            copy = copy->next;
            }
      }


public:
      Deque()
      {
            _left=NULL;
            _right=NULL;
      }
            Deque(Deque const& d) : _left(NULL), _right(NULL) {
            copy(d);
      }

            bool empty() const {
            return _left == NULL;
      }


      void push_l(int const n)
{
      elem *p;
      p=_left;
      _left=new elem;
      _left->key=n;
      _left->next=p;
      if (_right==NULL)
      {
            _right=_left;
      }
}

void push_r(int const n)
{
      elem *p;
      p=_right;
      _right=new elem;
      _right->key=n;
      _right->next=NULL;
      if(_left==NULL)
      {
            _left=_right;
      }
      else
            p->next=_right;

}

int pop_l(int  &n)
{
      elem *p;
      if(_left)
      {
            n=_left->key;
            p=_left;
            _left=_left->next;
            if(_left==NULL)
                  _right=NULL;
            delete p;
            return 1;
      }
      else return 0;
}

int pop_r(int  &n)
{
      elem *p;
      if(_right)
      {
            n=_right->key;
            if(_left==_right)
            {
                  delete _right;
                  _left=_right=NULL;
            }
            else
            {
                  p=_left;
                  while(p->next!=_right)
                        p=p->next;
                        p->next=NULL;
                        delete _right;
                        _right=p;
            }
            return 1;
      }
      else return 0;
      
}
};

actually quicksort works on arrays while your double-ended queue is based on a single-linked list.

to sort a single-linked list you would use insert sort since insertions are cheap into a linked list.

for this you would remove the left node from deque, then sort the rest of the deque recursively and insert the removed node at the right positition. recursion ends when the list to sort contains only one node.

of course you also could put all values from deque into an array, then use quicksort to sort the array, and finally create a new deque from array. this would be same speed for small numbers but probably not the most efficient method.

Sara

Isn't there a way to implement the quicksort sorting the deque ? I am banging my head 2nd week now and literally no clue.

can you describe your requirements? do you want to implement quicksort algorithm (method) for (your) deque or do you want to use a c function like qsort to sort the deque?

the latter requires the elements to be stored in an array (packed).

the first is to divide the deque into two deque's with random sizes, sort both recursively and then merge the two sorted lists into one. this could be done with linked lists but requires some extra storage since not all operations could be done in-place.

Sara

First of all thank u for all the comments and explanations. So my task is pretty much to create a deque, then actually write an algorithm based on the quicksort method so it can work with the deque.

I've made the header changes, but I am not quite aware how would I implement the static function in the cpp since it is an "elem" type.

#include<cstddef>
class Deque
{
private:
      bool own;
      struct elem
{
      int key;
      elem *next;
} *_left,*_right;

      void copy(Deque const& d)
      {
            if (d.empty())
            return;
            push_r(d._left->key);
            elem *copy = d._left->next;
            while (copy != NULL) {
            push_r(copy->key);
            copy = copy->next;
            }
      }


public:
      Deque(bool own = true) : _left(NULL), _right(NULL), own(own)
      {

      }

      ~Deque();

      Deque(Deque const& d) : _left(NULL), _right(NULL) {
            copy(d);
      }

            bool empty() const {
            return _left == NULL;
      }

            static elem* Deque::Partition(const Deque & currentDeque, Deque & newDeque)
            {

            }

      void push_l(int const n)
{
      elem *p;
      p=_left;
      _left=new elem;
      _left->key=n;
      _left->next=p;
      if (_right==NULL)
      {
            _right=_left;
      }
}

void push_r(int const n)
{
      elem *p;
      p=_right;
      _right=new elem;
      _right->key=n;
      _right->next=NULL;
      if(_left==NULL)
      {
            _left=_right;
      }
      else
            p->next=_right;

}

int pop_l(int  &n)
{
      elem *p;
      if(_left)
      {
            n=_left->key;
            p=_left;
            _left=_left->next;
            if(_left==NULL)
                  _right=NULL;
            delete p;
            return 1;
      }
      else return 0;
}

int pop_r(int  &n)
{
      elem *p;
      if(_right)
      {
            n=_right->key;
            if(_left==_right)
            {
                  delete _right;
                  _left=_right=NULL;
            }
            else
            {
                  p=_left;
                  while(p->next!=_right)
                        p=p->next;
                        p->next=NULL;
                        delete _right;
                        _right=p;
            }
            return 1;
      }
      else return 0;
      
}
};

looks quite good. if you add 'return NULL;' to member function Partition, it even should compile.

note, you should/could put your code into a code block. for that choose CODE from mini icons what inserts code tags and then paste your code between the tags. alternatively past the code first, select it and click on CODE minibutton.

since Deque is not a template class you could put the bodies of member functions  to deque.cpp file while the class only contains prototypes:

// deque.h
#ifndef DEQUE_H     // this prevents from including the header twice
#define DEQUE_H

class Deque
{
      ...
      Deque(bool own);
     ~Deque();
     static elem * Partition(const Deque&, Deque&);
     int pop_r(int & i);
     ...
};

#endif

Select allOpen in new window

//deque.cpp
#include "deque.h"
....

Deque::Deque(bool own) : _left(NULL), _right(NULL), _own(own) {}
Deque::~Deque()
{
       // delete nodes
       if (_own)
       {
            // iterate all nodes and delete them
            ...
        }
}

Deque::elem * Deque::Partition(const Deque & deque, Deque & newdeque)
{
      elem * pivot = deque.right;
      // todo
      ...
      return pivot;
}

// more implementations

Select allOpen in new window

Sara

note that i used Deque::elem for type in cpp file since elem was defined within class Deque.

you may consider to move the struct above class Deque:

struct elem
{
     int key;
     elem * next;
     elem(int k = 0) : key(k), next(NULL) {}
};

class Deque
{
      elem * _left;
      elem * _right;
      bool    _own;
      ....

Select allOpen in new window

then elem could be used from outside of the class without class scope.

Sara

Soo technically, What I've done pretty much:

#ifndef DEQUE_H 
#define DEQUE_H

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

class Deque
{
private:
bool own;
elem *_left;
elem *_right;
.....
Deque(bool own);
	Deque ();
	~Deque();

	Deque(Deque const& d) : _left(NULL), _right(NULL) {
		copy(d);
	}

		bool empty() const {
		return _left == NULL;
	}

	static elem * Partition(const Deque&, Deque&);

Select allOpen in new window

and cpp:

Deque::Deque(bool own) : _left(NULL), _right(NULL), own(own) {}
Deque::~Deque()
{
	int temp;
       if (own)
       {
		   while(_left!=NULL && _right!=NULL)
		   {
			   pop_l(temp);
		   }
       }
}

elem * Deque::Partition(const Deque & deque, Deque & newdeque)
{
      elem * pivot = deque._right;
      return pivot;
}

Select allOpen in new window

But I am getting some errors, something messed up. I think it will be easier for me if i keep the structure outside the class as you suggested.

But I am getting some errors

yes. if you copy some of my code, you always should be aware that it is not full code.

if you find .... somewhere it means that you need to add your old code at these positions.

Deque::Deque(bool own) : _left(NULL), _right(NULL), own(own)

the initializer always should init the member variables in the same order as they were defined. if 'bool own' is the first member, it also should be initialized first. one more point, left and right have an _ prefix to signal they were members. this is optional. you also could omit the _ prefix. but, it is bad coding if some members have an _ prefix and some not. so, you may name the member variable _own and not own. if you do so, it has the additional advantage that you avoided to have an argument variable with the same name as an member variable. this is not an error and the compiler can handle it (very old compilers did not) but it is bad coding either.

Sara

Still have some unresolved externals, gonna fix it. I just want to know if my destructor block is correct and about the partition function. I pass 2 deques, one of them is with the data, another one for temporary hold. I go through the deque with iterations using ->next pointer from the structure?
Thanks again!

I just want to know if my destructor block is correct

you need to iterate all 'elem' nodes from _left to _right similar you did in else branch of the pop_r member function.

but i see that the code in that function is wrongly indented. should be like

elem * p;

....
else 
{
       p=_left; 
       while(p->next !=_right)
             p=p->next;
       // end-of-while-loop
       p->next=NULL;
       delete _right;
       _right=p;
 }

Select allOpen in new window

for the destructor we could call pop_r as long as _right was not NULL.

or we need an iteration loop like the one above but have to delele each pointer

elem * pp, *pn;

pp =_left; 
while(pp !=NULL)
{
      pn = pp->next;
      delete pp;
      pp = pn;
}
_left = _right = NULL;  // just to make it clear that the deque is empty

Select allOpen in new window

Sara

I've wrote a partition function, I dont know if it makes any sence I hope it does. Going to continue later so for now

elem * Deque::Partition(Deque & curDeque)
	{
		int x = curDeque._left->key;
		elem *i = curDeque._left->next;
		for(elem *j=curDeque._left;j!=curDeque._right;j = j->next)
		{
			if(j->key <= x)
			{
				i = (i==NULL)?curDeque._left:i->next;
				swap(&(i->key),&(j->key));
			}
		}
		i=(i==NULL)?curDeque._left:i->next;
		swap(&(i->key),&(curDeque._left->key));
		return i;
		}

Select allOpen in new window

I will try figure it my self and then post it! Thanks again!

since the input deque was changed by partition function if you move nodes, it probably makes sense to pass only one deque by reference as you did in your code. since partition is a member function now, we even could use the 'this' deque for the first call. but for further calls with smaller lists this is not convenient and makes more trouble than it helped.

in next step we would add the caller function of partitition which is the one which was called recursively.

Sara

Okay, that's what I 've came up with following the pseudo code:

elem * Deque::Partition(const Deque& curDeque, Deque &newDeque)
	{
		newDeque._left=newDeque._right=NULL;
		elem* cur;
		elem* prev;
		elem* tmp;
		cur=curDeque._left;
		elem* pivot=curDeque._right;
		elem* tail=pivot;
		while(1)
		{
if(cur==pivot){break;}
			if(cur->key < pivot->key)
			{
				if(newDeque.empty()==true)
				{
					newDeque._left=cur;
					prev=cur;
					cur++;//didnt quite get it
				}
			}
			else
			{
				if(prev!=NULL)
				{
					prev->next=cur->next;
				}
				tmp=cur->next;
				cur->next=NULL;
				tail->next=cur;
				tail=cur;
				cur=tmp;
			}
		}
		
		if(newDeque._left==NULL)
		{
			newDeque._left=pivot;
			newDeque._right=tail;
		}
		return pivot;
	}

Select allOpen in new window

I did some thinking and correct some of the code but it is still not working correctly. It seems to break somewhere. Passing the first deque by value might be bad coding I don't really know but i want to use it for my other functions so ..

elem * Deque::Partition( Deque curDeque, Deque &newDeque)
	{
		newDeque._left=newDeque._right=NULL;
		elem* cur;
		elem* prev=NULL;
		elem* tmp=NULL;
		cur=curDeque._left;
		elem* pivot=curDeque._right;
		elem* tail=pivot;
		while(cur!=pivot)
		{
			if(cur->key < pivot->key)
			{
				if(newDeque._left==NULL)
				{
					newDeque._left=cur;
					prev=cur;
					cur=cur->next;
				}
			}
			else
			{
				if(prev)
				{
					prev->next=cur->next;
				}
				tmp=cur->next;
				cur->next=NULL;
				tail->next=cur;
				tail=cur;
				cur=tmp;
			}
		}
		
		if(newDeque._left==NULL)
		{
			newDeque._left=pivot;
			newDeque._right=tail;
		}
		return pivot;
	}

Select allOpen in new window

Passing the first deque by value might be bad coding

no. it is good. you may change to 'const Deque &' what avoids construction of a copy, but since the structure is very small, this doesn't matter.

the code looks good beside of a few mistakes:

{
    if(newDeque._left==NULL)
   {
	newDeque._left=cur;
   }
   // the following two statements must be done for all nodes less than the pivot 
   prev=cur;
   cur=cur->next;
}

Select allOpen in new window

}
if(newDeque._left==NULL)
{
	newDeque._left=pivot;
}
// right must be set always to the last tail node
newDeque._right=tail;

Select allOpen in new window

Sara

It seems to break somewhere.. and now I have to do another function for the recursive call yes?

elem * Deque::Partition(Deque curDeque, Deque &newDeque) // curDeque - inputted Deque // newDeque outputted Deque
	{
		newDeque._left=newDeque._right=NULL;
		elem* prev=NULL;
		elem* tmp=NULL;
		elem* cur=curDeque._left;
		elem* pivot=curDeque._right;
		elem* tail=pivot;
		while(cur!=pivot)
		{
			if(newDeque._left==NULL)
			{
					newDeque._left=cur;
			}
			if(cur->key < pivot->key)
			{

			if(newDeque._left==NULL)
			{
					newDeque._left=cur;
			}
					prev=cur;
					cur=cur->next;
				
			}
			else
			{
				if(prev)
				{
					prev->next=cur->next;
				}
				tmp=cur->next;
				cur->next=NULL;
				tail->next=cur;
				tail=cur;
				cur=tmp;
			}
		}
		
		if(newDeque._left==NULL)
		{
			newDeque._left=pivot;
		}
			newDeque._right=tail;
		return pivot;
	}

Select allOpen in new window

you still mixed up some code by duplicating an if block in

if(newDeque._left==NULL)   // remove that if block
{
	newDeque._left=cur;
}
if(cur->key < pivot->key)
{
	if(newDeque._left==NULL)
        {
		newDeque._left=cur;
	}
	prev=cur;
	cur=cur->next;
}

Select allOpen in new window

           

the right code is

if(cur->key < pivot->key)
{
        // this only may happen for the first node less than the pivot
        // because this node becomes the new _left (start node)
	if(newDeque._left==NULL)
        {
		newDeque._left=cur;
	}
        prev=cur;
	cur=cur->next;
}

Select allOpen in new window

           

Sara

you should test the code like

Deque deque(false);   // make a deque which doesn't own its nodes
                  // otherwise the copy you pass to Partition would delete all nodes
                  // we will solve that issue with next function 
deque.push_r(3);
deque.push_r(6);
deque.push_r(2);
deque.push_r(5);
deque.push_r(1);
deque.push_r(4);

Deque newDeque(false);  // an empty deque

elem * pivot = deque.Partition(deque, newDeque);

for (elem * pelem = newDeque._left; pelem != NULL; pelem = pelem->next)
{
        std::cout << "[";
        if (pelem == pivot) 
                std::cout << "*" << pivot.key << "*] ";
        else 
               std::cout << pelem->key << "] ";
        if (pelem->next != NULL)
              std::cout << "=> ";
        else  
              std::cout << "\n";
}

Select allOpen in new window

Sara

Okay I did it but something is wrong. I am going to post the whole code if that's not a problem.
Header:

#include<cstddef>
	struct elem
{
	int key;
	elem *next;
} ;
class Deque
{
private:
elem *_left;
elem *_right;
bool own;

	void copy(Deque const& d) 
	{
		if (d.empty())
		return;
		push_r(d._left->key);
		elem *copy = d._left->next;
		while (copy != NULL) {
		push_r(copy->key);
		copy = copy->next;
		}
	}


public:
	Deque(bool own);
	~Deque();
	Deque(){}

		Deque(Deque const& d) : _left(NULL), _right(NULL) {
		copy(d);
	}
		static elem* Partition(Deque curDeque, Deque &newDeque);

		bool empty() const 
		{
		return _left == NULL;
		}


	void push_l(int const n)
{
	elem *p;
	p=_left;
	_left=new elem;
	_left->key=n;
	_left->next=p;
	if (_right==NULL)
	{
		_right=_left;
	}
}

void push_r(int const n)
{
	elem *p;
	p=_right;
	_right=new elem;
	_right->key=n;
	_right->next=NULL;
	if(_left==NULL)
	{
		_left=_right;
	}
	else
		p->next=_right;

}

int pop_l(int  &n)
{
	elem *p;
	if(_left)
	{
		n=_left->key;
		p=_left;
		_left=_left->next;
		if(_left==NULL)
			_right=NULL;
		delete p;
		return 1;
	}
	else return 0;
}

int pop_r(int  &n)
{
	elem *p;
	if(_right)
	{
		n=_right->key;
		if(_left==_right)
		{
			delete _right;
			_left=_right=NULL;
		}
		else
		{
			p=_left;
			while(p->next!=_right)
				p=p->next;
				p->next=NULL;
				delete _right;
				_right=p;
		}
		return 1;
	}
	else return 0;
	
}
};

Select allOpen in new window

cpp:

#include<iostream>
#include"DequeH.h"
#include<fstream>
using namespace std;
int max(Deque d);
void search(Deque d,Deque &d2, int num, int funct);
void saveInFile(ofstream& toStream, Deque d);
void printFromLeft(Deque d);
void printFromRight(Deque d);
void main()
{
	ifstream fp("integers.txt");
	ofstream fp2;
	fp2.open("integers2.txt");
	Deque deq(false);
	Deque newDeque(false);
	int temp;
	int x;
	while(fp >> x)
	{
		deq.push_r(x); // pushes 3 6 2 5 1 4
	}

	cout<<"######################"<<endl
		<<"# 1.Print from left  #"<<endl
		<<"# 2.Print from right #"<<endl
		<<"# 3.Find specific    #"<<endl
		<<"# 4.Quicksort        #"<<endl
		<<"# 5.Save in file     #"<<endl
		<<"######################"<<endl;
	Deque::Partition(deq,newDeque);
	elem *pivot=Deque.Partition(deq,newDeque);
	for (elem * pelem = newDeque._left; pelem != NULL; pelem = pelem->next) //newDeque._left is inaccessible
{
        std::cout << "[";
        if (pelem == pivot) 
                std::cout << "*" << pivot->key << "*] ";
        else 
               std::cout << pelem->key << "] ";
        if (pelem->next != NULL)
              std::cout << "=> ";
        else  
              std::cout << "\n";
}
}

int max(Deque d)
{
	int x;
	int max(0);
	while(d.pop_l(x))
	{
		if(x%7==0)
		{
			if(x>max)
			{
				max = x;
			}
		}
	}
	return max;
}

void search(Deque d,Deque &d2, int num, int funct)
{
	int x;
	while(d.pop_l(x))
	{
		if(x%num==0 && x<funct)
		{
			d2.push_l(x);
		}
	}
}

void saveInFile(ofstream& toStream, Deque d)
{
	int x;
	toStream<<"Searched elements: ";
	while(d.pop_l(x))
	{
		toStream<<x<<" ";
	}
}
elem * Deque::Partition(Deque curDeque, Deque &newDeque) // curDeque - inputted Deque // newDeque outputted Deque
	{
		newDeque._left=newDeque._right=NULL;
		elem* prev=NULL;
		elem* tmp=NULL;
		elem* cur=curDeque._left;
		elem* pivot=curDeque._right;
		elem* tail=pivot;
		while(cur!=pivot)
		{
			
			if(cur->key < pivot->key)
			{

			if(newDeque._left==NULL)
			{
					newDeque._left=cur;
			}
					prev=cur;
					cur=cur->next;
				
			}
			else
			{
				if(prev)
				{
					prev->next=cur->next;
				}
				tmp=cur->next;
				cur->next=NULL;
				tail->next=cur;
				tail=cur;
				cur=tmp;
			}
		}
		
		if(newDeque._left==NULL)
		{
			newDeque._left=pivot;
		}
			newDeque._right=tail;
		return pivot;
	}

Deque::Deque(bool own) : _left(NULL), _right(NULL), own(own) {}
Deque::~Deque()
{
	elem * pp, *pn;

pp =_left; 
while(pp !=NULL)
{
      pn = pp->next;
      delete pp;
      pp = pn;
}
_left = _right = NULL;
}
void printFromLeft(Deque d)
{
	int temp;
	while(d.pop_l(temp))
	{
		cout<<temp<<" ";
	}
}

void printFromRight(Deque d)
{
	int temp;
	while(d.pop_r(temp))
	{
		cout<<temp<<" ";
	}
}

Select allOpen in new window

Deque(){}

you need to initialize member variable own for this constructor (which better was called _own)

otherwise own has some arbitrary value what makes the destructor delete all elem nodes. since you passed (a copy of ) the Deque by value to Partition, nodes of curdeque were deleted, after the function returned to caller. this is fatal in your case since the output deque contains the nodes of the curdeque and thos nodes were invalid after delete.

Deque(Deque const& d) : _left(NULL), _right(NULL)
{
    copy(d);
}

the copy constructor doesn't copy the 'own' member variable either. hence the new object also may have own with a non-zero value what is 'true'. also it makes a deep copy creating new node elements.  that makes not so much sense for Partition function which is supposed to work on the original deque and not on a copy.

Deque::Partition(deq,newDeque);
elem *pivot=Deque.Partition(deq,newDeque);

you call Partition function twice and the first time you don't store the return value. together with the previous issue, it is fatal.

i would suggest you to have a minimal class definition and put all implementation into cpp file:

the header then looks like

#ifndef DEQUE_H
#define DEQUE_H

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

class Deque
{
private:
      elem *_left;
      elem *_right;
public:
	Deque(elem * left = NULL, elem * right = NULL) : _left(NULL), _right(NULL) {}
	~Deque();

	static elem* Partition(elem * left, elem * right, elem *& newleft, elem *& newright);
        // these functions are only temporary
        void SortPrint();
        void PrintList(elem * pivot);

        bool empty() const { return _left == NULL; }
        void push_l(int const n);    // define body in cpp
        void push_r(int const n);   // define body in cpp
        int pop_l(int  &n);    // define body in cpp
        int pop_r(int  &n);  // define body in cpp
};

#endif

Select allOpen in new window

note, i removed the own member and the copy function. the compiler would add a copy constructor automatically. but since we want to operate only on the original nodes we don't need a copy and we will not pass the Deque by value.

note, _left and _right are private members. so, only member functions of class Deque have access to them. that means you either have to provide get functions for the members or use only members of Deque to access the members.  because of that i added member functions Sort and PrintList. the first will call the Partition and assign the new left and new right to _left and _right. the second will output the nodes in a loop and mark the pivot with *x*.

note, function Partition has now left and right node of a linked list as input, and newleft and newright as output.  the latter arguments are references to elem pointers what allows us to return new pointers for output. the Partition function will operate not only on the full linked list of the current deque but also has to part smaller lists when called recursively.

elem * Deque::Partition(elem * left, elem * right, elem *& newleft, elem *& newright)
{
      newleft=newright=NULL;
      elem* prev=NULL;
      elem* tmp=NULL;
      elem* cur=left;
      elem* pivot=right;
      elem* tail=pivot;
      while(cur!=pivot)
      {
           if(cur->key < pivot->key)
           {
                if(newleft==NULL)
                {
                     newleft=cur;
                }
                prev=cur;
		cur=cur->next;
           }
           else
           {
               if (prev != NULL) 
              {
   		   prev->next=cur->next;
              }
              tmp=cur->next;
              cur->next=NULL;
              tail->next=cur;
              tail=cur;
              cur=tmp;
         }
     }
     if(newleft==NULL)
     {
	   newleft=pivot;
     }
     newright=tail;
     return pivot;
}

Select allOpen in new window

// the following function will call Partition and print out the new list after first sorting step.
void Deque::SortPrint()
{
      elem * newleft = NULL, *newright = NULL;
      elem * pivot = Partition(_left, _right, newleft, newright);
      PrintList(pivot);
}
void Deque::PrintList(elem * pivot)
{
        for (elem * pelem = _left; pelem != NULL; pelem = pelem->next)   
        {
               // put here the output from my previous post
        }
}

Select allOpen in new window

#include <iostream>
#include "deque.h"

// put her your current code
....

int main()
{
      ....
      Deque deq; // no argument
      // fill 3 6 2 5 1 4
      ...
      dec.SortPrint();
      
      return 0;
 }

Select allOpen in new window

if you got errors post only one error a time with the code snippet where the error occured.

Sara

I have done everything, I dont have errors when I compile but it prints out 3 =>6 => 2 =>4 =>5. Prints the list from left to right and eats the last number.

Okay, everything works fine, I figured it out. It leaves me with the recursive call.

With mainly your help, a lot of other resources I've written this, It seems to be working just fine. Anyways, I am leaving it for a final review.
header:

static elem* Partition(elem * left, elem * right, elem *& newleft, elem *& newright);
static void quickSort(Deque &d);

Select allOpen in new window

cpp:

elem *quicksortrecur(elem * left, elem *right)
{
	if (!left || left == right)
        return left;
    elem *newleft = NULL, *newright = NULL;
    struct elem *pivot = Deque::Partition(left, right, newleft, newright);
    if (newleft != pivot)
    {
        struct elem *tmp = newleft;
        while (tmp->next != pivot)
            tmp = tmp->next;
        tmp->next = NULL;
        newleft = quicksortrecur(newleft, tmp);
        tmp = getTail(newleft);
        tmp->next =  pivot;
    }
    pivot->next = quicksortrecur(pivot->next, newright);
    return newleft;
}
void Deque::quickSort(Deque&d)
{
	d._left = quicksortrecur(d._left, getTail(d._left));
    return;
}

Select allOpen in new window

you did find the c source code i used as a base. you will have found out that it couldn't be used without making some changes.

so, if you don't mind, i will return to pseudo code (what gives you the chance to fully understand the code).

we now need a function always parting a list of elem nodes into two and call itself recursively for the two lists.

the signature of this function (we make it a static member function of Deque) is

void QuicksortList(elem * left, elem * right, elem *& newleft, elem *& newright);

Select allOpen in new window

the function gets the first and last node of the list to sort and has new first and new last as output. recursion ends if the function returns before calling itself again..

here the pseudo code (which follows the code you posted):

// check if list only has zero or one node
- if left equals right 
  + newleft is left
  + newright is right
  // recursion stops here
  + return 
- endif
- set newleft and newright to null
- create elem pointers pivot, tmp, leftleft, leftright, rightleft and init to null
- call Partition and pass left, right, newleft, newright
- store the return value into pivot
// If pivot is the smallest element - no need to recur for the left part.
- if newleft not equal to pivot
   // make the left list a separate list 
   + set tmp to newleft
   + while next of tmp is not equal to pivot 
         - set tmp to next of tmp
   + end while
   + call QuicksortList with newleft, tmp, leftleft, leftright as arguments
   + set newleft to leftleft
   + set next of leftright to pivot
- endif
// now sort right list and concatenate with pivot
- call QuicksortList and pass next of pivot, right, rightleft, newright as arguments
- set next of pivot to rightleft  

Select allOpen in new window

if that compiles you can create a non-static member function Quicksort() which calls QuicksortList and passes _left, _right, _left, _right  (note, the members are input and output arguments). after that call the print function.

Sara