Skip to content

Instantly share code, notes, and snippets.

@ramsunvtech
Last active November 5, 2021 11:09
Show Gist options
  • Save ramsunvtech/404ca8b53e4f8f3f4da8 to your computer and use it in GitHub Desktop.
Save ramsunvtech/404ca8b53e4f8f3f4da8 to your computer and use it in GitHub Desktop.
Quick Sort in Javascript
function quickSort(arr, left, right){
var len = arr.length,
pivot,
partitionIndex;
if(left < right){
pivot = right;
partitionIndex = partition(arr, pivot, left, right);
//sort left and right
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
function partition(arr, pivot, left, right){
var pivotValue = arr[pivot],
partitionIndex = left;
for(var i = left; i < right; i++){
if(arr[i] < pivotValue){
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
swap(arr, right, partitionIndex);
return partitionIndex;
}
function swap(arr, i, j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
@ramsunvtech
Copy link
Author

ramsunvtech commented Oct 31, 2021

Sort Ascending in Quick Sort using JS 2021

function swap(inputArray, i, j){
   let temp = inputArray[i];
   inputArray[i] = inputArray[j];
   inputArray[j] = temp;
}

function partition(inputArray, pivot, left, right){
   let pivotValue = inputArray[pivot];
   let partitionIndex = left;

   for(let index = left; index < right; index++){
    if(inputArray[index] < pivotValue){
      swap(inputArray, index, partitionIndex);
      partitionIndex++;
    }
  }
  swap(inputArray, right, partitionIndex);
  return partitionIndex;
}

function quickSort(inputArray, left, right){
   let len = inputArray.length;
   let pivot = '';
   let partitionIndex = '';


  if(left < right){
    pivot = right;
    partitionIndex = partition(inputArray, pivot, left, right);
    
   //sort left and right
   quickSort(inputArray, left, partitionIndex - 1);
   quickSort(inputArray, partitionIndex + 1, right);
  }
  return inputArray;
}

@ramsunvtech
Copy link
Author

Sort Descending in Quick Sort using JS 2021

function swap(inputArray, i, j){
   let temp = inputArray[i];
   inputArray[i] = inputArray[j];
   inputArray[j] = temp;
}

function partition(inputArray, pivot, left, right){
   let pivotValue = inputArray[pivot];
   let partitionIndex = left;

   for(let index = left; index < right; index++){
    if(inputArray[index] > pivotValue){
      swap(inputArray, index, partitionIndex);
      partitionIndex++;
    }
  }
  swap(inputArray, right, partitionIndex);
  return partitionIndex;
}

function quickSort(inputArray, left, right){
   let len = inputArray.length;
   let pivot = '';
   let partitionIndex = '';


  if(left < right){
    pivot = right;
    partitionIndex = partition(inputArray, pivot, left, right);
    
   //sort left and right
   quickSort(inputArray, left, partitionIndex - 1);
   quickSort(inputArray, partitionIndex + 1, right);
  }
  return inputArray;
}

@ramsunvtech
Copy link
Author

Ascending in ES2021 spread operator.

function QuickSort(inputArray) {
  if(inputArray.length === 1) {
    return inputArray;
  }
  
  const pivotNumber = inputArray[inputArray.length - 1];
  const numbersLesserThanPivot = [];
  const numbersGreaterThanPivot = [];
  
  for(let inputArrayIndex = 0; inputArrayIndex < inputArray.length - 1; inputArrayIndex++) {
      if( inputArray[inputArrayIndex] < pivotNumber) {
        numbersLesserThanPivot.push(inputArray[inputArrayIndex])
      } else if( inputArray[inputArrayIndex] > pivotNumber) {
        numbersGreaterThanPivot.push(inputArray[inputArrayIndex])
      }
  }
  
  if (numbersLesserThanPivot.length > 0 && numbersGreaterThanPivot.length > 0) {
    return [...QuickSort(numbersLesserThanPivot), pivotNumber, ...QuickSort(numbersGreaterThanPivot)];
  } else if (numbersLesserThanPivot.length > 0) {
    return [...QuickSort(numbersLesserThanPivot), pivotNumber];
  }
  
  return [pivotNumber, ...QuickSort(numbersGreaterThanPivot)];
}

@ramsunvtech
Copy link
Author

Sort Descending with Duplicates

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const pivot = arr[arr.length-1];
  const lesserNumbersThanPivot = [];
  const equalToPivot = [];
  const greaterNumbersThanPivot = [];
  
  for(let arrayIndex = 0;arrayIndex<arr.length-1;arrayIndex++) {
    if (arr[arrayIndex] < pivot) {
      lesserNumbersThanPivot.push(arr[arrayIndex]);
    } if (arr[arrayIndex] === pivot) {
      equalToPivot.push(arr[arrayIndex]);
    } else if (arr[arrayIndex] > pivot) {
      greaterNumbersThanPivot.push(arr[arrayIndex]);
    }
  }
  
  if(lesserNumbersThanPivot.length > 0 && greaterNumbersThanPivot.length > 0) {
    return [...quickSort(greaterNumbersThanPivot), pivot, ...equalToPivot, ...quickSort(lesserNumbersThanPivot)];
  } else if(greaterNumbersThanPivot.length > 0) {
    return [...quickSort(greaterNumbersThanPivot), pivot, ...equalToPivot];
  } else {
    return [pivot, ...equalToPivot, ...quickSort(lesserNumbersThanPivot)];
  } 
}

@ramsunvtech
Copy link
Author

Sort Ascending with Duplicates.

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const pivot = arr[arr.length-1];
  const lesserNumbersThanPivot = [];
  const equalToPivot = [];
  const greaterNumbersThanPivot = [];
  
  for(let arrayIndex = 0;arrayIndex<arr.length-1;arrayIndex++) {
    if (arr[arrayIndex] < pivot) {
      lesserNumbersThanPivot.push(arr[arrayIndex]);
    } if (arr[arrayIndex] === pivot) {
      equalToPivot.push(arr[arrayIndex]);
    } else if (arr[arrayIndex] > pivot) {
      greaterNumbersThanPivot.push(arr[arrayIndex]);
    }
  }
  
  if(lesserNumbersThanPivot.length > 0 && greaterNumbersThanPivot.length > 0) {
    return [...quickSort(lesserNumbersThanPivot), pivot, ...equalToPivot, ...quickSort(greaterNumbersThanPivot)];
  } else if(lesserNumbersThanPivot.length > 0) {
    return [...quickSort(lesserNumbersThanPivot), pivot, ...equalToPivot];
  } else {
    return [pivot, ...equalToPivot, ...quickSort(greaterNumbersThanPivot)];
  } 
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment