Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: [5,2,3,1]
Output: [1,2,3,5]Example 2:
Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]Note:
1 <= A.length <= 10000
-50000 <= A[i] <= 50000
Relevant posts: How to Implement Quicksort Algorithm in Python – the Pythonic Way and Quick Demonstration of Quick Sort in Python
QuickSort in Javascript
Similarly, the quicksort implementation in Javascript can be done via Recursion. The first step is to pick a random element from the current array, which can be done via generating a random index. Here ia another post: The Recursive QuickSort Implementation in C++
The second step is to group the numbers in the array into three: the smaller ones, the equals ones and the larger ones.
Then, by recursions (to sort out the smaller and larger groups), we can concatenate (append arrays one by one) the groups by using Javascript triple dots notation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** * @param {number[]} nums * @return {number[]} */ var sortArray = function(nums) { if (nums.length === 0) return []; // pick a random value e.g. random.choice let x = nums[Math.floor(Math.random() * nums.length)]; let lt = []; let eq = []; let gt = []; // separate into three groups nums.map(a => { if (a < x) lt.push(a); else if (a === x) eq.push(a); else gt.push(a); }); // concatenate the part results let n = sortArray(lt); n.push(...eq); n.push(...sortArray(gt)); return n; }; |
/** * @param {number[]} nums * @return {number[]} */ var sortArray = function(nums) { if (nums.length === 0) return []; // pick a random value e.g. random.choice let x = nums[Math.floor(Math.random() * nums.length)]; let lt = []; let eq = []; let gt = []; // separate into three groups nums.map(a => { if (a < x) lt.push(a); else if (a === x) eq.push(a); else gt.push(a); }); // concatenate the part results let n = sortArray(lt); n.push(...eq); n.push(...sortArray(gt)); return n; };
Powerful, Simple and elegant – despite the fact that Javascript may look weird in some aspects!
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: In-place Run-Length String Compressions using C++
Next Post: Coding Exercise: Sum of Digits in the Minimum Number
It’s not a quicksort. Looks like some kind of a merge sort (instead of two sorted arrays you have one more equal array)
In the case of quicksort you will have a median pointer and switch values inside the same array `[arr[left], arr[right]] = [arr[right], arr[left]]`