1.

Write a function to implement Quicksort on Doubly Linked List

Answer»


  • Input: 8<->10<->1<->7<->6


  • Output: 1<->6<->7<->8<->10

class Solution{
public:
Node* partition(Node *l, Node *h){
//Your code goes here
Node*temp = h;
Node*tt = l;
Node*first = l;

while(tt != h){
if(tt->data <= temp->data){
swap(first->data, tt->data);
first = first->next;
}
tt = tt -> next;
}
swap(first-> data, h->data);
return first;

}
};

void _quickSort(struct Node* l, struct Node *h)
{
if (h != NULL && l != h && l != h->next)
{
Solution ob;
struct Node *p = ob.partition(l, h);
_quickSort(l, p->prev);
_quickSort(p->next, h);
}
}

void quickSort(struct Node *head)
{
struct Node *h = lastNode(head);
_quickSort(head, h);
}


  • Time Complexity: O(n^2) in the worst case when the list is already sorted. O(nlog(n)) in the best and average case.


  • Space Complexity: O(n)


Discussion

No Comment Found

Related InterviewSolutions