Quick Sort on Doubly Linked List

The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage. As a trade-off, however, it is possible that the list may not be divided in half.

Algorithm:

• Quick Sort Method
• • Get a pivot element from list or array by partitioning algorithm
  • Recursive call quick sort method for first part partition which is less than pivot and
  • Recursive call quick sort method for half part partition which is greater than or equal to pivot
• Partition Method
• • For partition divide list or array in three buckets, that is
  • • element less than pivot (handled by i)
    • element equal to pivot (handled by pivot)
    • element greater than pivot (handled by j)
  • Set values
  • • Pivot = high
    • i = null
    • j = low
  • iterate below code till j != high
  • if list.i < list.pivot then
  • • i = (i == null) ? low : i.next
    • now swap ith data with jth data
  • j = j.next
  • iterate below code till j != high
  • if list.i < list.pivot then
  • • i = (i == null) ? low : i.next
    • now swap ith data with jth data
  • return i

Wiki

Tutorial Video

Latest Source Code:
Github: QuickSortUsingDLL.java

Output:

10 2 6 49 5 12 7 19 
2 5 6 7 10 12 19 49