# Javascript solution(write out quicksort)

• var arrayPairSum = function(nums) {
// get the largest possible sum of MIN of the pair.
// eg: [1,2,3,4] => (1,2) and (3,4).  min(1,2) + min(3,4) = 4
// so the core is to understand:  why (1,2) and (3,4) would result to best possible sum?
// intuitive: to get the best possible sum, need to make the min number in the pair as large as possible.
// as proof in https://discuss.leetcode.com/topic/87206/java-solution-sorting-and-rough-proof-of-algorithm/3 ,
// cont'd , in order to make |ai - bi| smallest, THEY SHOULD BE ADJACENT
// solution: sort, then add 1st, 3rd... elem of the sorted array

// quick sort
// partition arr first, then quicksort smaller part(from code, recursive, check backwards one by one), then quicksort bigger part(recursive, check forward one by one)
var p = 0;  // first index of arr, arr[p...r]
var r = nums.length - 1;  // last index of arr, arr[p...r]
var i;  // the last index of "smaller part"
var pivot, j, save, q;
var result = 0;

var quickSort = function(A, p, r) {
if (p < r) {
q = partition(A, p, r);
// smaller part, and bigger part
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}

var partition = function(nums, p, r) {
pivot = nums[r];
i = p - 1;
for (j = p; j < r; j++) {
if (nums[j] <= pivot) {
i++;
// if current elem is smaller than pivot, and there are bigger-than-pivot checked elem(s), switch cur with the first bigger-than-pivot-checked elem
// if not, just switch with itself, so no change
save = nums[j];
nums[j] = nums[i];
nums[i] = save;
}
}
// insert as separator
save = nums[r];
nums[r] = nums[i+1];
nums[i+1] = save;

return i+1;
}

// test partition
console.log(partition(nums, p, r));

quickSort(nums, p, r);
console.log(nums);

// add 1st, 3rd elems of array
for (i = 0; i < nums.length; i += 2) {
result += nums[i];
}

return result;
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.