{"id":16570,"date":"2020-07-12T19:13:15","date_gmt":"2020-07-12T13:43:15","guid":{"rendered":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/"},"modified":"2024-09-03T11:24:48","modified_gmt":"2024-09-03T05:54:48","slug":"quick-sort-algorithm","status":"publish","type":"post","link":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/","title":{"rendered":"Quick Sort Algorithm using C , C++, Java, and Python"},"content":{"rendered":"\n<ol class=\"wp-block-list\"><\/ol>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"what-is-quick-sort\"><strong>What is Quick Sort<\/strong><\/h2>\n\n\n\n<p>Quick sort algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm. We usually use Recursion in quicksort implementation. In each recursive call, a pivot is chosen, then the array is partitioned in such a way that all the elements less than pivot lie to the left and all the elements greater than pivot lie to the right.<\/p>\n\n\n\n<p>After every call, the chosen pivot occupies its correct position in the array which it is supposed to as in a sorted array. So with each step, our problem gets reduced by 2 which leads to quick sorting. Pivot can be an element. Example: last element of the current array or the first element of current array or random pivot etc.<\/p>\n\n\n\n<h2 id=\"quick-sort-pseudocode\"><strong>Quick Sort Pseudocode<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We are given with an input array<\/li>\n\n\n\n<li>Choose pivot, here we are choosing the last element as our pivot<\/li>\n\n\n\n<li>Now partition the array as per pivot\n<ul class=\"wp-block-list\">\n<li>Keep a partitioned index say p and initialize it to -1<\/li>\n\n\n\n<li>Iterate through every element in the array except the pivot<\/li>\n\n\n\n<li>If an element is less than the pivot element then increment p and swap the elements at index p with the element at index i.<\/li>\n\n\n\n<li>Once all the elements are traversed, swap pivot with element present at p+1 as this will the same position as in the sorted array<\/li>\n\n\n\n<li>Now return the pivot index<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Once partitioned, now make 2 calls on quicksort\n<ul class=\"wp-block-list\">\n<li>One from beg to p-1<\/li>\n\n\n\n<li>Other from p+1 to n-1<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-algorithm\"><strong>Quick Sort Algorithm<\/strong><br><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>quickSort(arr, beg, end)\n  if (beg &lt; end)\n    pivotIndex = partition(arr,beg, end)\n    quickSort(arr, beg, pivotIndex)\n    quickSort(arr, pivotIndex + 1, end)\n\npartition(arr, beg, end)\n  set end as pivotIndex\n  pIndex = beg - 1\n  for i = beg to end-1\n  if arr&#91;i] &lt; pivot\n    swap arr&#91;i] and arr&#91;pIndex]\n    pIndex++\n  swap pivot and arr&#91;pIndex+1]\nreturn pIndex + 1\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-time-complexity\"><strong>Quick Sort Time Complexity<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Partition of elements take n time<\/li>\n\n\n\n<li>And in quicksort problem is divide by the factor 2<\/li>\n\n\n\n<li>Best Time Complexity : O(nlogn)<\/li>\n\n\n\n<li>Average Time Complexity : O(nlogn)<\/li>\n\n\n\n<li>Worst Time Complexity : O(n^2)<\/li>\n\n\n\n<li>Worst Case will happen when array is sorted<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-space-complexity\"><strong>Quick Sort Space Complexity<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>O(n) : basic approach<\/li>\n\n\n\n<li>O(logn) : modified approach<\/li>\n<\/ul>\n\n\n\n<p><strong><a href=\"https:\/\/www.mygreatlearning.com\/blog\/bubble-sort\/\" target=\"_blank\" rel=\"noreferrer noopener\" aria-label=\"Learn about Bubble sort  (opens in a new tab)\"><em>Learn about Bubble sort <\/em><\/a><\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-in-c\"><strong>Quick Sort in C<\/strong><br><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe title=\"Quick Sort | Quick Sort Program in C | sorting algorithms | Great Learning\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/uitnVmb7ZFc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;stdio.h&gt; \n\n\/\/ Function to swap the elements \nvoid swap_elements(int* first, int* second) \n{ \n\tint temp = *first; \n\t*first = *second; \n\t*second = temp; \n} \n\n\/\/ In partition function l represents low and h represents high\nint partition_function(int arr&#91;], int l, int h) \n{ \n\tint p = arr&#91;h]; \/\/ pivot is the last element\n\tint i = (l - 1); \/\/ Index of smaller element \n\n\tfor (int j = l; j &lt;= h- 1; j++) \n\t{ \n\t\t\/\/ If current element is smaller than the pivot \n\t\tif (arr&#91;j] &lt; p) \n\t\t{ \n\t\t\ti++; \n\t\t\tswap_elements(&amp;arr&#91;i], &amp;arr&#91;j]); \/\/ swapping the elements\n\t\t} \n\t} \n\tswap_elements(&amp;arr&#91;i + 1], &amp;arr&#91;h]); \n\treturn (i + 1);   \n} \n\nvoid quick_sort(int arr&#91;], int l, int h) \n{ \n\tif (l &lt; h) \n\t{ \n\t\tint p_index = partition_function(arr, l, h); \n\t\tquick_sort(arr, l, p_index - 1); \n\t\tquick_sort(arr, p_index + 1, h); \n\t} \n} \n\n\/\/Function to print the elements of the array \nvoid print_Array(int arr&#91;], int len) \n{ \n\tint i; \n\tfor (i=0; i &lt; len; i++) \n\t\tprintf(\"%d \", arr&#91;i]);  \n} \n\n\/\/ Main Function or driver function\nint main() \n{ \n\tint array&#91;] = {14, 17, 8, 90, 11, 2}; \/\/Static array\n\tint length = sizeof(array)\/sizeof(array&#91;0]); \/\/For finding the length of the array\n\tprintf(\"Before Sorting the array: \");\n\tprint_Array(array, length);\n\tprintf(\"\\n\");\n\tprintf(\"After Sorting the array: \");\n       \/\/Indexing starts from 0(zero) in array (that is why length-1)\n        quick_sort(array, 0, length-1); \n\tprint_Array(array, length); \n\treturn 0; \n} \n<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"output-of-the-program\">Output of the program:<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>Before Sorting the array: 14 17 8 90 11 2 \nAfter Sorting the array: 2 8 11 14 17 90 \n<\/code><\/pre>\n\n\n\n<h2 id=\"quicksort-in-java\"><strong>QuickSort in Java<\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>import java.util.*;\npublic class QuickSortDemo\n{\n    static void quickSort(int&#91;] a,int p,int r) \n\t{\n\t\tif(p&lt;r)\n\t\t   {int q=partition(a,p,r);\n\t\t\tquickSort(a,p,q-1);\n\t\t\tquickSort(a,q+1,r);\n\t\n\t\t   }\n\t\t \n\t}\n\t\n\tstatic int partition(int&#91;] a,int b,int r)  \/\/ partition method \n\t{\n\t\tint pivot=a&#91;r];\n\t\tint pindex=b-1;\n\t\tfor(int i=b;i&lt;r;i++)\n\t\t{\n\t\t\tif(a&#91;i]&lt;=pivot)\n\t\t\t{\n\t\t\t\tpindex++;\n\t\t\t\tint t=a&#91;i];\n\t\t\t\ta&#91;i]=a&#91;pindex];\n\t\t\t\ta&#91;pindex]=t;\n\t\t\t}\n\t\t}\n\t\tpindex++;\n\t\tint t=a&#91;pindex];\n\t\ta&#91;pindex]=a&#91;r];\n\t\ta&#91;r]=t;\n\t\treturn pindex;\n\t\t\n\t}\n\t\n\tstatic void display(int&#91;] a)  \/\/ method to display the array\n\t{\n\t\tfor(int i=0;i&lt;a.length;i++)\n\t\t\tSystem.out.println(a&#91;i]+\" \");\n\t}\n\t\t\n\t\t\n    \n\tpublic static void main(String&#91;] args) \/\/ main method \n\t{\n\t\tScanner in=new Scanner(System.in);\n\t\tSystem.out.println(\u201center size of array\u201d);\n                int n=in.nextInt();\n\t\tint&#91;] a =new int&#91;n];\n\t\t\n                System.out.println(\u201center the elements of array\u201d);\n\t\tfor(int i=0;i&lt;a.length;i++)\n\t\t   a&#91;i]=in.nextInt();\n                quickSort(a,0,n-1);\n                System.out.println(\u201cArray after sorting the elements: \u201d);\n                display(a);\n\t}\n}\n\n<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"output-of-the-program\">Output of the program:<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>Output of the program:\nenter size of array\n5\nenter the elements of array\n12\n43\n21\n69\n56\nArray after sorting the elements:\n12\n21\n43\n56\n69\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-in-c\"><strong>Quick Sort in C++ <\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt; \nusing namespace std;  \n\nvoid swap(int* ele1, int* ele2)  \/\/ swapping the elements\n{  \n    int t = *ele1;  \n    *ele1 = *ele2;  \n    *ele2 = t;  \n}  \n  \n\nint partition (int a&#91;], int beg, int end)   \/\/ partitioning the elements\n{  \n    int pivot = a&#91;end]; \n    int i = (beg - 1); \n  \n    for (int j = beg; j &lt;= end - 1; j++)  \n    {  \n      \n        if (a&#91;j] &lt; pivot)  \n        {  \n            i++; \n            swap(&amp;a&#91;i], &amp;a&#91;j]);  \n        }  \n    }  \n    swap(&amp;a&#91;i + 1], &amp;a&#91;end]);  \n    return (i + 1);  \n}  \n  \n\nvoid quickSort(int a&#91;], int beg, int end)  \/\/ sorting the elements based on partitioning index\n{  \n    if (beg &lt; end)  \n    {  \n        \n        int pIndex = partition(a, beg, end);  \n  \n        quickSort(a, beg, pIndex - 1);  \n        quickSort(a, pIndex + 1, end);  \n    }  \n}  \n  \nvoid display(int a&#91;], int n)   \/\/ displaying the elements of the array\n{  \n  \n    for (int i = 0; i &lt; n; i++)  \n        cout &lt;&lt; a&#91;i] &lt;&lt; \" \";  \n    cout &lt;&lt; endl;  \n}  \n  \nint main()  \n{  \n    int a&#91;] = {10, 7, 8, 9, 1, 5};  \n    int n = sizeof(a) \/ sizeof(a&#91;0]);\n    cout &lt;&lt; \"Elements of array before sorting: \\n\";  \n    display(a, n);\n    quickSort(a, 0, n - 1);  \n    cout &lt;&lt; \"Elements of array after sorting: \\n\";  \n    display(a, n);  \n    return 0;  \n}  \n  \n\n\n<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"output-of-the-program\">Output of the program:<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>Elements of array before sorting:\n10 7 8 9 1 5 \nElements of array after sorting:\n1 5 7 8 9 10 <\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-in-python\"><strong>Quick Sort in Python<\/strong><br><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>def partition(array,l,h): \n    i = ( l-1 )          \n    p = array&#91;h]     \n  \n    for j in range(l, h): \n  \n        \n        if   array&#91;j] &lt; p: \n    \n            i = i+1 \n            array&#91;i],array&#91;j] = array&#91;j],array&#91;i] \n  \n    array&#91;i+1],array&#91;h] = array&#91;h],array&#91;i+1] \n    return ( i+1 ) \n  \n \ndef quickSort(a,l,h): \n    if l &lt; h: \n   \n        pin = partition(a,l,h)        \n        quickSort(a, l, pin-1) \n        quickSort(a, pin+1, h) \n  \n \narr = &#91;100, 76, 80, 9, 111, 50] \nn = len(arr)-1 \nquickSort(arr,0,n) \nprint (\"Elements of array after applying sorting:\") \nfor i in range(n): \n    print (\"%d\" %arr&#91;i]), \n\n\n\n\n<\/code><\/pre>\n\n\n\n<p>Output of the program:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Elements of array after applying sorting: 9 50 76 80 100 111<\/code><\/pre>\n\n\n\n<p> <strong><a rel=\"noreferrer noopener\" href=\"https:\/\/www.mygreatlearning.com\/blog\/bubble-sort\/\" target=\"_blank\"><em>Learn about Bubble sort <\/em><\/a><\/strong> <\/p>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"quick-sort-example\"><strong>Quick Sort Example<\/strong><br><\/h2>\n\n\n\n<p><strong>Example1:<\/strong><\/p>\n\n\n\n<p>Rearrange the array elements so that positive and negative numbers are placed alternatively. The relative ordering of elements do not matter<\/p>\n\n\n\n<p>Example:<\/p>\n\n\n\n<p>Input: [-1, 2, -3, 4, 5, 6, -7, 8, 9]<\/p>\n\n\n\n<p>Output: [4, -3, 5, -1, 6, -7, 2, 8, 9]<br><\/p>\n\n\n\n<p><strong>Optimal Approach<\/strong><br><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li> Follow quicksort approach by taking 0 as Pivot<\/li>\n\n\n\n<li> Partition the array around a pivot<\/li>\n\n\n\n<li> Now we will be having negative elements on the left-hand side and positive elements on the right-hand side.<\/li>\n\n\n\n<li>Take 2 index variable, neg=0 and pos=partition index+1<\/li>\n\n\n\n<li>Increment neg by 2 and pos by 1, and swap the elements<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Time Complexity: O(n)<\/li>\n\n\n\n<li>Space Complexity: O(1)<\/li>\n<\/ul>\n\n\n\n<p><strong>Code of the above example:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import java.util.*;\nclass Main{\n\tpublic static void main (String&#91;] args) {\n\t\tScanner in=new Scanner(System.in);\n\t\tint n=in.nextInt();\n\t\tint arr&#91;] = new int&#91;n];\n\t\tfor(int i=0;i&lt;n;i++)\n\t\t    arr&#91;i]=in.nextInt();\n\t\trearrange(arr,n);\n\t\tfor(int i=0;i&lt;n;i++)\n\t\t    System.out.println(arr&#91;i]);\n\t}\n\t\n    static void rearrange(int arr&#91;], int n) \n    { \n        int i = -1, tmp = 0; \n        for (int j = 0; j &lt; n; j++) \n        { \n            if (arr&#91;j] &lt; 0) \n            { \n                i++; \n\t\t\t\ttmp = arr&#91;i]; \n                arr&#91;i] = arr&#91;j]; \n                arr&#91;j] = tmp; \n            } \n        } \n\n        int pos = i+1, neg = 0; \n        while (pos &lt; n &amp;&amp; neg &lt; pos &amp;&amp; arr&#91;neg] &lt; 0) \n        { \n            tmp = arr&#91;neg]; \n            arr&#91;neg] = arr&#91;pos]; \n            arr&#91;pos] = tmp; \n            pos++; \n            neg += 2; \n        } \n    } \n\n}\n<\/code><\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<p>Move all 0's to the end of the array while maintaining the relative order of the non-zero elements.<br><\/p>\n\n\n\n<p>Example:<\/p>\n\n\n\n<p>Input: [0,1,0,3,12]<\/p>\n\n\n\n<p>Output: [1,3,12,0,0]<\/p>\n\n\n\n<p><strong>Optimal Approach:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Take a partitioned index p = -1 and traverse all the elements\u00a0<\/li>\n\n\n\n<li>If they are not equal to 0, then increment p and swap elements at i and p index.<\/li>\n<\/ol>\n\n\n\n<p><strong>Code of the above example:<\/strong><br><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import java.util.*;\n \nclass Main{\n\tpublic static void main (String&#91;] args) {\n\t\tScanner in=new Scanner(System.in);\n\t\tint n=in.nextInt();\n\t\tint arr&#91;] = new int&#91;n];\n\t\tfor(int i=0;i&lt;n;i++)\n\t\t    arr&#91;i]=in.nextInt();\n\t\trearrange(arr,n);\n\t\tfor(int i=0;i&lt;n;i++)\n\t\t    System.out.println(arr&#91;i]);\n\t}\n\t\n    static void rearrange(int arr&#91;], int n) \n    { \n         if(arr==null || n==0)\n                return;\n        int p=-1;       \n        for(int i=0;i&lt;n;i++){\n            if(arr&#91;i]!=0)\n            {\n                p++;\n                int t=arr&#91;i];\n                arr&#91;i]=arr&#91;p];\n                arr&#91;p]=t;\n            }\n        }\n        \n    } \n \n}\n<\/code><\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<p>Find the kth largest element in the given array.&nbsp;<\/p>\n\n\n\n<p>Example 1:<\/p>\n\n\n\n<p>Input: [3,2,1,5,6,4] and k = 2<\/p>\n\n\n\n<p>Output: 5<\/p>\n\n\n\n<p>Example 2:<\/p>\n\n\n\n<p>Input: [3,2,3,1,2,4,5,5,6] and k = 4<\/p>\n\n\n\n<p>Output: 4<\/p>\n\n\n\n<p>Note:<\/p>\n\n\n\n<p>You may assume k is always valid, 1 \u2264 k \u2264 array's length.<br><\/p>\n\n\n\n<p><strong>Optimal Approach<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Quicksort can be used to solve this problem<\/li>\n\n\n\n<li>so if you want 4th largest in 9 size array then in sorted order it should be at 9-4+1 (i.e, n-k+1)<\/li>\n\n\n\n<li>so start setting pivot one by one ...as soon as pivot comes at n-k+1 position return<\/li>\n\n\n\n<li>TC: linear in avg case with O(1) space<\/li>\n<\/ul>\n\n\n\n<p><strong>Code of the above example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>public int findKthLargest(int&#91;] nums, int k) {\n        int desired=nums.length-k;\n        return quick(nums,desired,0,nums.length-1);\n        \n    }\n    \n    int quick(int&#91;] nums,int desired,int start,int end){\n       int p=partition(nums,start,end);\n       if(p==desired)\n            return nums&#91;p];\n        \n        \/\/depending on desired index we will move our quicksort\n       if(desired&lt;p)\n           return quick(nums,desired,start,p-1);\n        else\n          \/\/ if(p&lt;nums.length-1)\n               return quick(nums,desired,p+1,end); \n       \/\/ return -1;\n    }\n    \n    int partition(int&#91;] a,int start,int end)\n    {\n        int i=start;\n        int j=start;\n        int piv=end;\n        while(j&lt;end)\n        {\n            if(a&#91;j]&lt;=a&#91;piv])\n            {\n                int t=a&#91;i];\n                a&#91;i]=a&#91;j];\n                a&#91;j]=t;\n                i++;\n            }\n            j++;\n        }\n     \n      int t=a&#91;i];\n      a&#91;i]=a&#91;piv];\n      a&#91;piv]=t;\n      return i;\n        \n    }\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading toc\" id=\"difference-between-quick-sort-and-merge-sort\"><strong>Difference between Quick Sort and Merge Sort<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>In terms of algorithm and complexity<\/strong>\n<ul class=\"wp-block-list\">\n<li>In Quicksort, the partition of the array in the next iteration completely depends on the choice of the pivot element. We will have 2 arrays after placing the pivot to its correct position. So if we have a sorted array, the pivot will remain at the same position, leading to n^2 complexity, as no real partition will take place.<\/li>\n\n\n\n<li>In Mergesort, we take the mid index which is (beg index + end index)\/2. Our array will always break into two subsequent arrays with approximately equal length. This keeps the complexity to nlogn and is much time-efficient<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>In terms of space complexity<\/strong>\n<ul class=\"wp-block-list\">\n<li>If we are implementing our sort algorithm using recursion, then obviously our recursion stack will take n space.<\/li>\n\n\n\n<li>But in merge sort in every iteration we create two new temporary arrays. In one we copy all the left subarray and in other we copy all the right subarray. Since all the elements are copied, it takes another n space.<\/li>\n\n\n\n<li>In quicksort no such temporary array creation and copying takes place. Therefore no extra n space is needed<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>In terms of speed<\/strong>\n<ul class=\"wp-block-list\">\n<li>Quicksort is faster than merge sort because of the previous explanation.<\/li>\n\n\n\n<li>No temporary array, copying etc happens in quicksort, making it much faster in execution<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>In terms of in-place<\/strong>\n<ul class=\"wp-block-list\">\n<li>In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.<\/li>\n\n\n\n<li>Quicksort is in-place but merge sort is not as it needs extra n space for creating temporary arrays whose sixes adds up to n\u00a0\u00a0<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>In terms of stability<\/strong>\n<ul class=\"wp-block-list\">\n<li>Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.<\/li>\n\n\n\n<li>In quicksort, a lot of swapping takes place leading it to lose its stability whereas merge sort maintains the relative ordering and hence it is stable.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>QUICK SORT<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>MERGE SORT<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><\/td><td class=\"has-text-align-left\" data-align=\"left\"><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">Splitting of array depends on the value of pivot and other array elements<\/td><td class=\"has-text-align-left\" data-align=\"left\">Splitting of array generally done on half<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">Worst-case time complexity is O(n2)<\/td><td class=\"has-text-align-left\" data-align=\"left\">Worst-case time complexity is O(nlogn)<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">It takes less n space than merge sort<\/td><td class=\"has-text-align-left\" data-align=\"left\">It takes more n space than quick sort<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">It works faster than other sorting algorithms for small data set like Selection sort etc<\/td><td class=\"has-text-align-left\" data-align=\"left\">It has a consistent speed on any size of data<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">It is in-place<\/td><td class=\"has-text-align-left\" data-align=\"left\">It is out-place<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">Not stable<\/td><td class=\"has-text-align-left\" data-align=\"left\">Stable<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p> <strong><a rel=\"noreferrer noopener\" href=\"https:\/\/www.mygreatlearning.com\/blog\/bubble-sort\/\" target=\"_blank\"><em>Learn about Bubble sort <\/em><\/a><\/strong> <\/p>\n\n\n\n<p>This brings us to the end of this article where we learned about Quik sort and its implementation in C, C++, Java and python. Improve your programming skills by taking up this free course by Great Learning academy. Click the banner below to know more.<\/p>\n\n\n<figure class=\"wp-block-image size-large zoomable\" data-full=\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/June-29-banner-for-GL-data-structures-1.png\"><a href=\"https:\/\/www.mygreatlearning.com\/academy\/learn-for-free\/courses\/data-structures-and-algorithms-in-java\"><img decoding=\"async\" width=\"1000\" height=\"242\" src=\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/June-29-banner-for-GL-data-structures-1.png\" alt=\"quick sort\" class=\"wp-image-16657\" srcset=\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/June-29-banner-for-GL-data-structures-1.png 1000w, https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/June-29-banner-for-GL-data-structures-1-300x73.png 300w, https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/June-29-banner-for-GL-data-structures-1-768x186.png 768w, https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/June-29-banner-for-GL-data-structures-1-696x168.png 696w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><\/a><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>What is Quick Sort Quick sort algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm. We usually use Recursion in quicksort implementation. In each recursive call, a pivot is chosen, then the array is partitioned in such a way that all the elements less than pivot lie [&hellip;]<\/p>\n","protected":false},"author":41,"featured_media":16789,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_uag_custom_page_level_css":"","site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[25860],"tags":[36858],"content_type":[],"class_list":["post-16570","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-software","tag-sorting-algorithm"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v27.3 (Yoast SEO v27.3) - https:\/\/yoast.com\/product\/yoast-seo-premium-wordpress\/ -->\n<title>Quick Sort Algorithm using C , C++, Java, and Python<\/title>\n<meta name=\"description\" content=\"Quick Sort Algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm which is done recursively for sorting.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Quick Sort Algorithm using C , C++, Java, and Python\" \/>\n<meta property=\"og:description\" content=\"Quick Sort Algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm which is done recursively for sorting.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/\" \/>\n<meta property=\"og:site_name\" content=\"Great Learning Blog: Free Resources what Matters to shape your Career!\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/GreatLearningOfficial\/\" \/>\n<meta property=\"article:published_time\" content=\"2020-07-12T13:43:15+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-09-03T05:54:48+00:00\" \/>\n<meta property=\"og:image\" content=\"http:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1000\" \/>\n\t<meta property=\"og:image:height\" content=\"700\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Great Learning Editorial Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@https:\/\/twitter.com\/Great_Learning\" \/>\n<meta name=\"twitter:site\" content=\"@Great_Learning\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Great Learning Editorial Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/\"},\"author\":{\"name\":\"Great Learning Editorial Team\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#\\\/schema\\\/person\\\/6f993d1be4c584a335951e836f2656ad\"},\"headline\":\"Quick Sort Algorithm using C , C++, Java, and Python\",\"datePublished\":\"2020-07-12T13:43:15+00:00\",\"dateModified\":\"2024-09-03T05:54:48+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/\"},\"wordCount\":1065,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#organization\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/Blog-Info-graphics-1000X700-05.jpg\",\"keywords\":[\"sorting algorithm\"],\"articleSection\":[\"IT\\\/Software Development\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/\",\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/\",\"name\":\"Quick Sort Algorithm using C , C++, Java, and Python\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/Blog-Info-graphics-1000X700-05.jpg\",\"datePublished\":\"2020-07-12T13:43:15+00:00\",\"dateModified\":\"2024-09-03T05:54:48+00:00\",\"description\":\"Quick Sort Algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm which is done recursively for sorting.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/Blog-Info-graphics-1000X700-05.jpg\",\"contentUrl\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2020\\\/07\\\/Blog-Info-graphics-1000X700-05.jpg\",\"width\":1000,\"height\":700,\"caption\":\"QuickSort_GL\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/quick-sort-algorithm\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Blog\",\"item\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"IT\\\/Software Development\",\"item\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/software\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Quick Sort Algorithm using C , C++, Java, and Python\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/\",\"name\":\"Great Learning Blog\",\"description\":\"Learn, Upskill &amp; Career Development Guide and Resources\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#organization\"},\"alternateName\":\"Great Learning\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#organization\",\"name\":\"Great Learning\",\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/06\\\/GL-Logo.jpg\",\"contentUrl\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/06\\\/GL-Logo.jpg\",\"width\":900,\"height\":900,\"caption\":\"Great Learning\"},\"image\":{\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#\\\/schema\\\/logo\\\/image\\\/\"},\"sameAs\":[\"https:\\\/\\\/www.facebook.com\\\/GreatLearningOfficial\\\/\",\"https:\\\/\\\/x.com\\\/Great_Learning\",\"https:\\\/\\\/www.instagram.com\\\/greatlearningofficial\\\/\",\"https:\\\/\\\/www.linkedin.com\\\/school\\\/great-learning\\\/\",\"https:\\\/\\\/in.pinterest.com\\\/greatlearning12\\\/\",\"https:\\\/\\\/www.youtube.com\\\/user\\\/beaconelearning\\\/\"],\"description\":\"Great Learning is a leading global ed-tech company for professional training and higher education. It offers comprehensive, industry-relevant, hands-on learning programs across various business, technology, and interdisciplinary domains driving the digital economy. These programs are developed and offered in collaboration with the world's foremost academic institutions.\",\"email\":\"info@mygreatlearning.com\",\"legalName\":\"Great Learning Education Services Pvt. Ltd\",\"foundingDate\":\"2013-11-29\",\"numberOfEmployees\":{\"@type\":\"QuantitativeValue\",\"minValue\":\"1001\",\"maxValue\":\"5000\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/#\\\/schema\\\/person\\\/6f993d1be4c584a335951e836f2656ad\",\"name\":\"Great Learning Editorial Team\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/02\\\/unnamed.webp\",\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/02\\\/unnamed.webp\",\"contentUrl\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/wp-content\\\/uploads\\\/2022\\\/02\\\/unnamed.webp\",\"caption\":\"Great Learning Editorial Team\"},\"description\":\"The Great Learning Editorial Staff includes a dynamic team of subject matter experts, instructors, and education professionals who combine their deep industry knowledge with innovative teaching methods. Their mission is to provide learners with the skills and insights needed to excel in their careers, whether through upskilling, reskilling, or transitioning into new fields.\",\"sameAs\":[\"https:\\\/\\\/www.mygreatlearning.com\\\/\",\"https:\\\/\\\/in.linkedin.com\\\/school\\\/great-learning\\\/\",\"https:\\\/\\\/x.com\\\/https:\\\/\\\/twitter.com\\\/Great_Learning\",\"https:\\\/\\\/www.youtube.com\\\/channel\\\/UCObs0kLIrDjX2LLSybqNaEA\"],\"award\":[\"Best EdTech Company of the Year 2024\",\"Education Economictimes Outstanding Education\\\/Edtech Solution Provider of the Year 2024\",\"Leading E-learning Platform 2024\"],\"url\":\"https:\\\/\\\/www.mygreatlearning.com\\\/blog\\\/author\\\/greatlearning\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Quick Sort Algorithm using C , C++, Java, and Python","description":"Quick Sort Algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm which is done recursively for sorting.","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:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/","og_locale":"en_US","og_type":"article","og_title":"Quick Sort Algorithm using C , C++, Java, and Python","og_description":"Quick Sort Algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm which is done recursively for sorting.","og_url":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/","og_site_name":"Great Learning Blog: Free Resources what Matters to shape your Career!","article_publisher":"https:\/\/www.facebook.com\/GreatLearningOfficial\/","article_published_time":"2020-07-12T13:43:15+00:00","article_modified_time":"2024-09-03T05:54:48+00:00","og_image":[{"width":1000,"height":700,"url":"http:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg","type":"image\/jpeg"}],"author":"Great Learning Editorial Team","twitter_card":"summary_large_image","twitter_creator":"@https:\/\/twitter.com\/Great_Learning","twitter_site":"@Great_Learning","twitter_misc":{"Written by":"Great Learning Editorial Team","Est. reading time":"6 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#article","isPartOf":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/"},"author":{"name":"Great Learning Editorial Team","@id":"https:\/\/www.mygreatlearning.com\/blog\/#\/schema\/person\/6f993d1be4c584a335951e836f2656ad"},"headline":"Quick Sort Algorithm using C , C++, Java, and Python","datePublished":"2020-07-12T13:43:15+00:00","dateModified":"2024-09-03T05:54:48+00:00","mainEntityOfPage":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/"},"wordCount":1065,"commentCount":0,"publisher":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/#organization"},"image":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#primaryimage"},"thumbnailUrl":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg","keywords":["sorting algorithm"],"articleSection":["IT\/Software Development"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/","url":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/","name":"Quick Sort Algorithm using C , C++, Java, and Python","isPartOf":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#primaryimage"},"image":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#primaryimage"},"thumbnailUrl":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg","datePublished":"2020-07-12T13:43:15+00:00","dateModified":"2024-09-03T05:54:48+00:00","description":"Quick Sort Algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm which is done recursively for sorting.","breadcrumb":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#primaryimage","url":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg","contentUrl":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg","width":1000,"height":700,"caption":"QuickSort_GL"},{"@type":"BreadcrumbList","@id":"https:\/\/www.mygreatlearning.com\/blog\/quick-sort-algorithm\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog","item":"https:\/\/www.mygreatlearning.com\/blog\/"},{"@type":"ListItem","position":2,"name":"IT\/Software Development","item":"https:\/\/www.mygreatlearning.com\/blog\/software\/"},{"@type":"ListItem","position":3,"name":"Quick Sort Algorithm using C , C++, Java, and Python"}]},{"@type":"WebSite","@id":"https:\/\/www.mygreatlearning.com\/blog\/#website","url":"https:\/\/www.mygreatlearning.com\/blog\/","name":"Great Learning Blog","description":"Learn, Upskill &amp; Career Development Guide and Resources","publisher":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/#organization"},"alternateName":"Great Learning","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.mygreatlearning.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.mygreatlearning.com\/blog\/#organization","name":"Great Learning","url":"https:\/\/www.mygreatlearning.com\/blog\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.mygreatlearning.com\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2022\/06\/GL-Logo.jpg","contentUrl":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2022\/06\/GL-Logo.jpg","width":900,"height":900,"caption":"Great Learning"},"image":{"@id":"https:\/\/www.mygreatlearning.com\/blog\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/GreatLearningOfficial\/","https:\/\/x.com\/Great_Learning","https:\/\/www.instagram.com\/greatlearningofficial\/","https:\/\/www.linkedin.com\/school\/great-learning\/","https:\/\/in.pinterest.com\/greatlearning12\/","https:\/\/www.youtube.com\/user\/beaconelearning\/"],"description":"Great Learning is a leading global ed-tech company for professional training and higher education. It offers comprehensive, industry-relevant, hands-on learning programs across various business, technology, and interdisciplinary domains driving the digital economy. These programs are developed and offered in collaboration with the world's foremost academic institutions.","email":"info@mygreatlearning.com","legalName":"Great Learning Education Services Pvt. Ltd","foundingDate":"2013-11-29","numberOfEmployees":{"@type":"QuantitativeValue","minValue":"1001","maxValue":"5000"}},{"@type":"Person","@id":"https:\/\/www.mygreatlearning.com\/blog\/#\/schema\/person\/6f993d1be4c584a335951e836f2656ad","name":"Great Learning Editorial Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2022\/02\/unnamed.webp","url":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2022\/02\/unnamed.webp","contentUrl":"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2022\/02\/unnamed.webp","caption":"Great Learning Editorial Team"},"description":"The Great Learning Editorial Staff includes a dynamic team of subject matter experts, instructors, and education professionals who combine their deep industry knowledge with innovative teaching methods. Their mission is to provide learners with the skills and insights needed to excel in their careers, whether through upskilling, reskilling, or transitioning into new fields.","sameAs":["https:\/\/www.mygreatlearning.com\/","https:\/\/in.linkedin.com\/school\/great-learning\/","https:\/\/x.com\/https:\/\/twitter.com\/Great_Learning","https:\/\/www.youtube.com\/channel\/UCObs0kLIrDjX2LLSybqNaEA"],"award":["Best EdTech Company of the Year 2024","Education Economictimes Outstanding Education\/Edtech Solution Provider of the Year 2024","Leading E-learning Platform 2024"],"url":"https:\/\/www.mygreatlearning.com\/blog\/author\/greatlearning\/"}]}},"uagb_featured_image_src":{"full":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",1000,700,false],"thumbnail":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05-150x150.jpg",150,150,true],"medium":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05-300x210.jpg",300,210,true],"medium_large":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05-768x538.jpg",768,538,true],"large":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",1000,700,false],"1536x1536":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",1000,700,false],"2048x2048":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",1000,700,false],"web-stories-poster-portrait":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",640,448,false],"web-stories-publisher-logo":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",96,67,false],"web-stories-thumbnail":["https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2020\/07\/Blog-Info-graphics-1000X700-05.jpg",150,105,false]},"uagb_author_info":{"display_name":"Great Learning Editorial Team","author_link":"https:\/\/www.mygreatlearning.com\/blog\/author\/greatlearning\/"},"uagb_comment_info":0,"uagb_excerpt":"What is Quick Sort Quick sort algorithm is one of the most widely used sorting algorithms. It follows a divide and conquer paradigm. We usually use Recursion in quicksort implementation. In each recursive call, a pivot is chosen, then the array is partitioned in such a way that all the elements less than pivot lie&hellip;","_links":{"self":[{"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/posts\/16570","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/users\/41"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/comments?post=16570"}],"version-history":[{"count":22,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/posts\/16570\/revisions"}],"predecessor-version":[{"id":104927,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/posts\/16570\/revisions\/104927"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/media\/16789"}],"wp:attachment":[{"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/media?parent=16570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/categories?post=16570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/tags?post=16570"},{"taxonomy":"content_type","embeddable":true,"href":"https:\/\/www.mygreatlearning.com\/blog\/wp-json\/wp\/v2\/content_type?post=16570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}