{"id":562,"date":"2013-08-08T21:15:32","date_gmt":"2013-08-09T04:15:32","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=562"},"modified":"2021-04-04T23:09:42","modified_gmt":"2021-04-05T06:09:42","slug":"sorting-quick-sort","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=562","title":{"rendered":"Sorting &#8211; Quick Sort"},"content":{"rendered":"<p>Time complexity:<\/p>\n<p>Worst-case: \\(O(n^2)\\)<\/p>\n<p>Best-case: \\(O(nlog(n))\\)<\/p>\n<p>Average-case: \\(O(nlog(n))\\)<\/p>\n<p>Pick a random element (pivot) and partition the array.<br \/>\n[all numbers that are less than the pivot] pivot [all numbers that are greater than the pivot]<\/p>\n<p>&nbsp;<\/p>\n<p><!--more--><\/p>\n<p><strong>Version 1.<\/strong><\/p>\n<pre class=\"brush:cpp;\">void QuickSort(int *list, int size)\r\n{\r\n    sortStep(list, size, 0, size-1);\r\n}\r\n\r\nint partition(int *list, int size, int left, int right, int pivotIndex)\r\n{\r\n    int pivot = list[pivotIndex];\r\n    int i, index = left;\r\n    swap(&amp;list[right], &amp;list[pivotIndex]);\r\n    for(i=left;i&lt;right;i++)\r\n    {\r\n        if(list[i] &lt; pivot)\r\n        {\r\n            swap(&amp;list[index++],&amp;list[i]);\r\n        }\r\n    }\r\n    swap(&amp;list[index], &amp;list[right]);\r\n    return index;\r\n}\r\n\r\nvoid sortStep(int *list, int size, int left, int right)\r\n{\r\n    if(left &lt; right)\r\n    {\r\n        \/\/pick up a pivot\r\n        srand(time(NULL));\r\n        int pivotIndex =  rand()%(right-left+1) + left; \/\/ make sure the range you set is correct\r\n        int index = partition(list, size, left, right, pivotIndex);\r\n        sortStep(list, size, left, index-1);\r\n        sortStep(list, size, index+1, right);\r\n    }\r\n}<\/pre>\n<p>Version 2.<\/p>\n<pre class=\"brush:cpp;\">void QuickSort(int *list, int size)\r\n{\r\n    sortStep(list, size, 0, size-1);\r\n}\r\n\r\nint partition(int *list, int size, int left, int right, int pivotIndex)\r\n{\r\n    \r\n    if(left &lt; right)\r\n    {\r\n        int i, j, leftIndex=left, rightIndex=right;\r\n        while(list[leftIndex] &lt; list[pivotIndex]) leftIndex++; while(list[rightIndex] &gt; list[pivotIndex])\r\n            rightIndex--;\r\n\r\n        while(leftIndex &lt; rightIndex)\r\n        {\r\n            swap(&amp;list[leftIndex], &amp;list[rightIndex]);\r\n            \r\n            leftIndex++;\r\n            rightIndex--;\r\n            \r\n            while(list[leftIndex] &lt; list[pivotIndex]) leftIndex++; while(list[rightIndex] &gt; list[pivotIndex])\r\n                rightIndex--;\r\n        }\r\n        swap(&amp;list[rightIndex], &amp;list[pivotIndex]);\r\n        return rightIndex;\r\n    }\r\n}\r\n\r\nvoid sortStep(int *list, int size, int left, int right)\r\n{\r\n    if(left &lt; right)\r\n    {\r\n        \/\/pick up a pivot\r\n        int pivotIndex = left; \/\/set first element as our pivot\r\n        int index = partition(list, size, left, right, pivotIndex);\r\n        sortStep(list, size, left, index-1);\r\n        sortStep(list, size, index+1, right);\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Time complexity: Worst-case: Best-case: Average-case: Pick a random element (pivot) and partition the array. [all numbers that are less than the pivot] pivot [all numbers that are greater than the pivot] &nbsp;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[24,21],"tags":[],"class_list":["post-562","post","type-post","status-publish","format-standard","hentry","category-chapter-11-sorting-and-searching","category-data-structures-and-algorithms"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/562","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=562"}],"version-history":[{"count":3,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/562\/revisions"}],"predecessor-version":[{"id":860,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/562\/revisions\/860"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=562"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=562"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=562"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}