{"id":2578,"date":"2024-01-03T07:46:07","date_gmt":"2024-01-03T02:16:07","guid":{"rendered":"https:\/\/pythonarray.com\/?p=2578"},"modified":"2024-01-03T17:15:25","modified_gmt":"2024-01-03T11:45:25","slug":"quick-sort-implementation-guide","status":"publish","type":"post","link":"https:\/\/pythonarray.com\/quick-sort-implementation-guide\/","title":{"rendered":"Quick Sort: A Tutorial and Implementation Guide"},"content":{"rendered":"<p><strong>Prerequisites<\/strong><\/p>\n<p>To learn about Quick Sort, you must know:<\/p>\n<ol>\n<li>Python 3<\/li>\n<li>Python data structures &#8211; Lists<\/li>\n<li>Recursion<\/li>\n<\/ol>\n<h2>What is Quick Sort?<\/h2>\n<p>We are in the fifth and final tutorial of the sorting series. The previous tutorial talks about Bubble Sort, Insertion Sort, Selection Sort, and Merge Sort. If you haven\u2019t read that, please do as we will be building off of those concepts. Like all sorting algorithms, we consider a list to be sorted only if it is in ascending order. Descending order is considered the worst unsorted case.<\/p>\n<p>Quick Sort is quite different and complicated from the sorting techniques we have seen so far. In this technique, we select the first element and call it the\u00a0<i>pivot<\/i>. The idea is to group elements such that elements to the left of the pivot are smaller than the pivot and the elements to the right of the pivot are larger than the pivot.<\/p>\n<p>This is done by maintaining two pointers\u00a0<i>left\u00a0<\/i>and\u00a0<i>right<\/i>. The\u00a0<i>left\u00a0<\/i>pointer points to the first element after the pivot. Let us refer to the element pointed by\u00a0<i>left\u00a0<\/i>as\u00a0<i>lelement.\u00a0<\/i>Similarly, the\u00a0<i>right\u00a0<\/i>pointer points to the farthest element on the right side of the list. Let us call this element as\u00a0<i>relement<\/i>. At each step, compare\u00a0<i>lelement\u00a0<\/i>with\u00a0<i>pivot\u00a0<\/i>and\u00a0<i>relement\u00a0<\/i>with\u00a0<i>pivot.<\/i><\/p>\n<ul>\n<li><a href=\"https:\/\/pythonarray.com\/insertion-sort-a-quick-tutorial-and-implementation-guide\/\">Insertion Sort: A quick tutorial and implementation guide<\/a><\/li>\n<li><a href=\"https:\/\/pythonarray.com\/bubble-sort-implementation-guide\/\">Bubble Sort: Quick Tutorial and Implementation Guide<\/a><\/li>\n<li><a href=\"https:\/\/pythonarray.com\/how-to-sort-python-dictionaries-by-key-or-value\/\">How to Sort Python Dictionaries by Key or Value<\/a><\/li>\n<\/ul>\n<p>Remeber\u00a0<i>lelement &lt; pivot\u00a0<\/i>and\u00a0<i>relement &gt; pivot<\/i>. If these conditions are not satisfied, the\u00a0<i>lelement\u00a0<\/i>and\u00a0<i>relement\u00a0<\/i>are swapped. Else,\u00a0<i>left\u00a0<\/i>pointer is incremented by 1 and the\u00a0<i>right\u00a0<\/i>pointer is decremented by 1.<\/p>\n<p>When\u00a0<i>left &gt;= right<\/i>, the\u00a0<i>pivot\u00a0<\/i>is swapped with either the\u00a0<i>lelement\u00a0<\/i>or\u00a0<i>relement.\u00a0<\/i>The\u00a0<i>pivot\u00a0<\/i>element will be in its correct position. Then continue the quick sort on the left half and the right half of the list.<\/p>\n<p>Let us see this using an example, alist = [5,9,6,2,7,0]<\/p>\n<table>\n<tbody>\n<tr>\n<td>Pivot<\/td>\n<td>Left<\/td>\n<td>Right<\/td>\n<td>Compare<\/td>\n<td>Action<\/td>\n<td>alist<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>9 [1]<\/td>\n<td>0 [5]<\/td>\n<td>9&gt;5<\/p>\n<p>0&lt;5<\/p>\n<p>&nbsp;<\/td>\n<td>Swap 0 and 9<\/p>\n<p>Increment\u00a0<i>left\u00a0<\/i>by 1<\/p>\n<p>Decrement\u00a0<i>right by 1<\/i><\/td>\n<td>[5,0,6,2,7,9]<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>6 [2]<\/td>\n<td>7[4]<\/td>\n<td>6&gt;5<\/p>\n<p>7&gt;5<\/td>\n<td>Decrement\u00a0<i>right\u00a0<\/i>by 1\u00a0pointer and leave\u00a0<i>left\u00a0<\/i>pointer as it is<\/td>\n<td>[5,0,6,2,7,9]<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>6 [2]<\/td>\n<td>2[3]<\/td>\n<td>6&gt;5<\/p>\n<p>2&lt;5<\/td>\n<td>Swap 2 and 6<\/p>\n<p>Increment\u00a0<i>left\u00a0<\/i>by 1<\/p>\n<p>Decrement\u00a0<i>right by 1<\/i><\/td>\n<td>[5,0,2,6,7,9]<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>6[3]<\/td>\n<td>2[2]<\/td>\n<td>Stop (since\u00a0<i>left&gt;right<\/i>)<\/td>\n<td>Swap 5 and 2<\/td>\n<td>[2,0,5,6,7,9]<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Similarly, perform Quick Sort on the left half &#8211; [2,0] and on the right half [6,7,9]. Repeat this process until the whole list is sorted. Even though we can see that the right half is already sorted, the algorithm has no way of knowing this.<\/p>\n<p>See\u00a0this\u00a0animation for better understanding.<\/p>\n<h3>How to implement Quick Sort?<\/h3>\n<p>Now that you have a fair understanding of what Quick Sort is, let us take a look at the algorithm and its code.<\/p>\n<h3>Algorithm<\/h3>\n<ol>\n<li>Choose a pivot<\/li>\n<li>Set a\u00a0<i>left\u00a0<\/i>pointer and\u00a0<i>right\u00a0<\/i>pointer<\/li>\n<li>Compare the\u00a0<i>left\u00a0<\/i>pointer element (<i>lelement)\u00a0<\/i>with the pivot and the\u00a0<i>right\u00a0<\/i>pointer element (<i>relement)\u00a0<\/i>with the\u00a0<i>pivot<\/i>.<\/li>\n<li>Check if\u00a0<i>lelement&lt;pivot\u00a0<\/i>and\u00a0<i>relement&gt;<\/i>pivot:\n<ol>\n<li>If yes, increment the\u00a0<i>left<\/i>\u00a0pointer and decrement the\u00a0<i>right\u00a0<\/i>pointer<\/li>\n<li>If not, swap the\u00a0<i>lelement\u00a0<\/i>and\u00a0<i>relement<\/i><\/li>\n<\/ol>\n<\/li>\n<li>When\u00a0<i>left &gt;= right,\u00a0<\/i>swap the\u00a0<i>pivot\u00a0<\/i>with either\u00a0<i>left\u00a0<\/i>or\u00a0<i>right\u00a0<\/i>pointer.<\/li>\n<li>Repeat steps 1 &#8211; 5 on the left half and the right half of the list till the entire list is sorted.<\/li>\n<\/ol>\n<p>Code<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">def quickSort(alist):\r\n\r\n  quickSortHelper(alist,0,len(alist)-1)\r\n\r\ndef quickSortHelper(alist,first,last):\r\n\r\n  if first&lt;last:\r\n      splitpoint = partition(alist,first,last)\r\n      quickSortHelper(alist,first,splitpoint-1)\r\n      quickSortHelper(alist,splitpoint+1,last)\r\n\r\ndef partition(alist,first,last):\r\n\r\n  pivotvalue = alist[first]\r\n  leftmark = first+1\r\n  rightmark = last\r\n  done = False\r\n\r\n  while not done:\r\n      while leftmark &lt;= rightmark and alist[leftmark] &lt;= pivotvalue:\r\n          leftmark = leftmark + 1\r\n\r\n      while alist[rightmark] &gt;= pivotvalue and rightmark &gt;= leftmark:\r\n          rightmark = rightmark -1\r\n\r\n      if rightmark &lt; leftmark:\r\n          done = True\r\n      else:\r\n          temp = alist[leftmark]\r\n          alist[leftmark] = alist[rightmark]\r\n          alist[rightmark] = temp\r\n\r\n  temp = alist[first]\r\n  alist[first] = alist[rightmark]\r\n  alist[rightmark] = temp\r\n\r\n  return rightmark\r\n\r\nalist = [54,26,93,17,77,31,44,55,20]\r\nquickSort(alist)\r\nprint(alist)<\/pre>\n<p>Courtesy of the code is\u00a0Interactive Python.<\/p>\n<h3>How to choose a pivot?<\/h3>\n<p>Choosing the\u00a0<i>pivot\u00a0<\/i>is very crucial as it determines the efficiency of this algorithm. If we get an already sorted list and we choose the first element as\u00a0<i>pivot\u00a0<\/i>then it will be a disaster! This is because there will be no element greater than the\u00a0<i>pivot\u00a0<\/i>and this drastically brings down the performance<i>.\u00a0<\/i>To avoid this, several methods are available to select the\u00a0<i>pivot\u00a0<\/i>value. One such method is the median method. In this, we choose the first element, the last element, and the middle element. After comparing these three elements, we choose the one with the median value. Let us see this with an example, alist = [5,6,9,0,3,1,2]<\/p>\n<p>First element is 5, last element is 2 and the middle element is 0. Comparing these values, it is clear that 2 is the median value and this selected as\u00a0<i>pivot<\/i>. Methods such as this ensure that we don\u2019t end up with the worst choice as our\u00a0<i>pivot.\u00a0<\/i>Remember the worst choice for\u00a0<i>pivot\u00a0<\/i>is the smallest or the largest value in the list.<\/p>\n<p><strong>Conclusion<\/strong><\/p>\n<p>Quick Sort works best with small and large number of elements. The worst case runtime complexity of Quick Sort is O(n2) similar to that of Insertion and Bubble Sort but it can be improved to O(nlog(n)) as discussed in the previous section. Unlike Merge Sort this doesn\u2019t have the disadvantage of using extra memory or space. That is why this is one of the most commonly used sorting techniques. That\u2019s all for this tutorial. Happy Pythoning!<\/p>\n<p><strong>You can Also Check<\/strong>:<\/p>\n<ul>\n<li><a href=\"https:\/\/pythonarray.com\/merge-sort-implementation-guide\/\">Merge Sort Implementation Guide<\/a><\/li>\n<li><a href=\"https:\/\/pythonarray.com\/selection-sort-implementation-guide\/\">Selection Sort Implementation Guide<\/a><\/li>\n<li><a href=\"https:\/\/pythonarray.com\/insertion-sort-a-quick-tutorial-and-implementation-guide\/\">Insertion Sort Implementation Guide<\/a><\/li>\n<li><a href=\"https:\/\/pythonarray.com\/bubble-sort-implementation-guide\/\">Bubble Sort Implementation Guide<\/a><\/li>\n<li><a href=\"https:\/\/paisaalgo.com\/astral-pivots-calculator\/\">ASTRAL Pivot Calculator<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Prerequisites To learn about Quick Sort, you must know: Python 3 Python data structures &#8211; Lists Recursion What is Quick Sort? We are in the fifth and final tutorial of the sorting series. The previous tutorial talks about Bubble Sort, Insertion Sort, Selection Sort, and Merge Sort. If you haven\u2019t read that, please do as&hellip;<\/p>\n","protected":false},"author":1,"featured_media":3949,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":""},"categories":[2],"tags":[],"jetpack_featured_media_url":"https:\/\/pythonarray.com\/wp-content\/uploads\/2021\/07\/Quick-Sort-A-Tutorial-and-Implementation-Guide.png","jetpack-related-posts":[{"id":2589,"url":"https:\/\/pythonarray.com\/insertion-sort-a-quick-tutorial-and-implementation-guide\/","url_meta":{"origin":2578,"position":0},"title":"Insertion Sort: A quick tutorial and implementation guide","date":"June 9, 2022","format":false,"excerpt":"Prerequisites To learn about Insertion Sort, you must know: Python 3 Python data structures - Lists What is Insertion Sort? We are in the second tutorial of the sorting series. The previous tutorial talks about Bubble Sort which is a very simple sorting algorithm. If you haven\u2019t read that, you\u2026","rel":"","context":"In &quot;Python&quot;","img":{"alt_text":"Insertion Sort A quick tutorial and implementation guide","src":"https:\/\/i2.wp.com\/pythonarray.com\/wp-content\/uploads\/2021\/07\/Insertion-Sort-A-quick-tutorial-and-implementation-guide.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2582,"url":"https:\/\/pythonarray.com\/merge-sort-implementation-guide\/","url_meta":{"origin":2578,"position":1},"title":"Merge Sort: A Quick Tutorial and Implementation Guide","date":"June 9, 2022","format":false,"excerpt":"Prerequisites To learn about Merge Sort, you must know: Python 3 Python data structures - Lists Recursion What is Merge Sort? We are in the fourth tutorial of the sorting series. The previous tutorials cover\u00a0Bubble Sort,\u00a0Insertion Sort, and\u00a0Selection Sort. If you haven\u2019t read these, please do as we will be\u2026","rel":"","context":"In &quot;Python&quot;","img":{"alt_text":"Merge Sort A Quick Tutorial and Implementation Guide","src":"https:\/\/i0.wp.com\/pythonarray.com\/wp-content\/uploads\/2021\/07\/Merge-Sort-A-Quick-Tutorial-and-Implementation-Guide.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2585,"url":"https:\/\/pythonarray.com\/selection-sort-implementation-guide\/","url_meta":{"origin":2578,"position":2},"title":"Selection Sort: A Quick Tutorial and Implementation Guide","date":"June 9, 2022","format":false,"excerpt":"Prerequisites To learn about Selection Sort, you must know: Python 3 Python data structures - Lists What is Selection Sort? We are in the third tutorial of the sorting series. The previous tutorial talks about Bubble Sort and Insertion Sort. If you haven\u2019t read that, please do as we will\u2026","rel":"","context":"In &quot;Python&quot;","img":{"alt_text":"Selection Sort A Quick Tutorial and Implementation Guide","src":"https:\/\/i2.wp.com\/pythonarray.com\/wp-content\/uploads\/2021\/07\/Selection-Sort-A-Quick-Tutorial-and-Implementation-Guide.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2591,"url":"https:\/\/pythonarray.com\/bubble-sort-implementation-guide\/","url_meta":{"origin":2578,"position":3},"title":"Bubble Sort: Quick Tutorial and Implementation Guide","date":"June 9, 2022","format":false,"excerpt":"Prerequisites T0 learn about Bubble Sort, you must know: Python 3 Python data structures - Lists What is Bubble Sort? In the last tutorial, we saw how to search for an element from unsorted and sorted lists. We discovered that search efficiency is greater when the lists are sorted. So\u2026","rel":"","context":"In &quot;Python&quot;","img":{"alt_text":"Bubble Sort Quick Tutorial and Implementation Guide","src":"https:\/\/i0.wp.com\/pythonarray.com\/wp-content\/uploads\/2021\/07\/Bubble-Sort-Quick-Tutorial-and-Implementation-Guide.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2387,"url":"https:\/\/pythonarray.com\/python-dictionary-quick-guide\/","url_meta":{"origin":2578,"position":4},"title":"Python Dictionary Quick Guide","date":"July 7, 2022","format":false,"excerpt":"As the title says, this is a Python dictionary quick guide. Please check out the\u00a0Dictionary Tutorial\u00a0for more articles about dictionaries. What is a Dictionary in Python? Python Programming - Creation, Initialization and Accessing The Elements In A Dictionary How to Sort Python Dictionaries by Key or Value # key\/value pairs\u2026","rel":"","context":"In &quot;Python&quot;","img":{"alt_text":"Python Dictionary Quick Guide","src":"https:\/\/i2.wp.com\/pythonarray.com\/wp-content\/uploads\/2021\/07\/Python-Dictionary-Quick-Guide-1.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2395,"url":"https:\/\/pythonarray.com\/how-to-use-sorting-in-python\/","url_meta":{"origin":2578,"position":5},"title":"How to use Sorting in Python","date":"July 7, 2022","format":false,"excerpt":"Sorting The easiest way to sort is with the sorted(list) function, which takes a list and returns a new list with those elements in sorted order. The original list is not changed. The sorted() function can be customized though optional arguments. The sorted() optional argument reverse=True, e.g. sorted(list, reverse=True), makes\u2026","rel":"","context":"In &quot;Python&quot;","img":{"alt_text":"How to use Sorting in Python","src":"https:\/\/i1.wp.com\/pythonarray.com\/wp-content\/uploads\/2021\/07\/How-to-use-Sorting-in-Python-1.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/posts\/2578"}],"collection":[{"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/comments?post=2578"}],"version-history":[{"count":3,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/posts\/2578\/revisions"}],"predecessor-version":[{"id":4368,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/posts\/2578\/revisions\/4368"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/media\/3949"}],"wp:attachment":[{"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/media?parent=2578"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/categories?post=2578"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pythonarray.com\/wp-json\/wp\/v2\/tags?post=2578"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}