Quicksort

by Anton Bagayev

JavaScript

function swap (array, left, right){
  let temp = array[left];
  array[left] = array[right];
  array[right] = temp;    
}

function quickSort (array, left, right) {
	if (left == undefined) {
		left = 0;
	}
	if (right == undefined) {
		right = array.length - 1;
	}
	let pivotIndex = partition(array, left, right);
	
	if (left < pivotIndex - 1) {
		quickSort(array, left, pivotIndex -1);
	}
	if (right > pivotIndex) {
		quickSort(array, pivotIndex, right);
	}
	
	return array;
}

function partition(array, left, right) {
	let pivotIndex = Math.floor((left + right) / 2);
	let pivot = array[pivotIndex];
	console.log("Pivot is: " + pivot);
	let leftIndex = left;
	let rightIndex = right;
	
	while (leftIndex <= rightIndex) {
		while(array[leftIndex] < pivot) {
			leftIndex++;
		}
		while(array[rightIndex] > pivot) {
			rightIndex--;
		}
		if (leftIndex <= rightIndex) {
			swap(array, leftIndex, rightIndex);
			leftIndex++;
			rightIndex--;
		}
	}
	
	return leftIndex; // should be same as pivotIndex

}

console.log(quickSort([5,12,10,3,8,2,25]));