{"id":4410,"date":"2020-12-16T14:31:51","date_gmt":"2020-12-16T09:01:51","guid":{"rendered":"https:\/\/copyassignment.com\/?p=4410"},"modified":"2022-06-18T16:56:17","modified_gmt":"2022-06-18T11:26:17","slug":"quick-sort-algorithm-in-python","status":"publish","type":"post","link":"https:\/\/copyassignment.com\/quick-sort-algorithm-in-python\/","title":{"rendered":"Quick Sort algorithm in data structures and algorithms using Python"},"content":{"rendered":"\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<p><strong>Quick Sort Algorithm<\/strong> is used to sort a given list or array into ascending or descending order depending on user preference. This <strong><a rel=\"noreferrer noopener\" href=\"https:\/\/copyassignment.com\/sorting-algorithms-and-searching-algorithms-in-python\/\" data-type=\"post\" data-id=\"3733\" target=\"_blank\">sorting algorithm<\/a><\/strong> is very efficient and easy to implement.<\/p>\n\n\n\n<p>Just like <a href=\"https:\/\/copyassignment.com\/merge-sort-algorithm-in-python\/\" data-type=\"post\" data-id=\"3788\" target=\"_blank\" rel=\"noreferrer noopener\">merge sort<\/a> this <strong>sorting algorithm<\/strong> is based on the principle of divide and conquer.<\/p>\n\n\n\n<p><strong>FOR EXAMPLE:<\/strong><\/p>\n\n\n\n<p><strong>INPUT Array: 38  27  43  3  9  82  10<\/strong><\/p>\n\n\n\n<p><strong>OUTPUT Array:  3  9  10  27  38  43  82<\/strong><\/p>\n\n\n\n<p>In the following article, we will learn what is<strong> <strong>Quick Sort Algorithm<\/strong><\/strong> and how to implement it using Python. We will first see how the <strong>sorting algorithm<\/strong> works and furthermore, we will study its algorithm, pseudocode, and lastly its actual implementation in Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Table of Contents:<\/strong><\/h2>\n\n\n\n<ol class=\"wp-block-list\" type=\"1\"><li>How does the quicksort algorithm work?<\/li><li>Algorithm of QuickSort<\/li><li>Python code for the quicksort algorithm<\/li><li>The time complexity of the quick sort algorithm.<\/li><li>The space complexity of quick sort algorithm.<\/li><li>Is quick sort an in-place sorting algorithm?<\/li><li>Does quicksort show a stable sorting algorithm behavior?<\/li><li>Is quick sort an adaptive sorting algorithm?<\/li><li>Properties<\/li><li>Applications of the quick sort<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Working of <strong>Quick Sort<\/strong><\/strong><\/h2>\n\n\n\n<p><strong><strong>Quick Sort<\/strong><\/strong> is based on the principle of<a rel=\"noreferrer noopener\" href=\"https:\/\/en.wikipedia.org\/wiki\/Divide_and_conquer\" data-type=\"URL\" data-id=\"https:\/\/en.wikipedia.org\/wiki\/Divide_and_conquer\" target=\"_blank\"> divide and conquer<\/a>. This algorithm divides the given list or Array into two parts and then solve each part. The partition of the list is done using a pivot element. A pivot element is an element of the list itself.<\/p>\n\n\n\n<p>There are many ways to decide on a pivot element:<\/p>\n\n\n\n<ol class=\"wp-block-list\" type=\"1\"><li>The very first element of the Array is chosen as the pivot.<\/li><li>Choosing the last element as pivot.<\/li><li>Picking middle element as pivot.<\/li><li>Randomly choosing any element as a pivot.<\/li><\/ol>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script>\n<ins class=\"adsbygoogle\" style=\"display:block; text-align:center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-9886351916045880\" data-ad-slot=\"2002566052\"><\/ins>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<p>The Array is divided such that all the elements to the right of the pivot element are greater than or equal to the pivot and the elements to the left are smaller than the pivot. We implement this <strong>sorting algorithm<\/strong> using a recursive call. Using recursion is far more simple and convenient than doing it by iteration.<\/p>\n\n\n\n<p>To understand further let\u2019s take an example<\/p>\n\n\n\n<p>Input: 7, 8, 5, 4, 6, 9 <\/p>\n\n\n\n<p>Step 1: Take 7 as the pivot element and divide the array into 2 subarrays.<\/p>\n\n\n\n\n\n<p>Step 2: Partition the subarrays further by taking 9 as pivot for the left subarray and 4 as pivot for the right subarray.<\/p>\n\n\n\n\n\n<p>Step 3: Once again the partition will take place using 6 as the pivot element.<\/p>\n\n\n\n\n\n<p>Step 4: After the sorting is done the final output will be:<\/p>\n\n\n\n<p>Output: 4, 5, 6, 7, 8, 9<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Algorithm of quick sort<\/strong><\/h2>\n\n\n\n<p>Step1: Choose a pivot element.<\/p>\n\n\n\n<p>Step2: Partition of the given list\/array about the pivot element.<\/p>\n\n\n\n<p>Step3: Passing these smaller arrays to the recursive calls.<\/p>\n\n\n\n<p>We will use two functions to implement this <strong>sorting algorithm<\/strong> namely partition() and quick_sort(). The quick_sort() will first call the partition() function on the given array and then call itself recursively on those divided parts of the array.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Python code<\/h2>\n\n\n\n<div style=\"height: 250px; position:relative; margin-bottom: 50px;\" class=\"wp-block-simple-code-block-ace\"><div style=\"position:absolute;top:-20px;right:0px;cursor:pointer\" class=\"copy-simple-code-block\"><span class=\"dashicon dashicons dashicons-admin-page\"><\/span><\/div><pre class=\"wp-block-simple-code-block-ace\" style=\"position:absolute;top:0;right:0;bottom:0;left:0\" data-mode=\"python\" data-theme=\"xcode\" data-fontsize=\"14\" data-lines=\"Infinity\" data-showlines=\"true\" data-copy=\"true\"># CODE BY COPYASSIGNMENT\n\n# The partition function takes last element as pivot, places \n# the pivot element at its correct position in sorted \n# array, and places all smaller (smaller than pivot) \n# to left of pivot and all greater elements to right \n# of pivot \ndef partition(arr,low,high): \n\ti = ( low-1 )\t\t # index of smaller element \n\tpivot = arr[high]\t # pivot \n\n\tfor j in range(low , high): \n\n\t\t# If current element is smaller than the pivot \n\t\tif arr[j] &lt; pivot: \n\t\t\n\t\t\t# increment index of smaller element \n\t\t\ti = i+1\n\t\t\tarr[i],arr[j] = arr[j],arr[i] \n\n\tarr[i+1],arr[high] = arr[high],arr[i+1] \n\treturn ( i+1 ) \n\n# Quick sort function\ndef quickSort(arr,low,high): \n\tif low &lt; high: \n\n\t\t# pi is partitioning index, arr[p] is now \n\t\t# at right place \n\t\tpi = partition(arr,low,high) \n\n\t\t# Separately sort elements before \n\t\t# partition and after partition \n\t\tquickSort(arr, low, pi-1) \n\t\tquickSort(arr, pi+1, high) \n\n# Driver code \narr = [10, 7, 8, 9, 1, 5] \nn = len(arr) \nquickSort(arr,0,n-1) \nprint (\"Sorted array is:\") \nfor i in range(n): \n\tprint (\"%d\" %arr[i])<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\">Output<\/h3>\n\n\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script>\n<ins class=\"adsbygoogle\" style=\"display:block; text-align:center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-9886351916045880\" data-ad-slot=\"2002566052\"><\/ins>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Time Complexity of <strong>Quick Sort Algorithm<\/strong><\/strong><\/h2>\n\n\n\n<p>Time Complexity: In programming Time Complexity is defined as the total time taken by a program to execute and completely run all its functions. When it comes to calculating Time Complexity we consider three main factors:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Worst case:<\/strong> The worst-case scenario occurs when one of the partitioned arrays is of size n-1. This only happens when the pivot element is the largest of the smallest element from the list. In this case, the time complexity is O(n^2).<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Best case:<\/strong> The best-case scenario occurs when the divided partitions are equally balanced or differ by just one. The first case occurs when the pivot element is right in the middle of the list, then each partition has (n-1)\/2 elements. The second case occurs when one partition of the subarray has an even number of elements and the other has an odd number of elements. In either case, there are utmost n\/2 elements in a partition. So the best case time complexity of the <strong>quick sort algorithm<\/strong> comes out to be O(n(logn)).<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Average case:<\/strong> The average time complexity of the <strong>quick sort algorithm<\/strong> is also O(n(logn)).&nbsp;&nbsp;&nbsp;<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Space complexity of Quick Sort Algorithm<\/strong><\/h2>\n\n\n\n<p>Space Complexity: In programming, space complexity is defined as the memory space occupied by the program to run and execute all its functions. Similar to the time complexity there are three cases to consider while evaluating the space complexity:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Worst case:<\/strong> The worst-case space complexity of the <strong>quicksort algorithm<\/strong> is O(n).<\/li><li><strong>Best case:<\/strong> The best-case space complexity of the quicksort algorithm is O(logn).<\/li><li><strong>Average case:<\/strong> Similarly to the best-case space complexity, the average case space complexity of the <strong>quicksort algorithm<\/strong> is also O(logn).<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>In-place sorting algorithm?<\/strong><\/h2>\n\n\n\n<p>Yes, <strong>quick sort <\/strong>is an in-place <strong>sorting algorithm<\/strong> as it does not require any other data structure like another array to perform its operations. Furthermore, it does not create any copies of its subarrays.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Stable sorting algorithm?<\/h2>\n\n\n\n<p>No, <strong>quick sort<\/strong> is an unstable <strong>sorting algorithm<\/strong>. A stable sorting algorithm is one in which the same elements appear at the same relative position in the sorted array as they appeared in the given initial unsorted array. <strong>Quick sort algorithm<\/strong> does not guarantee the maintenance of this relative order.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Adaptive sorting algorithm?<\/h2>\n\n\n\n<p>As the time complexity of the <strong>quick sort <\/strong>depends on the initial input sequence, so yes quick sort is an adaptive sorting algorithm just like insertion and bubble sort.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Properties<\/h2>\n\n\n\n<ol class=\"wp-block-list\" type=\"1\"><li>It uses the principle of divide and conquer.<\/li><li>It does not require any extra space to perform its operations.<\/li><li>Being tail-recursive there is room for optimization.<\/li><li>It is a chase friendly sorting algorithm.<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">Applications of quick sort<\/h2>\n\n\n\n<ol class=\"wp-block-list\" type=\"1\"><li>Whenever users don&#8217;t need a stable sorting algorithm they prefer quicksort.<\/li><li>The divide and conquer approach enables the use of parallelization.<\/li><li>In the problem of separating the k largest and smallest elements, we use this algorithm.<\/li><\/ol>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<p><strong>Thanks for reading my post.<\/strong><\/p>\n\n\n\n<p>Comment if you have any queries or if you found something wrong in the post or on our website.<\/p>\n\n\n\n<p><strong>Keep learning<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<p style=\"font-size:22px\"><strong>Also Read:<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/selection-sort-algorithm-in-data-structures-and-algorithms-using-python\/\">Selection Sort Algorithm In Data Structures and Algorithms using Python<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/introduction-to-searching-algorithms-linear-search-in-python\/\">Introduction to Searching Algorithms: Linear Search Algorithm<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/bubble-sort-algorithm\/\">Bubble Sort Algorithm In Data Structures &amp; Algorithms using Python<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/merge-sort-algorithm-in-python\/\">Merge Sort Algorithm in Python<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/binary-search-in-python-program\/\">Binary Search in python<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/linear-search-python\/\">Linear Search Python<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/copyassignment.com\/sorting-algorithms-and-searching-algorithms-in-python\/\">Sorting Algorithms and Searching Algorithms in Python<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Quick Sort Algorithm is used to sort a given list or array into ascending or descending order depending on user preference. This sorting algorithm is&#8230;<\/p>\n","protected":false},"author":62,"featured_media":12837,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"template-s1-c-post.php","format":"standard","meta":{"footnotes":""},"categories":[22,1059],"tags":[1682,1673,1091,1089,1088,1090],"class_list":["post-4410","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-allcategorites","category-data-structures-and-algorithms","tag-algorithms","tag-data-structures","tag-quick-sort-algorithm-in-data-structures-and-algorithms-using-python","tag-quick-sort-using-python","tag-quicksort-algorithm","tag-quicksort-in-python","wpcat-22-id","wpcat-1059-id"],"_links":{"self":[{"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/posts\/4410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/users\/62"}],"replies":[{"embeddable":true,"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/comments?post=4410"}],"version-history":[{"count":0,"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/posts\/4410\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/media\/12837"}],"wp:attachment":[{"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/media?parent=4410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/categories?post=4410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/copyassignment.com\/wp-json\/wp\/v2\/tags?post=4410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}