Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- class node
- {
- public:
- int data;
- node * next;
- };
- node * newnode (int x);
- void quicksort(node ** begin, node ** end);
- int main (void)
- {
- int foo,n,i,j,k;
- node * temp;
- node * head = NULL;
- node * tail = NULL;
- cout<<"How many nodes do you want to insert\n";
- cin>>n;
- cout<<"Enter data of linked list\n";
- for ( i = 0; i < n; i++ )
- {
- cin>>foo;
- node * bar;
- if (head == NULL)
- {
- head = newnode(foo);
- tail = head;
- }
- else
- {
- bar = newnode(foo);
- tail->next = bar;
- tail = bar;
- }
- }
- cout<<"The linkedlist that you entered is as follows\n"; // Taking input
- temp = head;
- node * prev = NULL;
- while (temp != NULL)
- {
- cout<<temp->data<<"\t";
- prev = temp;
- temp = temp->next;
- }
- cout<<"\n";
- cout<<"Sorting the linked list now\n"; // Calling sort function
- quicksort(&head,&prev);
- temp = head;
- while (temp != NULL) // Printing output
- {
- cout<<temp->data<<"\t";
- temp = temp->next;
- }
- return 0;
- }
- node * newnode (int x) // for allocating a new node
- {
- node * foo = new node;
- foo->data = x;
- foo->next = NULL;
- return foo;
- }
- void quicksort(node ** begin, node ** end) // actual sort function
- {
- if (*begin == *end)
- return;
- node * pivot = *begin;
- node * temp = *begin;
- temp = temp->next; // for pointing to next element
- while (temp != *end)
- {
- if (temp->data < pivot->data)
- {
- node * temp1 = *begin; // swapping the two nodes if less than pivot
- *begin = temp;
- temp = temp->next;
- (*begin)->next = temp1;
- }
- else
- temp = temp->next; //else moving to next
- }
- quicksort(begin,&pivot); // calling for remaining elements (first half)
- quicksort(&(pivot->next),end); //for second half
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement