Quick Sort Using Double Linked lIst
This code does not sort the data in first approach.When i enter the sorting option two to three time then it sort the data.I think the problem is in recursive part.I am trying to sort the linkedlist in the same way as we done in quick sort array.I also comment the array sorting lines.Kindly help me.

#include<iostream>
using namespace std;
class  Node{
private:
    int data;
    Node * Next;
    Node * Previous;
public:

    Node()
    {

    }
    ~Node()
    {

    }
   Node * insertt (Node * head, int value){
    Node * newNode=new Node ();
    newNode->Next=NULL;
    newNode->Previous=NULL;
    newNode->data=value;
    if(head==NULL)
    {

        head=newNode;
    }
    else{

        newNode->Next=head;
        head->Previous=newNode;
        head=newNode;

        }
        return head;

    }
 Node * lastNode(Node * root)
 {
        while(root && root->Next)
        {
            root=root->Next;
        }
        return root;
 }

Node *quickSort(Node * head)
{
           //Find Last Node
      Node * last=lastNode(head);



    _quickSort(head, last);
    return head;







}

Node * _quickSort(Node *Head, Node * Last)
{
    int tmp;
    Node * pivot=Last;
    Node * i=Head;
    Node * j=Last;
        //while(i<=j)
            while(i!=j && j!=NULL && i !=j->Next)
            {
                //while(arr[i]<mid)
                while(i->data<pivot->data  && i!=NULL)
                {
                     //i++;
                    i=i->Next;
                }
                //while(arr[j]>mid)
                while(j->data>pivot->data && j!=NULL)
                {
                    //j--
                    j=j->Previous;
                }
                //if(i<=j)
                if (i != j && j != NULL && i != j->Next)
                {
                          // tmp = arr[i];
                            tmp=i->data;
                            //arr[i] = arr[j];
                            i->data=j->data;
                             //arr[j] = tmp;
                             j->data=tmp;
                             //i++;
                             i=i->Next;
                             //j--;
                             j=j->Previous;
                }


            }
            //if (left < j)
            if(Head!=j && Head!=NULL )
            //    quickSort(arr, left, j);

           _quickSort(Head,j->Previous);
            //if (i < right)
           if(i!=Last && i!=NULL )
            // quickSort(arr, i, right);
            _quickSort(i->Next,Last);

            return Head;
}





        void Printt(Node * node)
    {
        cout << "\t\t" << node->data << endl;

    }
    void printSort(Node* head)
    {
        Node* ptr = head;
        cout << endl;
        while (ptr != NULL)
        {
            Printt(ptr);
            ptr = ptr->Next;
        }
        cout << endl << endl;
    }


};
int main(){
Node * Head=NULL;
Node  l;
int ch, v;
do
{
    cout<<"1- Add Data: "<<endl;
    cout<<"2- Sorting: "<<endl;
    cout<<"3- Exit !!!"<<endl;
    cin>>ch;
    switch(ch)
    {
    case 1:
        cout<<"Enter Data"<<endl;
        cin>>v;
        Head=l.insertt(Head,v);
        l.printSort(Head);
         break;
    case 2:

        Head=l.quickSort(Head);
        l.printSort(Head);
    case 3:
        break;
    default:
        cout<<"Invalid Choice"<<endl;
            break;
    }

}while(ch!=3);

}

When I had to sort a linked list in the past, I would put the nodes into an array and use qsort(), then take the sorted output and regenerate the list. Worked great, and was reasonably fast, even on old 8086 PC's with 256-640K of RAM. Of course, that limited the size of the list you could sort, but it worked well for our purposes (real-time manufacturing systems).

@rubberman.That is also a good option that we put the nodes into an array and use qsort().But can we correct this code?

This article has been dead for over six months. Start a new discussion instead.