QuickSort on Doubly Linked List

Quicksort data structures are a way of sorting a list of items. This uses a divide and conquer approach. That is, the array of elements is divided into two parts and a quick sort algorithm is applied to these two parts. This matrix division is done using pivot points. The position of the pivot is chosen so that the element on the left side of the pivot is smaller than the pivot element and the element on the right side is larger than the pivot element. This partition is meant to get a linear run-time ordered array.

In C ++ implementation of a double-linked list. The idea is simple. First, find the pointer to the last node. Once you have a pointer to the last node, you can recursively sort the linked list using the pointers to the first and last node of the linked list. This is similar to the recursive function above, which passes the indices of the first and last element of the array. The linked list partition function is also similar to an array partition. Instead of returning the index of the pivot element, it returns a pointer to the pivot element. In the following implementation, quickSort () is just a wrapper function and the main recursive function is _quickSort (), similar to the quickSort () array implementation.

sort

For example:

sort

sort

sort

sort

Here Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
          public:
          int data;
          Node *next;
          Node *prev;
};
void swap ( int* a, int* b )
{ int t = *a; *a = *b; *b = t; }
          Node *lastNode(Node *root)
{
          while (root && root->next)
                   root = root->next;
          return root;
}
Node* partition(Node *l, Node *h)
{
          int x = h->data;
          Node *i = l->prev;
          for (Node *j = l; j != h; j = j->next)
          {
                   if (j->data <= x)
                   {
                             i = (i == NULL)? l : i->next;
                             swap(&(i->data), &(j->data));
                   }
          }
          i = (i == NULL)? l : i->next;
          swap(&(i->data), &(h->data));
          return i;
}
void _quickSort(Node* l, Node *h)
{
          if (h != NULL && l != h && l != h->next)
          {
                   Node *p = partition(l, h);
                   _quickSort(l, p->prev);
                   _quickSort(p->next, h);
          }
}
void quickSort(Node *head)
{
          Node *h = lastNode(head);
          _quickSort(head, h);
}
void printList(Node *head)
{
          while (head)
          {
                   cout << head->data << " ";
                   head = head->next;
          }
          cout << endl;
}
void push(Node** head_ref, int new_data)
{
          Node* new_node = new Node;
          new_node->data = new_data;
          new_node->prev = NULL;
          new_node->next = (*head_ref);
          if ((*head_ref) != NULL) (*head_ref)->prev = new_node ;
          (*head_ref) = new_node;
}
int main()
{
          Node *a = NULL;
          push(&a, 10);
          push(&a, 2);
          push(&a, -1);
          push(&a, 9);
          push(&a, 5);
          cout << "Linked List before sorting \n";
          printList(a);
          quickSort(a);
          cout << "Linked List after sorting \n";
          printList(a);
          return 0;
}

Complexity Analysis:

  • Time Complexity: Time complexity is O (n ^ 2) hours at worst, average, and O (nLogn) at best.

Conclusion:

The quick sort method uses the divide and conquer method to sort the items. It supports in-place caching and is also a queuing recursive algorithm. This is most preferred because arrays require a lot of access to items and linked lists take a long time.

Recommended Articles:

  1. Insertion in Doubly Linked List
  2. Deletion in Doubly Linked List
  3. How to reverse a doubly linked list?
  4. Merge Sort for Doubly Linked List
  5. How to reverse a string using stack?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 116 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] QuickSort on Doubly Linked List […]

You cannot copy content of this page
Scroll Up
1
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.