{"id":5267,"date":"2021-09-28T11:50:18","date_gmt":"2021-09-28T11:50:18","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5267"},"modified":"2023-07-31T05:04:46","modified_gmt":"2023-07-31T05:04:46","slug":"quicksort-on-singly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/","title":{"rendered":"QuickSort on Singly Linked List"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg\" alt=\"\" \/><\/p>\n<p>QuickSort is a popular sorting algorithm known for its efficiency in sorting arrays. However, when it comes to sorting a singly linked list, a few modifications are needed to adapt the algorithm. In this explanation, I will provide an introduction to quick sort in linked list.<\/p>\n<p>The QuickSort algorithm follows the divide-and-conquer approach. It works by selecting a pivot element from the list and partitioning the other elements into two sub-lists, according to whether they are less than or greater than the pivot. The algorithm then recursively sorts the sub-lists until the entire list is sorted. Let\u2019s see, what is a quick sort using linked list in C programming.<\/p>\n<h3>What is quick sort in linked list?<\/h3>\n<ul>\n<li>QuickSort is a Divide and Conquer algorithm, so it is also a recursive algorithm. <\/li>\n<li>Here, We pick an element as a pivot and partition the given array around the picked pivot element. <\/li>\n<li>After partition, we arrange the elements such that all the elements smaller than the pivot element will be before the pivot, and all the elements greater than the pivot element will be after the pivot. <\/li>\n<li>After this, we will call Quick sort again on the elements from <strong>starting<\/strong> to <strong>pivot-1<\/strong> and <strong>pivot+1<\/strong> to the <strong>end<\/strong>. <\/li>\n<li>We will continue to call Quick sort till we hit the base case.<\/li>\n<\/ul>\n<h3>How to perform Quick Sort on Singly linked list<\/h3>\n<p>According to the problem statement, We will be given a linked list and we need to sort the list using the quick sort sorting algorithm.<\/p>\n<p>Before going to the approach section to apply quick sort on linked list, we need to understand Quicksort Algorithm thoroughly. It is easier to understand the QuickSort algorithm on an array; that\u2019s why we will first learn to apply quicksort on an array, and then learn how to apply the quicksort on singly linked list<\/p>\n<h3>Algorithm of Quick Sort<\/h3>\n<ul>\n<li>We have to first pick an element of the array as a pivot.<\/li>\n<li>We can choose any element as a <strong>pivot<\/strong> element, e.g. starting element of the array, last element of the array, middle element of the array, etc.<\/li>\n<li>We will take the <strong>first element<\/strong> of the array as the <strong>pivot<\/strong> element.<\/li>\n<li>Now we will count the number of elements that are <strong>smaller<\/strong> than the <strong>pivot element<\/strong> in the array.<\/li>\n<li>Now we have to move the <strong>pivot element<\/strong> to its <strong>correct position<\/strong> in the array.<\/li>\n<li>Initialize <strong>K = 0<\/strong>, <strong>K<\/strong> is the correct position of the pivot element.\n<ul>\n<li><strong>K = (pivot index + the number of elements smaller than the pivot element in the array)<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<li>After <strong>swapping<\/strong> the <strong>pivot element<\/strong> with the element at the index <strong>K<\/strong>, arrange the elements such that all elements smaller than the pivot element will be before the pivot, and all elements greater than the pivot element will be after the pivot.<\/li>\n<li>After this, we will call Quicksort again on the elements from <strong>starting index<\/strong> to <strong>pivot-1<\/strong> and <strong>pivot+1<\/strong> to the <strong>end index<\/strong>. We will continue to call Quicksort till we hit the base case.<\/li>\n<\/ul>\n<h3>Dry Run<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1-28.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2-28.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_3-16.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_4_5.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_12_13.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_14_15.png\" alt=\"\" \/><\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5268 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_5268 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_5268 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5268 .wpsm_nav-tabs > li.active > a, #tab_container_5268 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5268 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_5268 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_5268 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5268 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5268 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5268 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5268 .wpsm_nav-tabs > li > a:hover , #tab_container_5268 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_5268 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_5268 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_5268 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_5268 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_5268 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_5268 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_5268 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5268 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_5268 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5268 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_5268 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_5268\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5268\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5268_1\" aria-controls=\"tabs_desc_5268_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5268_2\" aria-controls=\"tabs_desc_5268_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5268_3\" aria-controls=\"tabs_desc_5268_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_5268\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_5268_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include&lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n\r\nint partition(int* arr, int si, int ei){\r\n\r\n    int count = 0;\r\n    \/\/ count of numbers of elements smaller than arr[0]\r\n\r\n    int i = si+1;\r\n    while(i&lt;=ei){\r\n        if(arr[i]&lt;arr[si]){\r\n            count++;\r\n        }\r\n        i++;\r\n    }\r\n\r\n    int pivot = si + count;\r\n\r\n    swap(arr[si], arr[pivot]);\r\n    \r\n    int k = si;\r\n    int j = ei;\r\n\r\n\r\n    \/\/ Arrange elements such that all elements before pivot \r\n    \/\/ will be smaller than pivot element and all elements greater than pivot element after pivot.\r\n    while(k&lt;pivot &amp;&amp; j&gt;pivot){\r\n        if(arr[k]&gt;arr[pivot] &amp;&amp; arr[j]&lt;arr[pivot]){\r\n            swap(arr[k], arr[j]);\r\n            k++;\r\n            j--;\r\n        }else if(arr[k]&lt;arr[pivot]){\r\n            k++;\r\n        }else if(arr[j]&gt;arr[pivot]){\r\n            j--;\r\n        }\r\n    }\r\n\r\n    return pivot;\r\n}\r\n\r\n\r\nvoid quickSort(int* arr, int si, int ei){\r\n    \/\/Base case\r\n    if(si&gt;=ei){\r\n        return;\r\n    }\r\n\r\n\r\n    \/\/ function for partition around pivot\r\n    int pivot = partition(arr, si, ei);\r\n\r\n    quickSort(arr, si, pivot-1);\r\n    quickSort(arr, pivot+1, ei);\r\n}\r\n\r\nint main(){\r\n    int n;\r\n    cin&gt;&gt;n;\r\n\r\n    int* arr = new int[n];\r\n\r\n    for(int i=0; i&lt;n; i++){\r\n        cin&gt;&gt;arr[i];\r\n    }\r\n\r\n    quickSort(arr, 0, n-1);\r\n\r\n    for(int i=0; i&lt;n; i++){\r\n        cout&lt;&lt;arr[i]&lt;&lt;&quot; &quot;;\r\n    }\r\n}\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5268_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\npublic class QuickSort \r\n{\r\n\tstatic class Node \r\n    {\r\n\t\tint data;\r\n\t\tNode next;\r\n\t\tNode(int d)\r\n\t\t{\r\n\t\t\tthis.data = d;\r\n\t\t\tthis.next = null;\r\n\t\t}\r\n\t}\r\n\tNode head;\r\n\r\n\tvoid addNode(int data)\r\n\t{\r\n\t\tif (head == null) {\r\n\t\t\thead = new Node(data);\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tNode curr = head;\r\n\t\twhile (curr.next != null)\r\n\t\t\tcurr = curr.next;\r\n\r\n\t\tNode newNode = new Node(data);\r\n\t\tcurr.next = newNode;\r\n\t}\r\n\tvoid printList(Node n)\r\n\t{\r\n\t\twhile (n != null) {\r\n\t\t\tSystem.out.print(n.data);\r\n\t\t\tSystem.out.print(&quot; &quot;);\r\n\t\t\tn = n.next;\r\n\t\t}\r\n\t}\r\n\t\/* takes first and last node,but do not break any links in\r\n\tthe whole linked list *\/\r\n\tNode paritionLast(Node start, Node end)\r\n\t{\r\n\t\tif (start == end || start == null || end == null)\r\n\t\t\treturn start;\r\n\r\n\t\tNode pivot_prev = start;\r\n\t\tNode curr = start;\r\n\t\tint pivot = end.data;\r\n\r\n\t\t\/* iterate till one before the end, no need to iterate till the end\r\n\t\tbecause end is pivot *\/\r\n\t\twhile (start != end) \r\n        {\r\n\t\t\tif (start.data &lt; pivot) {\r\n\t\t\t\t\/\/ keep tracks of last modified item\r\n\t\t\t\tpivot_prev = curr;\r\n\t\t\t\tint temp = curr.data;\r\n\t\t\t\tcurr.data = start.data;\r\n\t\t\t\tstart.data = temp;\r\n\t\t\t\tcurr = curr.next;\r\n\t\t\t}\r\n\t\t\tstart = start.next;\r\n\t\t}\r\n\t\t\/\/ swap the position of curr i.e. next suitable index and pivot\r\n\t\tint temp = curr.data;\r\n\t\tcurr.data = pivot;\r\n\t\tend.data = temp;\r\n\t\t\/* return one previous to current\r\n\t\t because current is now pointing to pivot\/ *\/\r\n\t\treturn pivot_prev;\r\n\t}\r\n\tvoid sort(Node start, Node end)\r\n\t{\r\n\t\tif(start == null || start == end|| start == end.next )\r\n\t\t\treturn;\r\n\r\n\t\t\/\/ split list and partition recurse\r\n\t\tNode pivot_prev = paritionLast(start, end);\r\n\t\tsort(start, pivot_prev);\r\n\r\n\t\t\/\/ if pivot is picked and moved to the start,\r\n\t\t\/\/ that means start and pivot is same\r\n\t\t\/\/ so pick from next of pivot\r\n\t\tif (pivot_prev != null &amp;&amp; pivot_prev == start)\r\n\t\t\tsort(pivot_prev.next, end);\r\n\r\n\t\t\/\/ if pivot is in between of the list,\r\n\t\t\/\/ start from next of pivot,\r\n\t\t\/\/ since we have pivot_prev, so we move two nodes\r\n\t\telse if (pivot_prev != null\r\n\t\t\t\t&amp;&amp; pivot_prev.next != null)\r\n\t\t\tsort(pivot_prev.next.next, end);\r\n\t}\r\n\t\/\/ Driver Code\r\npublic static void main(String[] args)\r\n    {\r\n\t\tQuickSort list= new QuickSort();\r\n\t\tlist.addNode(30);\r\n\t\tlist.addNode(3);\r\n\t\tlist.addNode(4);\r\n\t\tlist.addNode(20);\r\n\t\tlist.addNode(5);\r\n\r\n\t\tNode n = list.head;\r\n\t\twhile (n.next != null)\r\n\t\t\tn = n.next;\r\n\r\n\t\tSystem.out.println(&quot;Linked List before sorting&quot;);\r\n\t\tlist.printList(list.head);\r\n\r\n\t\tlist.sort(list.head, n);\r\n\r\n\t\tSystem.out.println(&quot;&#92;nLinked List after sorting&quot;);\r\n\t\tlist.printList(list.head);\r\n\t}\r\n}\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5268_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass Node:\r\n\tdef __init__(self, val):\r\n\t\tself.data = val\r\n\t\tself.next = None\r\n\r\nclass QuickSortLinkedList:\r\n\r\n\tdef __init__(self):\r\n\t\tself.head=None\r\n\r\n\tdef addNode(self,data):\r\n\t\tif (self.head == None):\r\n\t\t\tself.head = Node(data)\r\n\t\t\treturn\r\n\r\n\t\tcurr = self.head\r\n\t\twhile (curr.next != None):\r\n\t\t\tcurr = curr.next\r\n\r\n\t\tnewNode = Node(data)\r\n\t\tcurr.next = newNode\r\n\r\n\tdef printList(self,n):\r\n\t\twhile (n != None):\r\n\t\t\tprint(n.data, end=&quot; &quot;)\r\n\t\t\tn = n.next\r\n\r\n\tdef paritionLast(self,start, end):\r\n\t\tif (start == end or start == None or end == None):\r\n\t\t\treturn start\r\n\r\n\t\tpivot_prev = start\r\n\t\tcurr = start\r\n\t\tpivot = end.data\r\n\r\n\r\n\t\twhile (start != end):\r\n\t\t\tif (start.data &lt; pivot):\r\n\t\t\t\r\n\t\t\t\tpivot_prev = curr\r\n\t\t\t\ttemp = curr.data\r\n\t\t\t\tcurr.data = start.data\r\n\t\t\t\tstart.data = temp\r\n\t\t\t\tcurr = curr.next\r\n\t\t\tstart = start.next\r\n\r\n\r\n\t\ttemp = curr.data\r\n\t\tcurr.data = pivot\r\n\t\tend.data = temp\r\n\r\n\t\treturn pivot_prev\r\n\r\n\tdef sort(self, start, end):\r\n\t\tif(start == None or start == end or start == end.next):\r\n\t\t\treturn\r\n\r\n\t\tpivot_prev = self.paritionLast(start, end)\r\n\t\tself.sort(start, pivot_prev)\r\n\r\n\t\tif(pivot_prev != None and pivot_prev == start):\r\n\t\t\tself.sort(pivot_prev.next, end)\r\n\r\n\t\telif (pivot_prev != None and pivot_prev.next != None):\r\n\t\t\tself.sort(pivot_prev.next.next, end)\r\n\r\nif __name__ == &quot;__main__&quot;:\r\n\tll = QuickSortLinkedList()\r\n\tll.addNode(30)\r\n\tll.addNode(3)\r\n\tll.addNode(4)\r\n\tll.addNode(20)\r\n\tll.addNode(5)\r\n\r\n\tn = ll.head\r\n\twhile (n.next != None):\r\n\t\tn = n.next\r\n\r\n\tprint(&quot;Linked List before sorting&quot;)\r\n\tll.printList(ll.head)\r\n\r\n\tll.sort(ll.head, n)\r\n\r\n\tprint(&quot;&#92;nLinked List after sorting&quot;);\r\n\tll.printList(ll.head)\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_5268 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_5268 a\"),jQuery(\"#tab-content_5268\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p>Now, we have a good understanding of the QuickSort algorithm. Let\u2019s learn how to apply QuickSort on a singly linked list.<\/p>\n<h3>Algorithm to apply quicksort on singly linked list<\/h3>\n<p><strong>Quick Sort in Singly Linked List:<\/strong><\/p>\n<p>Initialize a pointer named <strong>tail<\/strong> of type node with <strong>head<\/strong>, and move it to the <strong>last node<\/strong> of the linked list. To get the last node of the linked list, we will traverse through the list until we have found a node whose <strong>next<\/strong> is NULL.<\/p>\n<p><strong>Recursive Function:<\/strong> Node <em>quickSortHelper( Node <\/em>head, Node *tail), it will return the new head after sorting the list.<\/p>\n<p><strong>Base Case:<\/strong> When the head and tail point to the same node or head is NULL, we will just return the head.<\/p>\n<p><strong>Algorithm Steps to apply quicksort on singly linked list:<\/strong><\/p>\n<ol>\n<li>We can pick any element as a <strong>pivot<\/strong>, but we will pick the <strong>last element as a pivot<\/strong>.<\/li>\n<li>Make a partition function that will partition the list around the picked <strong>pivot<\/strong>.<\/li>\n<li>We have already seen that we need to arrange the elements such that all elements smaller than the pivot element will be before the pivot, and all elements greater than the pivot element will be after the pivot; that\u2019s why we will create a partition function.<\/li>\n<li>In this partition function, we will traverse through the current list, and:<\/li>\n<ul>\n<li>If a <strong>node\u2019s data<\/strong> is greater than the <strong>pivot\u2019s data<\/strong>, we move it after <strong>tail<\/strong>.<\/li>\n<li>Else if the <strong>node\u2019s data<\/strong> has a smaller value than the <strong>tail\u2019s data<\/strong>, we keep it at its current position, i.e, no change in position.<\/li>\n<\/ul>\n<li>In this <strong>partition function<\/strong>, after partition of the nodes around the <strong>pivot<\/strong> node, generates two new linked lists. One linked list contains all nodes that are smaller in value than the pivot node and another linked list contains all nodes greater than the pivot node.<\/li>\n<li>The <strong>partition function<\/strong> will update 5 pointers that point to the <strong>pivot<\/strong>, <strong>head<\/strong> and <strong>tail<\/strong> pointer of linked list containing all nodes smaller than pivot and <strong>head<\/strong> and <strong>tail<\/strong> pointer of a linked list containing all nodes greater than the pivot.<\/li>\n<li>Now we will call <strong>quickSortRecur<\/strong> on nodes that are smaller than the pivot node, after that, we will again call <strong>quickSortRecur<\/strong> on nodes that are greater than the pivot node.<\/li>\n<li>This process continues till we hit the base case and when we hit the base case we start returning from the recursive calls.<\/li>\n<li>When we return back after hitting the base case we will join these two linked lists in such order that our whole linked list remains sorted.<\/li>\n<\/ol>\n<h3>Dry Run to apply quick sort on linked list<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_6-6.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_7-6.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_8-7.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_9-3.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_10_11.png\" alt=\"\" \/><\/p>\n<h3>Code Implementation for quick sort on linked list<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5269 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_5269 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_5269 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5269 .wpsm_nav-tabs > li.active > a, #tab_container_5269 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5269 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_5269 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_5269 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5269 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5269 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5269 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5269 .wpsm_nav-tabs > li > a:hover , #tab_container_5269 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_5269 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_5269 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_5269 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_5269 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_5269 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_5269 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_5269 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5269 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_5269 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5269 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_5269 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_5269\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5269\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5269_1\" aria-controls=\"tabs_desc_5269_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5269_2\" aria-controls=\"tabs_desc_5269_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5269_3\" aria-controls=\"tabs_desc_5269_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-laptop\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_5269\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_5269_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include <bits\/stdc++.h>\r\nusing namespace std;\r\n\r\n\/* Node structure of a singly linked list *\/\r\nclass Node {\r\npublic:\r\n    int data;\r\n    Node* next;\r\n};\r\n\r\n\/* Using this function we will insert a node at the beginning of the linked list *\/\r\nvoid push(Node** head_ref, int val){\r\n    Node* newNode = new Node;\r\n\r\n    newNode->data = val;\r\n\r\n    newNode->next = (*head_ref);\r\n\r\n    (*head_ref) = newNode;\r\n}\r\n\r\n\/* Using this function we will print the content of the linked list *\/\r\nvoid printList(Node* node){\r\n    while (node != NULL) {\r\n        cout<<node->data<<\" \";\r\n        node = node->next;\r\n    }\r\n    cout<<endl;\r\n}\r\n\r\n\/* This function returns the last node of the linked list *\/\r\nNode* getTail(Node* cur){\r\n    while (cur != NULL && cur->next != NULL)\r\n        cur = cur->next;\r\n    return cur;\r\n}\r\n\r\n\/* Using this function we will partition the linked list taking the last element of list as pivot *\/\r\nNode* partition( Node* head,  Node* end,\r\n                     Node** newHead,\r\n                     Node** newEnd)\r\n{\r\n     Node* pivot = end;\r\n     Node *prev = NULL, *cur = head, *tail = pivot;\r\n\r\n    \/\/ During the time of partition, both the head and end of the list\r\n    \/\/ might change and the changes will be updated in the newHead and\r\n    \/\/ newEnd variables\r\n    while (cur != pivot) {\r\n        if (cur->data < pivot->data) {\r\n            \/\/ The first node that will be having value less than the\r\n            \/\/ pivot node value will become the new head\r\n            if ((*newHead) == NULL)\r\n                (*newHead) = cur;\r\n\r\n            prev = cur;\r\n            cur = cur->next;\r\n        }\r\n        else \/\/ If the value of the cur node is greater than that of the pivot\r\n        {\r\n            \/\/ We will move the cur node to next of tail, and will update tail\r\n            if (prev)\r\n                prev->next = cur->next;\r\n             Node* tmp = cur->next;\r\n            cur->next = NULL;\r\n            tail->next = cur;\r\n            tail = cur;\r\n            cur = tmp;\r\n        }\r\n    }\r\n\r\n    \/\/ If the data of the pivot node is smallest in the\r\n    \/\/ current list, then we will make pivot as the head\r\n    if ((*newHead) == NULL)\r\n        (*newHead) = pivot;\r\n\r\n    \/\/ newEnd will be updated to the current last node\r\n    (*newEnd) = tail;\r\n\r\n    \/\/ Finally, we will return the pivot node\r\n    return pivot;\r\n}\r\n\r\n\/\/ Quick sort recursive function\r\n Node* quickSortRecur( Node* head,\r\n                             Node* end)\r\n{\r\n    \/\/ base condition\r\n    if (!head || head == end)\r\n        return head;\r\n\r\n    Node *newHead = NULL, *newEnd = NULL;\r\n\r\n    \/\/ We will call the partition function and it will partition the list\r\n    \/\/ and will also update newHead and newEnd\r\n    \/\/ it will return the pivot node\r\n     Node* pivot\r\n        = partition(head, end, &newHead, &newEnd);\r\n\r\n    \/\/ If our pivot is the smallest element in the current list\r\n    \/\/ then there is no need to recur for the left part of the list\r\n    if (newHead != pivot) {\r\n         Node* tmp = newHead;\r\n        while (tmp->next != pivot)\r\n            tmp = tmp->next;\r\n        tmp->next = NULL;\r\n\r\n        \/\/ Now we will recur for the list before the pivot\r\n        newHead = quickSortRecur(newHead, tmp);\r\n\r\n        tmp = getTail(newHead);\r\n        tmp->next = pivot;\r\n    }\r\n\r\n    \/\/ Now we will recur for the list after the pivot\r\n    pivot->next = quickSortRecur(pivot->next, newEnd);\r\n\r\n    return newHead;\r\n}\r\n\r\n\/\/ Ths is the function for quicksort. \r\nvoid quickSort(Node** headRef){\r\n    (*headRef)\r\n        = quickSortRecur(*headRef, getTail(*headRef));\r\n    return;\r\n} \r\n\r\n\r\nint main(){\r\n    Node* a = NULL;\r\n    push(&a, 8);\r\n    push(&a, 9);\r\n    push(&a, 5);\r\n    push(&a, 3);\r\n    push(&a, 2);\r\n    push(&a, 7);\r\n\r\n\r\n    cout << \"Linked List before sorting &#92;n\";\r\n    printList(a);\r\n\r\n    quickSort(&a);\r\n\r\n    cout << \"Linked List after sorting &#92;n\";\r\n    printList(a);\r\n\r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5269_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\npublic\r\nclass QuickSortLinkedList {\r\n    static class Node {\r\n        int data;\r\n        Node next;\r\n \r\n        Node(int d)\r\n        {\r\n            this.data = d;\r\n            this.next = null;\r\n        }\r\n    }\r\n \r\n    Node head;\r\n \r\n    void addNode(int data)\r\n    {\r\n        if (head == null) {\r\n            head = new Node(data);\r\n            return;\r\n        }\r\n \r\n        Node curr = head;\r\n        while (curr.next != null)\r\n            curr = curr.next;\r\n \r\n        Node newNode = new Node(data);\r\n        curr.next = newNode;\r\n    }\r\n \r\n    void printList(Node n)\r\n    {\r\n        while (n != null) {\r\n            System.out.print(n.data);\r\n            System.out.print(\" \");\r\n            n = n.next;\r\n        }\r\n    }\r\n \r\n    \/\/ takes first and last node,\r\n    \/\/ but do not break any links in\r\n    \/\/ the whole linked list\r\n    Node paritionLast(Node start, Node end)\r\n    {\r\n        if (start == end || start == null || end == null)\r\n            return start;\r\n \r\n        Node pivot_prev = start;\r\n        Node curr = start;\r\n        int pivot = end.data;\r\n \r\n        \/\/ iterate till one before the end,\r\n        \/\/ no need to iterate till the end\r\n        \/\/ because end is pivot\r\n        while (start != end) {\r\n            if (start.data < pivot) {\r\n                \/\/ keep tracks of last modified item\r\n                pivot_prev = curr;\r\n                int temp = curr.data;\r\n                curr.data = start.data;\r\n                start.data = temp;\r\n                curr = curr.next;\r\n            }\r\n            start = start.next;\r\n        }\r\n \r\n        \/\/ swap the position of curr i.e.\r\n        \/\/ next suitable index and pivot\r\n        int temp = curr.data;\r\n        curr.data = pivot;\r\n        end.data = temp;\r\n \r\n        \/\/ return one previous to current\r\n        \/\/ because current is now pointing to pivot\r\n        return pivot_prev;\r\n    }\r\n \r\n    void sort(Node start, Node end)\r\n    {\r\n        if(start == null || start == end|| start == end.next )\r\n            return;\r\n \r\n        \/\/ split list and partition recurse\r\n        Node pivot_prev = paritionLast(start, end);\r\n        sort(start, pivot_prev);\r\n \r\n        \/\/ if pivot is picked and moved to the start,\r\n        \/\/ that means start and pivot is same\r\n        \/\/ so pick from next of pivot\r\n        if (pivot_prev != null && pivot_prev == start)\r\n            sort(pivot_prev.next, end);\r\n \r\n        \/\/ if pivot is in between of the list,\r\n        \/\/ start from next of pivot,\r\n        \/\/ since we have pivot_prev, so we move two nodes\r\n        else if (pivot_prev != null\r\n                 && pivot_prev.next != null)\r\n            sort(pivot_prev.next.next, end);\r\n    }\r\n \r\n    \/\/ Driver Code\r\npublic\r\n    static void main(String[] args)\r\n    {\r\n        QuickSortLinkedList list\r\n            = new QuickSortLinkedList();\r\n        list.addNode(30);\r\n        list.addNode(3);\r\n        list.addNode(4);\r\n        list.addNode(20);\r\n        list.addNode(5);\r\n \r\n        Node n = list.head;\r\n        while (n.next != null)\r\n            n = n.next;\r\n \r\n        System.out.println(\"Linked List before sorting\");\r\n        list.printList(list.head);\r\n \r\n        list.sort(list.head, n);\r\n \r\n        System.out.println(\"&#92;nLinked List after sorting\");\r\n        list.printList(list.head);\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5269_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass Node:\r\n    def __init__(self, val):\r\n        self.data = val\r\n        self.next = None\r\n \r\nclass QuickSortLinkedList:\r\n \r\n    def __init__(self):\r\n        self.head=None\r\n \r\n    def addNode(self,data):\r\n        if (self.head == None):\r\n            self.head = Node(data)\r\n            return\r\n \r\n        curr = self.head\r\n        while (curr.next != None):\r\n            curr = curr.next\r\n \r\n        newNode = Node(data)\r\n        curr.next = newNode\r\n \r\n    def printList(self,n):\r\n        while (n != None):\r\n            print(n.data, end=&quot; &quot;)\r\n            n = n.next\r\n \r\n    ''' takes first and last node,but do not\r\n    break any links in    the whole linked list'''\r\n    def paritionLast(self,start, end):\r\n        if (start == end or start == None or end == None):\r\n            return start\r\n \r\n        pivot_prev = start\r\n        curr = start\r\n        pivot = end.data\r\n \r\n        '''iterate till one before the end,\r\n        no need to iterate till the end because end is pivot'''\r\n \r\n        while (start != end):\r\n            if (start.data &lt; pivot):\r\n               \r\n                # keep tracks of last modified item\r\n                pivot_prev = curr\r\n                temp = curr.data\r\n                curr.data = start.data\r\n                start.data = temp\r\n                curr = curr.next\r\n            start = start.next\r\n \r\n        '''swap the position of curr i.e.\r\n        next suitable index and pivot'''\r\n \r\n        temp = curr.data\r\n        curr.data = pivot\r\n        end.data = temp\r\n \r\n        ''' return one previous to current because\r\n        current is now pointing to pivot '''\r\n        return pivot_prev\r\n \r\n    def sort(self, start, end):\r\n        if(start == None or start == end or start == end.next):\r\n            return\r\n \r\n        # split list and partition recurse\r\n        pivot_prev = self.paritionLast(start, end)\r\n        self.sort(start, pivot_prev)\r\n \r\n        '''\r\n        if pivot is picked and moved to the start,\r\n        that means start and pivot is same\r\n        so pick from next of pivot\r\n        '''\r\n        if(pivot_prev != None and pivot_prev == start):\r\n            self.sort(pivot_prev.next, end)\r\n \r\n        # if pivot is in between of the list,start from next of pivot,\r\n        # since we have pivot_prev, so we move two nodes\r\n        elif (pivot_prev != None and pivot_prev.next != None):\r\n            self.sort(pivot_prev.next.next, end)\r\n \r\nif __name__ == &quot;__main__&quot;:\r\n    ll = QuickSortLinkedList()\r\n    ll.addNode(30)\r\n    ll.addNode(3)\r\n    ll.addNode(4)\r\n    ll.addNode(20)\r\n    ll.addNode(5)\r\n \r\n    n = ll.head\r\n    while (n.next != None):\r\n        n = n.next\r\n \r\n    print(&quot;&#92;nLinked List before sorting&quot;)\r\n    ll.printList(ll.head)\r\n \r\n    ll.sort(ll.head, n)\r\n \r\n    print(&quot;&#92;nLinked List after sorting&quot;);\r\n    ll.printList(ll.head)\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_5269 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_5269 a\"),jQuery(\"#tab-content_5269\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<h4>Output<\/h4>\n<p>Linked List before sorting<br \/>\n7 2 3 5 9 8<br \/>\nLinked List after sorting<br \/>\n2 3 5 7 8 9 <\/p>\n<p><strong>Time Complexity:<\/strong> Best case &#8211; O(NlogN), Worst case &#8211; O(N<sup>2<\/sup>).<\/p>\n<p>**Conclusion**<br \/>\nIn conclusion, we had discussed the quick sort using linked list in C++, Java and in Python programming language in detail with the dry run. While the algorithm follows the same divide-and-conquer approach as in the case of arrays, special considerations must be taken due to the nature of linked lists.<br \/>\nFAQs on quick sort in linked list<br \/>\nHere are some FAQs on Quick Sort in Linked List.<\/p>\n<p>**1. Does Quick Sort require additional memory for sorting a linked list?**<br \/>\nQuick Sort for linked lists typically requires a constant amount of additional memory for recursive function calls, making it more memory-efficient compared to other sorting algorithms like Merge Sort.<\/p>\n<p>**2. Can Quicksort be applied to linked lists?**<br \/>\nYes, Quick Sort can be applied to linked lists, and it is an efficient sorting technique for linked lists with a time complexity of O(n log n) on average.<\/p>\n<p>**3. How does Quicksort work on a linked list?**<br \/>\nIn a linked list, Quick Sort works by choosing a pivot element (usually the last element), partitioning the list into two sub-lists (less than pivot and greater than pivot), and recursively sorting the sub-lists until the entire list is sorted.<\/p>\n<p>**4. What is the time complexity of Quicksort on a linked list?**<br \/>\nThe time complexity of Quicksort on a linked list is O(n log n) on average. However, the worst-case time complexity can degrade to O(n^2) if the list is already sorted or nearly sorted.<\/p>\n<p>**5. How does Quicksort handle duplicate elements in a linked list?**<br \/>\nIn Quick Sort, duplicate elements are handled naturally during the partitioning process. All elements equal to the pivot are placed together in either the left or right sub-list.<\/p>\n<p>**6. Is Quicksort a stable sorting algorithm for linked lists?**<br \/>\nNo, Quick Sort is not a stable sorting algorithm for linked lists. Stable sorting algorithms preserve the relative order of equal elements, but Quick Sort does not guarantee this property.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>QuickSort is a popular sorting algorithm known for its efficiency in sorting arrays. However, when it comes to sorting a singly linked list, a few modifications are needed to adapt the algorithm. In this explanation, I will provide an introduction to quick sort in linked list. The QuickSort algorithm follows the divide-and-conquer approach. It works [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-5267","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>QuickSort on Singly Linked List<\/title>\n<meta name=\"description\" content=\"Learn the most efficient way to apply QuickSort on a Singly Linked List.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"QuickSort on Singly Linked List\" \/>\n<meta property=\"og:description\" content=\"Learn the most efficient way to apply QuickSort on a Singly Linked List.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-09-28T11:50:18+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-07-31T05:04:46+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg\" \/>\n<meta name=\"author\" content=\"PrepBytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PrepBytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"8 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\"},\"author\":{\"name\":\"PrepBytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\"},\"headline\":\"QuickSort on Singly Linked List\",\"datePublished\":\"2021-09-28T11:50:18+00:00\",\"dateModified\":\"2023-07-31T05:04:46+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\"},\"wordCount\":1298,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\",\"name\":\"QuickSort on Singly Linked List\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg\",\"datePublished\":\"2021-09-28T11:50:18+00:00\",\"dateModified\":\"2023-07-31T05:04:46+00:00\",\"description\":\"Learn the most efficient way to apply QuickSort on a Singly Linked List.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"QuickSort on Singly Linked List\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\",\"name\":\"PrepBytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"caption\":\"PrepBytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"QuickSort on Singly Linked List","description":"Learn the most efficient way to apply QuickSort on a Singly Linked List.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/","og_locale":"en_US","og_type":"article","og_title":"QuickSort on Singly Linked List","og_description":"Learn the most efficient way to apply QuickSort on a Singly Linked List.","og_url":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-28T11:50:18+00:00","article_modified_time":"2023-07-31T05:04:46+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg","type":"","width":"","height":""}],"author":"PrepBytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PrepBytes","Est. reading time":"8 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/"},"author":{"name":"PrepBytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e"},"headline":"QuickSort on Singly Linked List","datePublished":"2021-09-28T11:50:18+00:00","dateModified":"2023-07-31T05:04:46+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/"},"wordCount":1298,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/","url":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/","name":"QuickSort on Singly Linked List","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg","datePublished":"2021-09-28T11:50:18+00:00","dateModified":"2023-07-31T05:04:46+00:00","description":"Learn the most efficient way to apply QuickSort on a Singly Linked List.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1685081824646-QuickSort%20on%20Singly%20Linked%20List.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/quicksort-on-singly-linked-list\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"QuickSort on Singly Linked List"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e","name":"PrepBytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","caption":"PrepBytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=5267"}],"version-history":[{"count":9,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5267\/revisions"}],"predecessor-version":[{"id":17417,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5267\/revisions\/17417"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=5267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=5267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=5267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}