{"id":1239,"date":"2023-05-21T07:11:02","date_gmt":"2023-05-21T07:11:02","guid":{"rendered":"https:\/\/itnotes.apjsoftwares.com\/?p=1239"},"modified":"2023-05-21T07:11:49","modified_gmt":"2023-05-21T07:11:49","slug":"how-does-quicksort-work","status":"publish","type":"post","link":"https:\/\/itnotes.apjsoftwares.in\/index.php\/2023\/05\/21\/how-does-quicksort-work\/","title":{"rendered":"How does QuickSort Work"},"content":{"rendered":"\n

Step 1) <\/strong>First, find the \u201cpivot\u201d<\/strong> element in the array.<\/p>\n\n\n\n

Step 2)<\/strong> Start the left pointer at the first element of the array.<\/p>\n\n\n\n

Step 3) <\/strong>Start the right pointer at the last element of the array.<\/p>\n\n\n\n

Step 4) <\/strong>Compare the element pointing with the left pointer, and if it is less than the pivot element, then move the left pointer to the right (add 1 to the left index). Continue this until the left side element is greater than or equal to the pivot element.<\/p>\n\n\n\n

Step 5)<\/strong> Compare the element pointing with the right pointer. If it is greater than the pivot element, move the right pointer to the left (subtract 1 to the right index). Continue this until the right-side element is less than or equal to the pivot element.<\/p>\n\n\n\n

Step 6)<\/strong> Check if the left pointer is less than or equal to a right pointer, then saw the elements in these pointers\u2019 locations.<\/p>\n\n\n\n

Step 7) <\/strong>Increment the left pointer and decrement the right pointer.<\/p>\n\n\n\n

Step 8)<\/strong> If the left pointer index is still less than the right pointer\u2019s index, repeat the process; else, return the left pointer\u2019s index.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

So, let us see these steps with an example. Let us consider an array of elements which we need to sort is [5,3,7,6,2,9].<\/p>\n\n\n\n

Here are the steps to perform Quick sort that is being shown with an example [5,3,7,6,2,9].<\/p>\n\n\n\n

STEP 1) <\/strong>Determine pivot as a middle element. So, 7 <\/strong>is the pivot element.<\/p>\n\n\n\n

STEP 2) <\/strong>Start left and right pointers as first and last elements of the array, respectively. The left pointer points to 5 at index 0, and the right pointer points to 9<\/strong> at index 5.<\/p>\n\n\n\n

STEP 3) <\/strong>Compare the left pointer element with the pivot element, since 5 < 6 shift left pointer to the right to index 1.<\/p>\n\n\n\n

STEP 4) <\/strong>Now, still 3 <6, so shift the left pointer to one more index to the right. Now 7 > 6 stops incrementing the left pointer, and now the left pointer is index 2.<\/p>\n\n\n\n

STEP 5) <\/strong>Now, compare the value at the right pointer with the pivot element. Since 9 > 6, move the right pointer to the left. Now, as 2 < 6, stop moving the right pointer.<\/p>\n\n\n\n

STEP 6) <\/strong>Swap both values present at left and right pointers with each other.<\/p>\n\n\n\n

STEP 7) <\/strong>Move both pointers one more step.<\/p>\n\n\n\n

STEP 8) <\/strong>Since 6 = 6, move pointers to one more step and stop as the left pointer crosses the right pointer and returns the left pointer\u2019s index.<\/p>\n\n\n\n

Here, based on the above approach, we need to write code for swapping elements and partitioning the array as mentioned in the above steps.<\/p>\n\n\n\n

Example:<\/strong><\/p>\n\n\n\n

var items = [5,3,7,6,2,9];\nfunction swap(items, leftIndex, rightIndex){\n    var temp = items[leftIndex];\n    items[leftIndex] = items[rightIndex];\n    items[rightIndex] = temp;\n}\nfunction: partition(items, left, right) {\n    var pivot   = items[Math.floor((right + left) \/ 2)], \/\/middle element\n        i       = left, \/\/left pointer\n        j       = right; \/\/right pointer\n    while (i <= j) {\n        while (items[i] < pivot) {\n            i++;\n        }\n        while (items[j] > pivot) {\n            j--;\n        }\n        if (i <= j) {\n            swap(items, i, j); \/\/sawpping two elements\n            i++;\n            j--;\n        }\n    }\n    return i;\n}\n\nfunction quickSort(items, left, right) {\n    var index;\n    if (items.length > 1) {\n        index = partition(items, left, right); \/\/index returned from partition\n        if (left < index - 1) { \/\/more elements on the left side of the pivot\n            quickSort(items, left index - 1);\n        }\n        if (index < right) { \/\/more elements on the right side of the pivot\n            quickSort(items, index, right);\n        }\n    }\n    return items;\n}\n\/\/ first call to quick sort\nvar sortedArray = quickSort(items, 0, items.length - 1);\nconsole.log(sortedArray); \/\/prints [2,3,5,6,7,9]<\/pre>\n","protected":false},"excerpt":{"rendered":"
Step 1) First, find the \u201cpivot\u201d element in the array. Step 2) Start the left pointer at the first…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[23],"tags":[],"_links":{"self":[{"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/posts\/1239"}],"collection":[{"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/comments?post=1239"}],"version-history":[{"count":1,"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/posts\/1239\/revisions"}],"predecessor-version":[{"id":1240,"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/posts\/1239\/revisions\/1240"}],"wp:attachment":[{"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/media?parent=1239"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/categories?post=1239"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itnotes.apjsoftwares.in\/index.php\/wp-json\/wp\/v2\/tags?post=1239"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}