{"id":111,"date":"2021-01-12T11:53:58","date_gmt":"2021-01-12T10:53:58","guid":{"rendered":"http:\/\/materiale.gabrielemottola.it\/?p=111"},"modified":"2021-01-12T11:54:08","modified_gmt":"2021-01-12T10:54:08","slug":"quick-sort","status":"publish","type":"post","link":"https:\/\/materiale.gabrielemottola.it\/index.php\/2021\/01\/12\/quick-sort\/","title":{"rendered":"Quick &#8211; sort"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\"> <code>\/* C implementation QuickSort *\/<\/code>\n <code>#include&lt;stdio.h> <\/code>\n \u00a0\n <code>\/\/ A utility function to swap two elements <\/code>\n <code>void<\/code> <code>swap(int* a, int* b) <\/code>\n <code>{ <\/code>\n <code>int<\/code> <code>t = *a; <\/code>\n <code>*a = *b; <\/code>\n <code>*b = t; <\/code>\n <code>} <\/code>\n \u00a0\n <code>\/* This function takes last element as pivot, places <\/code>\n <code>the pivot element at its correct position in sorted <\/code>\n <code>array, and places all smaller (smaller than pivot) <\/code>\n <code>to left of pivot and all greater elements to right <\/code>\n <code>of pivot *\/<\/code>\n <code>int<\/code> <code>partition (int<\/code> <code>arr[], int<\/code> <code>low, int<\/code> <code>high) <\/code>\n <code>{ <\/code>\n <code>int<\/code> <code>pivot = arr[high];\u00a0\u00a0\u00a0 \/\/ pivot <\/code>\n <code>int<\/code> <code>i = (low - 1);\u00a0 \/\/ Index of smaller element <\/code>\n \u00a0\n <code>for<\/code> <code>(int<\/code> <code>j = low; j &lt;= high- 1; j++) <\/code>\n <code>{ <\/code>\n <code>\/\/ If current element is smaller than or <\/code>\n <code>\/\/ equal to pivot <\/code>\n <code>if<\/code> <code>(arr[j] &lt;= pivot) <\/code>\n <code>{ <\/code>\n <code>i++;\u00a0\u00a0\u00a0 \/\/ increment index of smaller element <\/code>\n <code>swap(&amp;arr[i], &amp;arr[j]); <\/code>\n <code>} <\/code>\n <code>} <\/code>\n <code>swap(&amp;arr[i + 1], &amp;arr[high]); <\/code>\n <code>return<\/code> <code>(i + 1); <\/code>\n <code>} <\/code>\n \u00a0\n <code>\/* The main function that implements QuickSort <\/code>\n <code>arr[] --> Array to be sorted, <\/code>\n <code>low\u00a0 --> Starting index, <\/code>\n <code>high\u00a0 --> Ending index *\/<\/code>\n <code>void<\/code> <code>quickSort(int<\/code> <code>arr[], int<\/code> <code>low, int<\/code> <code>high) <\/code>\n <code>{ <\/code>\n <code>if<\/code> <code>(low &lt; high) <\/code>\n <code>{ <\/code>\n <code>\/* pi is partitioning index, arr[p] is now <\/code>\n <code>at right place *\/<\/code>\n <code>int<\/code> <code>pi = partition(arr, low, high); <\/code>\n \u00a0\n <code>\/\/ Separately sort elements before <\/code>\n <code>\/\/ partition and after partition <\/code>\n <code>quickSort(arr, low, pi - 1); <\/code>\n <code>quickSort(arr, pi + 1, high); <\/code>\n <code>} <\/code>\n <code>} <\/code>\n \u00a0\n <code>\/* Function to print an array *\/<\/code>\n <code>void<\/code> <code>printArray(int<\/code> <code>arr[], int<\/code> <code>size) <\/code>\n <code>{ <\/code>\n <code>int<\/code> <code>i; <\/code>\n <code>for<\/code> <code>(i=0; i &lt; size; i++) <\/code>\n <code>printf(\"%d \", arr[i]); <\/code>\n <code>printf(\"n\"); <\/code>\n <code>} <\/code>\n \u00a0\n <code>\/\/ Driver program to test above functions <\/code>\n <code>int<\/code> <code>main() <\/code>\n <code>{ <\/code>\n <code>int<\/code> <code>arr[] = {10, 7, 8, 9, 1, 5}; <\/code>\n <code>int<\/code> <code>n = sizeof(arr)\/sizeof(arr[0]); <\/code>\n <code>quickSort(arr, 0, n-1); <\/code>\n <code>printf(\"Sorted array: n\"); <\/code>\n <code>printArray(arr, n); <\/code>\n <code>return<\/code> <code>0; <\/code>\n <code>} <\/code> <\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[],"_links":{"self":[{"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/posts\/111"}],"collection":[{"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/comments?post=111"}],"version-history":[{"count":1,"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/posts\/111\/revisions"}],"predecessor-version":[{"id":114,"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/posts\/111\/revisions\/114"}],"wp:attachment":[{"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/media?parent=111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/categories?post=111"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/materiale.gabrielemottola.it\/index.php\/wp-json\/wp\/v2\/tags?post=111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}