Programming Language:
Javascript (JS)
Solution:
// This function partitions given array and returns
// the index of the pivot.
//var partition=function(array, p, r){
// This code has been purposefully obfuscated,
// as you will implement it yourself in next challenge
// var e=array,t=p,n=r;var r=function(e,t,n){var r=e[t];e[t]=e[n];e[n]=r;};var i=t;for(var s=t;s<n;s++){if(e[s]<=e[n]){r(e,s,i);//i++;}}r(e,n,i);return i;
//};
// Swaps two items in an array, changing the original array
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
// This function partitions given array and returns
// the index of the pivot.
var partition = function(array, p, r) {
// Compare array[j] with array[r], for j = p, p+1,...r-1
var q = p;
// maintaining that:
// array[p..q-1] are values known to be <= to array[r]
// array[q..j-1] are values known to be > array[r]
// array[j..r-1] haven't been compared with array[r]
// If array[j] > array[r], just increment j.
// If array[j] <= array[r], swap array[j] with array[q],
// increment q, and increment j.
for (var j = p; j < r; j++) {
if (array[j] <= array[r]) {
swap(array, j, q);
q++;
}
}
// Once all elements in array[p..r-1]
// have been compared with array[r],
// swap array[r] with array[q], and return q.
swap(array, r, q);
return q;
};
var array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 4, 6];
var q = partition(array, 0, array.length-1);
println("Array after partitioning: " + array);
Program.assertEqual(q, 4);
Program.assertEqual(array, [5, 2, 3, 4, 6, 7, 14, 9, 10, 11, 12]);
var array = [-9, 7, 5, 11, 12, 2, 0, 3, 10, 4, -6];
var q = partition(array, 0, array.length-1);
println("Array after partitioning: " + array);
Program.assertEqual(q, 1);
Program.assertEqual(array, [-9, -6, 5, 11, 12, 2, 0, 3, 10, 4, 7]);
var quickSort = function(array, p, r) {
if(p < r) {
var pivotIndex = partition(array, p, r);
quickSort(array, p, pivotIndex - 1);
quickSort(array, pivotIndex + 1, r);
}
};
var array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
quickSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [2,3,5,6,7,9,10,11,12,14]);
var array = [-9, 75, 54, 1, 12, 2, 18, 3, 0, -6];
quickSort(array, 0, array.length-1);
println("Array after sorting: " + array);
Program.assertEqual(array, [-9, -6, 0, 1, 2, 3, 12, 18, 54, 75]);