struct node *lastNode(node *root){ while (root && root->next) root = root->next; return root;}/* Considers last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */node* partition(node *l, node *h){ // set pivot as h element int x = h->data; // similar to i = l-1 for array implementation node *i = l->prev; // Similar to "for (int j = l; j <= h- 1; j++)" for (node *j = l; j != h; j = j->next) { if (j->data <= x) { // Similar to i++ for array i = (i == NULL)? l : i->next; swap(&(i->data), &(j->data)); } } i = (i == NULL)? l : i->next; // Similar to i++ swap(&(i->data), &(h->data)); return i;}/* A recursive implementation of quicksort for linked list */void _quickSort(struct node* l, struct node *h){ if (h != NULL && l != h && l != h->next) { struct node *p = partition(l, h); _quickSort(l, p->prev); _quickSort(p->next, h); }}// The main function to sort a linked list. It mainly calls _quickSort()void quickSort(struct node *head){ // Find last node struct node *h = lastNode(head); // Call the recursive QuickSort _quickSort(head, h);}On Array
int partition (int arr[], int l, int h){ int x = arr[h]; int i = (l - 1); for (int j = l; j <= h- 1; j++) { if (arr[j] <= x) { i++; swap (&arr[i], &arr[j]); } } swap (&arr[i + 1], &arr[h]); return (i + 1);}/* A[] --> Array to be sorted, l --> Starting index, h --> Ending index */void quickSort(int A[], int l, int h){ if (l < h) { int p = partition(A, l, h); /* Partitioning index */ quickSort(A, l, p - 1); quickSort(A, p + 1, h); }http://www.acmerblog.com/leetcode-sort-list-5982.html
Read full article from QuickSort on Doubly Linked List | GeeksforGeeks
