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;
{

}
else{

}

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

{
//Find Last Node

}

Node * _quickSort(Node *Head, Node * Last)
{
int tmp;
Node * pivot=Last;
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)
//    quickSort(arr, left, j);

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

}

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

}
{
cout << endl;
while (ptr != NULL)
{
Printt(ptr);
ptr = ptr->Next;
}
cout << endl << endl;
}

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

case 3:
break;
default:
cout<<"Invalid Choice"<<endl;
break;
}

}while(ch!=3);

}
``````

All 5 Replies

Why is everyone trying to quicksort a linked list?

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?

@Duos .Beacuse quicksort is a bit tricky

Quicksort over a non-random access sequence is, I admit, tricky.

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.