{"id":25244,"date":"2017-10-15T16:18:20","date_gmt":"2017-10-15T10:48:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25244"},"modified":"2017-10-15T16:18:20","modified_gmt":"2017-10-15T10:48:20","slug":"quicksort-singly-linked-list-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/quicksort-singly-linked-list-2\/","title":{"rendered":"QuickSort on Singly Linked List"},"content":{"rendered":"<p>Quick Sort on Doubly Linked List is discussed <a href=\"http:\/\/www.geeksforgeeks.org\/quicksort-for-linked-list\/\" target=\"_blank\" rel=\"noopener noreferrer\">here<\/a>. Quick Sort on Singly linked list was given as an exercise. Following is C++ implementation for same. <span id=\"more-119900\"><\/span>The important things about implementation are, it changes pointers rather swapping data and time complexity is same as the implementation for Doubly Linked List.<br \/>\nIn <strong>partition()<\/strong>, we consider last element as pivot. We traverse through the current list and if a node has value greater than pivot, we move it after tail. If the node has smaller value, we keep it at its current position.<br \/>\nIn <strong>QuickSortRecur()<\/strong>, we first call partition() which places pivot at correct position and returns pivot. After pivot is placed at correct position, we find tail node of left side (list before pivot) and recur for left list. Finally, we recur for right list.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20for%20Quick%20Sort%20on%20Singly%20Linled%20List%0A%23include%20%3Ciostream%3E%0A%23include%20%3Ccstdio%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20a%20node%20of%20the%20singly%20linked%20list%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20A%20utility%20function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%20new%20node%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20print%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%20%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20the%20last%20node%20of%20the%20list%0Astruct%20node%20*getTail(struct%20node%20*cur)%0A%7B%0A%20%20%20%20while%20(cur%20!%3D%20NULL%20%26%26%20cur-%3Enext%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20cur%20%3D%20cur-%3Enext%3B%0A%20%20%20%20return%20cur%3B%0A%7D%0A%20%0A%2F%2F%20Partitions%20the%20list%20taking%20the%20last%20element%20as%20the%20pivot%0Astruct%20node%20*partition(struct%20node%20*head%2C%20struct%20node%20*end%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20struct%20node%20**newHead%2C%20struct%20node%20**newEnd)%0A%7B%0A%20%20%20%20struct%20node%20*pivot%20%3D%20end%3B%0A%20%20%20%20struct%20node%20*prev%20%3D%20NULL%2C%20*cur%20%3D%20head%2C%20*tail%20%3D%20pivot%3B%0A%20%0A%20%20%20%20%2F%2F%20During%20partition%2C%20both%20the%20head%20and%20end%20of%20the%20list%20might%20change%0A%20%20%20%20%2F%2F%20which%20is%20updated%20in%20the%20newHead%20and%20newEnd%20variables%0A%20%20%20%20while%20(cur%20!%3D%20pivot)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(cur-%3Edata%20%3C%20pivot-%3Edata)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20First%20node%20that%20has%20a%20value%20less%20than%20the%20pivot%20-%20becomes%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20the%20new%20head%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20((*newHead)%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(*newHead)%20%3D%20cur%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20cur%3B%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20cur%20%3D%20cur-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20If%20cur%20node%20is%20greater%20than%20pivot%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Move%20cur%20node%20to%20next%20of%20tail%2C%20and%20change%20tail%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(prev)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prev-%3Enext%20%3D%20cur-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20struct%20node%20*tmp%20%3D%20cur-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20cur-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20tail-%3Enext%20%3D%20cur%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20tail%20%3D%20cur%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20cur%20%3D%20tmp%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20the%20pivot%20data%20is%20the%20smallest%20element%20in%20the%20current%20list%2C%0A%20%20%20%20%2F%2F%20pivot%20becomes%20the%20head%0A%20%20%20%20if%20((*newHead)%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20(*newHead)%20%3D%20pivot%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20newEnd%20to%20the%20current%20last%20node%0A%20%20%20%20(*newEnd)%20%3D%20tail%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20pivot%20node%0A%20%20%20%20return%20pivot%3B%0A%7D%0A%20%0A%20%0A%2F%2Fhere%20the%20sorting%20happens%20exclusive%20of%20the%20end%20node%0Astruct%20node%20*quickSortRecur(struct%20node%20*head%2C%20struct%20node%20*end)%0A%7B%0A%20%20%20%20%2F%2F%20base%20condition%0A%20%20%20%20if%20(!head%20%7C%7C%20head%20%3D%3D%20end)%0A%20%20%20%20%20%20%20%20return%20head%3B%0A%20%0A%20%20%20%20node%20*newHead%20%3D%20NULL%2C%20*newEnd%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20Partition%20the%20list%2C%20newHead%20and%20newEnd%20will%20be%20updated%0A%20%20%20%20%2F%2F%20by%20the%20partition%20function%0A%20%20%20%20struct%20node%20*pivot%20%3D%20partition(head%2C%20end%2C%20%26newHead%2C%20%26newEnd)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20pivot%20is%20the%20smallest%20element%20-%20no%20need%20to%20recur%20for%0A%20%20%20%20%2F%2F%20the%20left%20part.%0A%20%20%20%20if%20(newHead%20!%3D%20pivot)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Set%20the%20node%20before%20the%20pivot%20node%20as%20NULL%0A%20%20%20%20%20%20%20%20struct%20node%20*tmp%20%3D%20newHead%3B%0A%20%20%20%20%20%20%20%20while%20(tmp-%3Enext%20!%3D%20pivot)%0A%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20tmp-%3Enext%3B%0A%20%20%20%20%20%20%20%20tmp-%3Enext%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20the%20list%20before%20pivot%0A%20%20%20%20%20%20%20%20newHead%20%3D%20quickSortRecur(newHead%2C%20tmp)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Change%20next%20of%20last%20node%20of%20the%20left%20half%20to%20pivot%0A%20%20%20%20%20%20%20%20tmp%20%3D%20getTail(newHead)%3B%0A%20%20%20%20%20%20%20%20tmp-%3Enext%20%3D%20%20pivot%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Recur%20for%20the%20list%20after%20the%20pivot%20element%0A%20%20%20%20pivot-%3Enext%20%3D%20quickSortRecur(pivot-%3Enext%2C%20newEnd)%3B%0A%20%0A%20%20%20%20return%20newHead%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20for%20quick%20sort.%20This%20is%20a%20wrapper%20over%20recursive%0A%2F%2F%20function%20quickSortRecur()%0Avoid%20quickSort(struct%20node%20**headRef)%0A%7B%0A%20%20%20%20(*headRef)%20%3D%20quickSortRecur(*headRef%2C%20getTail(*headRef))%3B%0A%20%20%20%20return%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20node%20*a%20%3D%20NULL%3B%0A%20%20%20%20push(%26a%2C%205)%3B%0A%20%20%20%20push(%26a%2C%2020)%3B%0A%20%20%20%20push(%26a%2C%204)%3B%0A%20%20%20%20push(%26a%2C%203)%3B%0A%20%20%20%20push(%26a%2C%2030)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Linked%20List%20before%20sorting%20%5Cn%22%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20quickSort(%26a)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Linked%20List%20after%20sorting%20%5Cn%22%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\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[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>QuickSort on Singly Linked List &#8211; Searching and sorting &#8211; Quick Sort on Doubly Linked List is discussed here.In Singly linked list was given as an exercise. Following is C++ implementation for same.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83511,83502,71670],"tags":[72497,72498,72495,70238,72484,71130,72501,72394,72483,72418,72481,72490,70233,72502,72494,72482,72488,72396,72480,72405,72485,72487,72479,72500,72493,72398,70262,71274,71892,71306,72408,72496,71693,70046,71717,71303,71265,70977,72492,72478,72503,72489,72499,72486,71299,72491,72395,71676,71142],"class_list":["post-25244","post","type-post","status-publish","format-standard","hentry","category-linked-lists","category-quick-sort","category-searching-and-sorting","tag-algorithm-for-linked-list","tag-algorithm-for-singly-linked-list","tag-algorithm-of-linked-list-in-data-structure","tag-algorithms-and-data-structures","tag-algorithms-in-java","tag-bubble-sort-in-data-structure","tag-bubble-sort-linked-list","tag-bubble-sort-linked-list-c","tag-c-linked-list","tag-c-quicksort","tag-circular-linked-list","tag-data-structure-linked-list","tag-data-structures-and-algorithms","tag-doubly-linked-list-c","tag-insertion-sort-linked-list","tag-java-list-sort","tag-java-merge-lists","tag-java-merge-sort","tag-java-sort-list","tag-linked-list-algorithm","tag-linked-list-c","tag-linked-list-data-structure","tag-linked-list-in-data-structure","tag-linked-list-merge-sort","tag-linked-list-program","tag-linked-list-sort","tag-merge-sort","tag-merge-sort-algorithm-in-data-structure","tag-merge-sort-algorithm-java","tag-merge-sort-linked-list","tag-merge-sort-linked-list-java","tag-merge-sort-using-linked-list","tag-quick-sort-program-in-c","tag-quicksort","tag-quicksort-animation","tag-quicksort-code","tag-quicksort-example","tag-quicksort-java","tag-quicksort-linked-list","tag-quicksort-on-singly-linked-list","tag-singly-linked-list","tag-singly-linked-list-algorithm","tag-singly-linked-list-in-data-structure-program","tag-sort-link","tag-sort-linked-list","tag-sort-linked-list-java","tag-sort-list-java","tag-sorting-a-linked-list","tag-sorting-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25244","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=25244"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25244\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25244"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25244"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}