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);
}
