implement-quick-sort.md

id	title	challengeType	forumTopicId	dashedName
587d825a367417b2b2512c89	實現快速排序	1	301615	implement-quick-sort

--description--

Here we will move on to an intermediate sorting algorithm: quick sort. Quick sort is an efficient, recursive divide-and-conquer approach to sorting an array. In this method, a pivot value is chosen in the original array. The array is then partitioned into two subarrays of values less than and greater than the pivot value. We then combine the result of recursively calling the quick sort algorithm on both sub-arrays. This continues until the base case of an empty or single-item array is reached, which we return. The unwinding of the recursive calls return us the sorted array.

快速排序是一種非常有效的排序方法，平均提供 O(nlog(n)) 的性能。 它也相對容易實現。 這些屬性使其成爲一種流行且有用的排序方法。

說明： 編寫一個函數 quickSort，它將整數數組作爲輸入，並按從最小到最大的排序順序返回這些整數的數組。 雖然樞軸值的選擇很重要，但任何樞軸都可以滿足我們的目的。 爲簡單起見，可以使用第一個或最後一個元素。

--hints--

quickSort 應該是一個函數。

assert(typeof quickSort == 'function');

quickSort 應該返回一個排序的數組（從最小到最大）。

assert(
  isSorted(
    quickSort([
      1,
      4,
      2,
      8,
      345,
      123,
      43,
      32,
      5643,
      63,
      123,
      43,
      2,
      55,
      1,
      234,
      92
    ])
  )
);

quickSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]) 應該返回一個數組，除了順序之外沒有變化。

assert.sameMembers(
  quickSort([
    1,
    4,
    2,
    8,
    345,
    123,
    43,
    32,
    5643,
    63,
    123,
    43,
    2,
    55,
    1,
    234,
    92
  ]),
  [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
);

quickSort 不應使用內置的 .sort() 方法。

assert.isFalse(isBuiltInSortUsed());

--seed--

--after-user-code--

function isSorted(a){
  for(let i = 0; i < a.length - 1; i++)
    if(a[i] > a[i + 1])
      return false;
  return true;
}

function isBuiltInSortUsed(){
  let sortUsed = false;
  const temp = Array.prototype.sort;
  Array.prototype.sort = () => sortUsed = true;
  try {
    quickSort([0, 1]);
  } finally {
    Array.prototype.sort = temp;
  }
  return sortUsed;
}

--seed-contents--

function quickSort(array) {
  // Only change code below this line
  return array;
  // Only change code above this line
}

--solutions--

function quickSort(array) {
  if (array.length === 0) {
    return [];
  } else {
    const pivotValue = array[0];

    // Sort elements into three piles
    let lesser = [];
    let equal = [];
    let greater = [];
    for (let e of array) {
      if (e < pivotValue) {
        lesser.push(e);
      } else if (e > pivotValue) {
        greater.push(e);
      } else {
        equal.push(e);
      }
    }

    return [...quickSort(lesser), ...equal, ...quickSort(greater)];
  }
}