Created
June 30, 2021 15:13
-
-
Save YaakovHatam/b463e53e8f9e0d3f59278be6d5a7d243 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function swap(items, leftIndex, rightIndex) { | |
| var temp = items[leftIndex]; | |
| items[leftIndex] = items[rightIndex]; | |
| items[rightIndex] = temp; | |
| } | |
| function partition(items, left, right) { | |
| var pivot = items[Math.floor((right + left) / 2)], //middle element | |
| i = left, //left pointer | |
| j = right; //right pointer | |
| while (i <= j) { | |
| while (items[i] < pivot) { | |
| i++; | |
| } | |
| while (items[j] > pivot) { | |
| j--; | |
| } | |
| if (i <= j) { | |
| swap(items, i, j); //sawpping two elements | |
| i++; | |
| j--; | |
| } | |
| } | |
| return i; | |
| } | |
| function quickSort(items, left, right) { | |
| var index; | |
| if (items.length > 1) { | |
| index = partition(items, left, right); //index returned from partition | |
| if (left < index - 1) { //more elements on the left side of the pivot | |
| quickSort(items, left, index - 1); | |
| } | |
| if (index < right) { //more elements on the right side of the pivot | |
| quickSort(items, index, right); | |
| } | |
| } | |
| return items; | |
| } | |
| // first call to quick sort | |
| var items = [5, 3, 7, 6, 2, 9]; | |
| var sortedArray = quickSort(items, 0, items.length - 1); | |
| console.log(sortedArray); //prints [2,3,5,6,7,9] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment