Skip to content

Instantly share code, notes, and snippets.

@tin80122
Created March 13, 2021 01:51
Show Gist options
  • Save tin80122/acfb3f284c292b548a74e8ae630a97c1 to your computer and use it in GitHub Desktop.
Save tin80122/acfb3f284c292b548a74e8ae630a97c1 to your computer and use it in GitHub Desktop.
LeetCode 75 Quick Sort in place
//use space
var sortColors1 = function(nums) {
const pivot = nums[0];
let left = [];
let right = [];
let i = 0;
while(i < nums.length -1) {
nums[i] < pivot ? left.push(nums[i]) : right.push(nums[i])
i++;
}
return [...left,pivot,...right]
};
//native sort in js used quick sort when less data
var sortColorsNativeSort = (nums) => {
nums.sort((a,b) => a - b)
}
//implement quick sort in place
var swap = (list,a,b) => [list[a],list[b]] = [list[b],list[a]]
var getPointer = (nums,start,end) => {
const v = nums[start];
let pointer = start;
for(let i = start + 1; i < end ; i++){
if(nums[i] < v){
pointer++;
swap(nums,pointer,i);
}
}
swap(nums,start,pointer)
return pointer
}
const sortColors = (nums,start = 0,end = nums.length) => {
if(start >= end) return
const p = getPointer(nums,start,end)
sortColors(nums, start, p)
sortColors(nums, p+1, end)
}
const nums = [2,1,4,3,7,1,8]
sortColors(nums)
console.log(nums)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment