Abstract

我是阿傑，昨天 (Day 26) 介紹了 sort() 的基本用法，今天就來介紹 ECMAScript 演算法的部分，這邊會用我的理解將其拆成幾個部份，應該可以稍微減少閱讀的負擔。

這裡會將整個演算法分以下成幾個部分：

• 前言
• 前置處理 (步驟 1 ~ 3)
• 建立抽象閉包 (步驟 4)
• 這個抽象閉包做了什麼 (步驟 4)
• IsLessThan() 做了什麼？
• SortIndexProperties 在幹嘛 (步驟 5)
• 注意事項

ECMAScript

• ECMA 連結 - Array.prototype.sort
• 語法 - Array.prototype.sort(comparefn)

前言

如果你有點進連結，你會看到 ECMAScript 在前言便馬上告訴你 sort() 必須是 stable 的，前面 (Day 28) 有提到這個 issue 其實是在 ES 第 10 版 才做改動的，我們找第 9 版的規範來驗證一下吧：

所以現在使用 sort() 的話，陣列最終的排序會是穩定的 (比較相同的元素會維持各自原來的順序)。

而這邊也告訴你 - 如果你有提供 comparefn ，它應該是像下列的形式：

• 它必須是一個接受 2 個參數 (x、y) 的函式
• 當 x < y 時必須回傳 1 個 負數 (negative)
• 當 x > y 時必須回傳一個整數 (positive)
• 否則回傳 0 (x === y)

例如這樣:

function comparator(a, b) {
	if (a < b) return -1
	if (a > b) return 1
	return 0
}

前置處理 (步驟 1 ~ 3)

步驟 1 表明了，如果有提供 comparefn，那它就必須是一個可呼叫的物件 (也就是 function)，否則會丟出一個 TypeError。

步驟 2 跟 Note 3 清楚地表明 sort() 被做成了 1 個通用的咩色，也就是說呼叫 sort() 的物件並沒有強制為一個陣列：我們來驗證看看：

const fakeArray =  {
	0: 1,
	1: 2,
	2: 0,
	length: 3
}

const sorted = [].sort.call(fakeArray)
console.log(sorted)
// {0: 0, 1: 1, 2: 2, length: 3}

步驟 3 則利用 LengthOfArrayLike 這個抽象操作，取到 length 屬性的值，也就是說只要這個物件有 length 這個屬性便可以取得，例如這種類似陣列的物件：

const fakeArray = {0: 'Pedro', length: 1}

建立抽象閉包 (步驟 4)

步驟 4 就是整個 sort() 的核心了！這邊使用了一個我們之前沒看過的操作 - Abstract Closure，我們先來講講它吧 (以下都使用 Closure 來簡稱)：

• Closure 是一種規範類型 (specification type - 存在於規範之中，不一定有實作)，它被用來處理演算法步驟跟一連串值的集合。
• Closure 看起來就像是一般的函式或抽象操作，會以這種型態出現 closure(arg1, arg2)，呼叫它便會執行內部的演算法步驟。
• Closure 在建立的時候會立即捕獲 (capture) 一連串的值，這些值是什麼呢？它會是 Closure 內部演算法執行時需要用到的值，而Closure 用到的值可以看作是一連串的別名 (aliases)，這些別名會對應到當下外部同名的值！也就是說Closure 會去捕獲這些於外部它需要的值。
• Closure 回傳的會是一個 normal completion 或 throw completion，就像是一般的函式一樣
• 可以把 Closure 想像成 JavaScript 中的閉包，應該會較好理解，例如這樣：

function outer(para) {
	const outerVariable = 'Hi'

	// 這裡建立了一個 inner 閉包，它會捕獲 para 跟 outerVariable
	function inner() {
		console.log(para + outerVariable)
	}
}

抽象閉包做了什麼？(步驟 4)

我們可以看到 sort() 在步驟 4 建立了一個 Abstract Closure - SortCompare(x, y)，並在其內部定義了一連串的演算法，同時它也捕獲了傳進 sort() 的參數 - comparefn ，這也表示 SortCompare() 的演算法會使用到 comparefn，我們來研究一下這個閉包會做什麼。

當 x 跟 y 都為 undefined 時回傳 0，也就是雙方位置不變，而步驟 b、c 可以看到當 x 或 y 其中一方為 undefined 時，會將 undefine 的元素直接往後排，這也驗證了 undefined 屆時會排在陣列的最後方。

步驟 d 可以看到當 comparefn 存在時，SortCompare() 會將其捕獲並在這裡呼叫 comparefn 並同時帶入 x、y 兩個參數，最後 SortCompare() 會將 comparefn 回傳的值轉型後回傳出去，並終止執行。

而接下來的步驟 e ~ k 個人認為非常重要，因爲這段就是 sort() 自身預設的排序方法，首先它會先將 x 、 y 轉成字串，接著使用 IsLessThan() 來比較它們：

• 當 x 小於 y 回傳 -1
• 當 x 大於 y 回傳 1
• 當 x 等於 y 回傳 -1

我們來總結一下這個抽象閉包 (SortCompare) 做了什麼

• 它捕獲了 comparefn 以方便之後使用它
• 它將所有的 undefined 往後排
• 如果有提供 comparefn 便會呼叫它來進行比較
• 如果沒有提供 comparefn 便會使用預設的排序方法，而這個方法主要的核心為 IsLessThan() 這個抽象操作，它利用了 UTF-16 的編碼來排序元素

我們接著來看 IsLessThan() 做了什麼?

IsLessThan() 做了什麼？ (步驟 4)

• IsLessThan(x, y, LeftFirst)

IsLessThan() 接受 3 個參數，其中的 x 跟 y 為 2 個會互相比較的值，而 LeftFirst 這個布林 flag 則是決定誰會出現在左邊 (前面)。

這個抽象操作的語義就是 比較 x 是否小於 y ，它會回傳 true、false 或 undefined (x、y 至少其中一個是 NaN)。

而 LeftFirst 這個 flag 很容易讓人困惑， 由於 ECMAScript 的表達式必須從左至右做運算，為了保持這個特性，當 LeftFirst 為 true 時，它會讓跟 x 相對應的表達式出現在跟 y 相對應的表達式左方，反之則讓 y 對應的表達式出現在 x 對應的表達時左方，可以看到前兩個步驟 (1、2) 就是在做這件事：

• 當 LeftFirst 為 true 時

• 當 LeftFirst 為 false 時

由於 SortCompare() 在呼叫 IsLessThan() 前便已將 x、y 轉成字串，因此在這裡我們只需關注步驟 3 的字串間比較即可，步驟 3 會先取得 x 跟 y 的長度，利用長度較短的一方來建立迴圈次數，重複以下步驟：

• 從 x 跟 y 各取一個相對應索引的字元
• 使用它們的字元編碼 (code unit) 來比較大小
• 如果 x 當前字元的編碼小於 y 當前字元的編碼，回傳 true
• 如果 x 當前字元的編碼大於 y 當前字元的編碼，回傳 false
• 如果上面的結果都是相等，則直接比較 x 跟 y 的長度，如果 x 長度小於 y 回傳 true ，否則回傳 false

綜上所述，因為有 IsLessThan() 這個抽象操作，所以當我們沒有提供 comparefn 給 sort() 時，預設的排序結果會是字典序的排序方式 (lexicographic)。

SortIndexProperties 在幹嘛 (步驟 5)

當抽象閉包 - SortCompare() 建立完成後，sort() 就會執行最後的步驟 5，就是呼叫 SortIndexProperties() 這個抽象操作，並且帶入 obj、len、SortCompare 三個參數，我們就來解析一下這個操作吧。

首先它創造了 1 個新陣列 - items，並淺拷貝 (shallow copy) 了原陣列的每個元素，接下來排序都會發生在這個 items 上而非原陣列。

其中的步驟 5 非常關鍵，這裡會發現 ECMAScript 並沒有直接規定應該要使用何種演算法，它把發球權交給了各自的實作，這意味著實作可以自由選擇 Quick Sort 、Insertion Sort 或 Tim Sort 等等演算法來實現它們的排序，它們要做的就是在自己的演算法內呼叫被傳進去的抽象閉包 - SortCompare()

當 items 被排序完成後，會在步驟 7 將每個元素設值到原陣列對應的索引上，如果原陣列有多出來的元素，會於步驟 8 將其刪除，也就是當 items 完成排序後才將其映射到原陣列上。

最後便將原陣列回傳出去，結束了 sort() 的執行。

注意事項

出現 ? 的地方代表有可能會丟出錯誤，所以整個演算法有 6 處有機會丟出錯誤，例如步驟 1 的 ToObject() 會在 this 是一個 Undefined 或 Null 時丟出一個 TypeError 的錯誤，我們來驗證一下：

上面可以發現當 this 被指定為 true 時不會發生錯誤，且被 ToObject() 轉成一個物件 。

如果出現 ! ，則代表這個抽象操作 (abstract operation) 絕對不會丟出錯誤，例如步驟 4-g 的 IsLessThan()，由於傳進去的 x、y 皆為字串所以不會有錯誤發生。

從 ECMAScript 的演算法來看，尚未找到與 JavaScript 實作的不同之處。

實作一個 sort 看看

注意！這個客製化版本的 sort() 極其簡易，略過了非常多的步驟跟檢查，因此不是一個嚴謹好用的函式！這邊是想確定我們是否能利用 ECMAScript 所提供的演算法實作出一個咩色。

const array = [2, 16, 3, 100, 41];

const sorted1 = sort([...array], (a, b) => {
  if (a > b) return -1;
  if (a < b) return 1;
  return 0;
});

const sorted2 = sort([...array], (a, b) => {
  if (a > b) return 1;
  if (a < b) return -1;
  return 0;
});

const sorted3 = sort([...array]);

console.log(sorted1);
// [100, 41, 16, 3, 2]

console.log(sorted2);
// [2, 3, 16, 41, 100]

console.log(sorted3);
// [100, 16, 2, 3, 41]


//------- 以下為 function 定義 --------

function sort(array, comparator) {
  const len = array.length;

  // closure
  function sortCompare(x, y) {
    // 將 undefined 往後排
    if (x === undefined && y === undefined) return 0;
    if (x === undefined) return 1;
    if (y === undefined) return -1;

    // 使用 comparator 來定義排序
    if (comparator) return comparator(x, y);

    // 如果沒有 comparator 則使用預設的排序
    // 先轉成字串
    const xString = String(x);
    const yString = String(y);

    // 使用 lessThan() 比較 x, y 的 UTF-16
    const xSmaller = lessThan(xString, yString);
    if (xSmaller) return -1;

    const ySmaller = lessThan(yString, xString);
    if (ySmaller) return 1;

    return 0;
  }

  return sortIndexProperty(array, sortCompare);
}

function sortIndexProperty(array, sortCompare) {
  // 先複製陣列
  const items = [...array];

  // bubble為實作使用的演算法
  // 它會根據 sortCompare 回傳的值來排序複製後的陣列
  bubbleSort(items, sortCompare);

  // 將 item 映射至原陣列上
  items.forEach(function (item, index) {
    this[index] = item;
  }, array);

  return array;
}

// 比較 UTF-16 的 function
function lessThan(x, y) {
  const lx = x.length;
  const ly = y.length;
  const loopLength = Math.min(lx, ly);

  for (let i = 0; i < loopLength; i++) {
    const cx = x[i].charCodeAt();
    const cy = y[i].charCodeAt();

    if (cx < cy) return true;
    if (cx > cy) return false;
  }
  return lx < ly;
}

// 實作使用的排序演算法
function bubbleSort(arr, sortCompare) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (sortCompare(arr[j], arr[j + 1]) === 1) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

結論

sort() 是一個很方便的咩色，但它會改動到原陣列，務必注意！

sort() 引用了不少複雜的抽象操作，所以看起來會非常難懂，如果試著將其拆開，應該會比較好理解。

最後，希望大家可以開心地使用各種咩色，體驗它帶給你的便利，祝大家歸剛沒煩惱。

參考資源

• Array.prototype.sort - MDN
• Draft ECMA 262 - TC39