{"id":27421,"date":"2018-02-02T21:24:12","date_gmt":"2018-02-02T15:54:12","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27421"},"modified":"2018-11-01T11:07:18","modified_gmt":"2018-11-01T05:37:18","slug":"quicksort-doubly-linked-list-3","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/quicksort-doubly-linked-list-3\/","title":{"rendered":"QuickSort on Doubly Linked List"},"content":{"rendered":"<p><span style=\"color: #003366;\"><strong>Java Program: QuickSort on doubly linked list<\/strong><\/span><\/p>\n<p>Following is a typical recursive implementation of <a href=\"http:\/\/en.wikipedia.org\/wiki\/Quicksort\">QuickSort<\/a> for arrays. The implementation uses last element as pivot.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20A%20typical%20recursive%20implementation%20of%20Quicksort%20for%20array*%2F%0A%20%0A%2F*%20This%20function%20takes%20last%20element%20as%20pivot%2C%20places%20the%20pivot%20element%20at%20its%0A%20%20%20correct%20position%20in%20sorted%20array%2C%20and%20places%20all%20smaller%20(smaller%20than%20%0A%20%20%20pivot)%20to%20left%20of%20pivot%20and%20all%20greater%20elements%20to%20right%20of%20pivot%20*%2F%0Aint%20partition%20(int%20arr%5B%5D%2C%20int%20l%2C%20int%20h)%0A%7B%0A%20%20%20%20int%20x%20%3D%20arr%5Bh%5D%3B%0A%20%20%20%20int%20i%20%3D%20(l%20-%201)%3B%0A%20%0A%20%20%20%20for%20(int%20j%20%3D%20l%3B%20j%20%3C%3D%20h-%201%3B%20j%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20swap%20(%26arr%5Bi%5D%2C%20%26arr%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20swap%20(%26arr%5Bi%20%2B%201%5D%2C%20%26arr%5Bh%5D)%3B%0A%20%20%20%20return%20(i%20%2B%201)%3B%0A%7D%0A%20%0A%2F*%20A%5B%5D%20\u2013%3E%20Array%20to%20be%20sorted%2C%20l%20%20\u2013%3E%20Starting%20index%2C%20h%20%20\u2013%3E%20Ending%20index%20*%2F%0Avoid%20quickSort(int%20A%5B%5D%2C%20int%20l%2C%20int%20h)%0A%7B%0A%20%20%20%20if%20(l%20%3C%20h)%0A%20%20%20%20%7B%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20int%20p%20%3D%20partition(A%2C%20l%2C%20h)%3B%20%2F*%20Partitioning%20index%20*%2F%0A%20%20%20%20%20%20%20%20quickSort(A%2C%20l%2C%20p%20-%201)%3B%20%20%0A%20%20%20%20%20%20%20%20quickSort(A%2C%20p%20%2B%201%2C%20h)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<h3 id=\"can-we-use-same-algorithm-for-linked-list\"><span style=\"color: #0000ff;\"><strong>Can we use same algorithm for Linked List?<\/strong><\/span><\/h3>\n<p>Following is <a href=\"https:\/\/www.wikitechy.com\/technology\/java-algorithm-pairwise-swap-elements-given-linked-list\/\" target=\"_blank\" rel=\"noopener\">Java implementation<\/a> for doubly linked list. The idea is simple, we first find out pointer to last node. Once we have pointer to last node, we can recursively <a href=\"https:\/\/www.wikitechy.com\/forum\/d\/32-how-can-we-sort-javascript-object-array-by-date\" target=\"_blank\" rel=\"noopener\">sort<\/a> the linked list using <a href=\"https:\/\/www.wikitechy.com\/tutorials\/c-programming\/pointer-to-pointer-in-c\" target=\"_blank\" rel=\"noopener\">pointers<\/a> to first and last nodes of linked list, similar to the above recursive function where we pass indexes of first and last array elements. The partition function for <a href=\"https:\/\/www.wikitechy.com\/technology\/java-algorithm-swap-nodes-linked-list-without-swapping-data\/\" target=\"_blank\" rel=\"noopener\">linked list<\/a> is also similar to partition for arrays. Instead of returning index of the pivot element, it returns pointer to the pivot element. In the following implementation, quickSort() is just a wrapper function, the main recursive function is <strong>_quickSort()<\/strong> which is similar to <strong>quickSort()<\/strong> for array implementation.<\/p>\n<h3 id=\"java-programming-for-quicksort-on-doubly-linked-list\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27435\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL-1-1.png\" alt=\"QuickSort on Doubly Linked List\" width=\"553\" height=\"112\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL-1-1.png 553w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL-1-1-300x61.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL-1-1-550x112.png 550w\" sizes=\"(max-width: 553px) 100vw, 553px\" \/><span style=\"color: #ff0000;\">Java Programming for QuickSort on Doubly Linked List<\/span><\/h3>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20A%20Java%20program%20to%20sort%20a%20linked%20list%20using%20Quicksort%0Aclass%20QuickSort_using_Doubly_LinkedList%7B%0A%20%20%20%20Node%20head%3B%0A%20%20%20%0A%2F*%20a%20node%20of%20the%20doubly%20linked%20list%20*%2F%20%0A%20%20%20%20static%20class%20Node%7B%0A%20%20%20%20%20%20%20%20private%20int%20data%3B%0A%20%20%20%20%20%20%20%20private%20Node%20next%3B%0A%20%20%20%20%20%20%20%20private%20Node%20prev%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%2F%2F%20A%20utility%20function%20to%20find%20last%20node%20of%20linked%20list%20%20%20%20%0A%20%20%20%20Node%20lastNode(Node%20node)%7B%0A%20%20%20%20%20%20%20%20while(node.next!%3Dnull)%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20return%20node%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%0A%2F*%20Considers%20last%20element%20as%20pivot%2C%20places%20the%20pivot%20element%20at%20its%0A%20%20%20correct%20position%20in%20sorted%20array%2C%20and%20places%20all%20smaller%20(smaller%20than%0A%20%20%20pivot)%20to%20left%20of%20pivot%20and%20all%20greater%20elements%20to%20right%20of%20pivot%20*%2F%0A%20%20%20%20Node%20partition(Node%20l%2CNode%20h)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20set%20pivot%20as%20h%20element%0A%20%20%20%20%20%20%20%20int%20x%20%3D%20h.data%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20similar%20to%20i%20%3D%20l-1%20for%20array%20implementation%0A%20%20%20%20%20%20%20%20Node%20i%20%3D%20l.prev%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Similar%20to%20%22for%20(int%20j%20%3D%20l%3B%20j%20%3C%3D%20h-%201%3B%20j%2B%2B)%22%0A%20%20%20%20%20%20%20%20for(Node%20j%3Dl%3B%20j!%3Dh%3B%20j%3Dj.next)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if(j.data%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Similar%20to%20i%2B%2B%20for%20array%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20(i%3D%3Dnull)%20%3F%20l%20%3A%20i.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%20%3D%20i.data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i.data%20%3D%20j.data%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j.data%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20i%20%3D%20(i%3D%3Dnull)%20%3F%20l%20%3A%20i.next%3B%20%20%2F%2F%20Similar%20to%20i%2B%2B%0A%20%20%20%20%20%20%20%20int%20temp%20%3D%20i.data%3B%0A%20%20%20%20%20%20%20%20i.data%20%3D%20h.data%3B%0A%20%20%20%20%20%20%20%20h.data%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20A%20recursive%20implementation%20of%20quicksort%20for%20linked%20list%20*%2F%0A%20%20%20%20void%20_quickSort(Node%20l%2CNode%20h)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if(h!%3Dnull%20%26%26%20l!%3Dh%20%26%26%20l!%3Dh.next)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20Node%20temp%20%3D%20partition(l%2Ch)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20_quickSort(l%2Ctemp.prev)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20_quickSort(temp.next%2Ch)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20The%20main%20function%20to%20sort%20a%20linked%20list.%20It%20mainly%20calls%20_quickSort()%0A%20%20%20%20public%20void%20quickSort(Node%20node)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20last%20node%0A%20%20%20%20%20%20%20%20Node%20head%20%3D%20lastNode(node)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Call%20the%20recursive%20QuickSort%0A%20%20%20%20%20%20%20%20_quickSort(node%2Chead)%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%20%2F%2F%20A%20utility%20function%20to%20print%20contents%20of%20arr%0A%20%20%20%20%20public%20void%20printList(Node%20head)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20while(head!%3Dnull)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(head.data%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20head.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20Doubly%20Linked%20List%20*%2F%0A%20%20%20%20void%20push(int%20new_Data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20new_Node%20%3D%20new%20Node(new_Data)%3B%20%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20head%20is%20null%2C%20head%20%3D%20new_Node%0A%20%20%20%20%20%20%20%20if(head%3D%3Dnull)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20new_Node%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20new_Node.next%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20head.prev%20%3D%20new_Node%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20begining%2C%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20%20%20%20%20new_Node.prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_Node%3B%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20QuickSort_using_Doubly_LinkedList%20list%20%3D%20new%20QuickSort_using_Doubly_LinkedList()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20list.push(5)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.push(20)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.push(4)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.push(3)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.push(30)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Linked%20List%20before%20sorting%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.printList(list.head)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22%5CnLinked%20List%20after%20sorting%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.quickSort(list.head)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20list.printList(list.head)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #339966;\">Output :<\/span><\/h3>\n<pre>Linked List before sorting\r\n30  3  4  20  5\r\nLinked List after sorting\r\n3  4  5  20  30<\/pre>\n<p><strong><span style=\"color: #33cccc;\">Time Complexity:<\/span> <\/strong>Time complexity of the above implementation is same as time complexity of QuickSort() for arrays. It takes <strong>O(n^2)<\/strong> time in worst case and<strong> O(nLogn)<\/strong> in average and best cases. The worst case occurs when the linked list is already sorted.<\/p>\n<h3 id=\"can-we-implement-random-quick-sort-for-linked-list\"><span style=\"color: #993366;\">Can we implement random quick sort for linked list?<\/span><\/h3>\n<p><a href=\"https:\/\/www.wikitechy.com\/technology\/quick-sort-preferred-arrays-merge-sort-linked-lists-2\/\" target=\"_blank\" rel=\"noopener\">Quicksort<\/a> can be implemented for Linked List only when we can pick a fixed point as pivot (like last element in above implementation). Random <a href=\"https:\/\/www.wikitechy.com\/technology\/quicksort-doubly-linked-list-3\/\" target=\"_blank\" rel=\"noopener\">QuickSort<\/a> cannot be efficiently implemented for Linked Lists by picking random pivot.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Quick Sort on Doubly Linked List &#8211; Doubly Linked List &#8211; The partition function for linked list is also similar to partition for arrays. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79479,2139,79476],"tags":[81557,81554,81553,81556,81555,72492,81552,81551],"class_list":["post-27421","post","type-post","status-publish","format-standard","hentry","category-doubly-linked-list","category-java","category-linked-list","tag-bubble-sort-doubly-linked-list-c","tag-merge-sort-doubly-linked-list-c","tag-quick-sort-doubly-linked-list-c","tag-quick-sort-singly-linked-list-c","tag-quick-sort-singly-linked-list-java","tag-quicksort-linked-list","tag-quicksort-linked-list-java","tag-sort-doubly-linked-list-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27421","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27421"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27421\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27421"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27421"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27421"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}