ES2015でどこまでクイックソートを短くかけるか

やってみた。

function quick(arr) {
  if (arr.length === 0) return []
  const [pivot, ...tail] = arr
  return [...quick(tail.filter( x => x <= pivot )),  pivot , ...quick(tail.filter( x => x > pivot ))]
}

const sorted = quick([8, 1, 10, 5, 4, 5, 1, 7, 9])
console.log(sorted) // [ 1, 1, 4, 5, 5, 7, 8, 9, 10 ]

実行環境

Node >= v7.ｘ

ポイント

filterを一行で書く場合returnも {}もいらない

これmapだけだと思っていましたがfilterでも使えるようです。

tail.filter( x => { return x <= pivot } )
// ↓
tail.filter( x => x <= pivot)

スプレッド演算子大活躍

• Haskellのパターンマッチでリストのheadとtailを分割する方法を似せて書こうとすることが出来る
  • デストラクチャリング + スプレッド演算子

 const [pivot, ...tail] = arr

• 配列の結合はスプレッド演算子でやる

[...quick(tail.filter( x => x <= pivot )),  pivot , ...quick(tail.filter( x => x > pivot ))]

もっとエレガントに出来るところあるか？

関連書籍

すごいHaskellたのしく学ぼう!