Last active
August 18, 2016 21:28
-
-
Save kurtzilla/83bb65fd0a46e3c1eda176a8397746c2 to your computer and use it in GitHub Desktop.
This file contains 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
/*********DISCLAIMER***********/ | |
/* there is more than one way to do a sort :) */ | |
function swap(arr, idx1, idx2) { | |
var temp = arr[idx1]; | |
arr[idx1] = arr[idx2]; | |
arr[idx2] = temp; | |
} | |
/* 1. Set the pivot value to be the value at the left index, and set a | |
varaible called partitionIndex equal to left. The partitionIndex will | |
help us keep track of where to perform our swaps so that we wind up with | |
values correctly placed on either side of the pivot. | |
2. For every index greater than left and less than right + 1, compare the | |
array value to the pivot value. | |
3. If the array value at the given index is less than the pivot value, | |
increment the partition index and swap the array value with the value at | |
the partition index. | |
4. At the end, swap the pivot value with the value at the partition index | |
(this ensures that the pivot ends up in between values less than it and | |
values greater than it). | |
5. Return the partition index. */ | |
function partition(arr, left, right) { | |
// 1 | |
var pivot = arr[left]; | |
var partitionIndex = left; | |
// 2 | |
for(var i=left+1;i<right+1;i++){ | |
// 3 | |
if(arr[i]<pivot){ | |
partitionIndex++; | |
swap(arr, i, partitionIndex); | |
} | |
} | |
// 4 | |
swap(arr, left, partitionIndex); | |
return partitionIndex; | |
} | |
function quickSort(arr, left=0, right=arr.length - 1) { | |
// init ^^^ | |
/* | |
1. If left is less than right, declare a variable called | |
partitionIndex which is equal to the result of a call to | |
partition, passing in arr, left, and right. | |
After the call to partition, perform a quicksort to the | |
two subarrays to the left and right of the partitionIndex. | |
2. Return arr. | |
*/ | |
if(left < right){ | |
var partitionIndex = partition(arr,left,right); | |
// what I thought | |
quickSort(arr,left,partitionIndex-1); | |
quickSort(arr,partitionIndex+1,right); | |
} | |
return arr; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment