Interview question: javascript implement quick sort

quickSort.js

/**
 * From: https://leetcode.com/problems/sort-an-array/
 * Question: quick sort
 * Given an array of integers nums, sort the array in ascending order.
 Example 1:
 Input: nums = [5,2,3,1]
 Output: [1,2,3,5]
 Example 2:
 Input: nums = [5,1,1,2,0,0]
 Output: [0,0,1,1,2,5]
 Constraints:
 1 <= nums.length <= 5 * 104
 -5 * 104 <= nums[i] <= 5 * 104
 */

/**
 * if leetcode timeout,  comment all #log
 */
var sortArray = (nums) => {
    var rand = (min, max) => {
        return min + Math.floor(Math.random() * (max - min + 1))
    }
    var swap = (i, j) => {
        var tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
    }
    var sortAndGetMid = (l, r) => {
        var pivotIdx = rand(l, r)
        // var pivotIdx = l + 1 // use pivotIdx = 1 for easy test
        var pivot = nums[pivotIdx]
        var i = l
        swap(pivotIdx, r) // must first mv pivot to last if not swap and if pivot is min or max, the array always keep origin
        for (var j = l; j < r /* for loop is aimed select <= pivot part arr and > pivot part arr, last(idx 'r') is pivot, so omit compare last */; j++) {
            if (nums[j] <= pivot) {
                swap(i, j)
                i++
            }
        }
        swap(i, r) // when finish above for, l to i - 1 <= pivot; i to r > pivot, so move pivot( to i
        return i
    }
    var sort = (l, r) => {
        if (l >= r) {
            return
        }
        var mid = sortAndGetMid(l, r)
        // nums[mid] is pivot, sortAndGetMid has make sure pivot left <= pivot pivot right > pivot, so following sort omit mid, only use mid - 1 and mid + 1,
        sort(l, mid - 1)
        sort(mid + 1, r)
    }
    sort(0, nums.length - 1)
    return nums
}
var {assertSort} = require("./sortHelper")
var asrSort = (nums) => {
    assertSort(sortArray, nums)
}
describe("quick sort", () => {
    it("1", () => {
        asrSort([3, 1, 2])
    })
    it("2", () => {
        asrSort([5, 1, 1, 2])
    })
    it("3", () => {
        asrSort([5, 2, 3, 1])
    })
    it("4", () => {
        asrSort(require("./debugNums"))
    })
})

If you like my article, donate me a coffee and let me continue

Donate

Donate backup