JavaScriptで文字列がソート済みかどうかを判定する方法

本記事では、文字列を受け取り、その文字列がソート済み(昇順または降順)であるかどうかを判定するJavaScript関数の作成方法を解説します。

要件の確認

作成する関数は、引数として文字列を受け取り、その文字がコードポイント順に整列しているかどうかを返します。昇順・降順のどちらか一方に統一されていれば「ソート済み」とみなします。

isSorted('adefgjmxz') // true(昇順)
isSorted('zxmfdba')   // true(降順)
isSorted('dsfdsfva')  // false(整列していない)

実装例

それでは、実際のコードを見ていきましょう。

const str = 'abdfhlmxz';

// 2文字のコードポイントの差分を計算するヘルパー関数
const findDiff = (a, b) => a.charCodeAt(0) - b.charCodeAt(0);

// 文字列がソート済みかどうかを判定する関数
const isStringSorted = (str = '') => {
  // 2文字未満なら常にソート済みとみなす
  if (str.length < 2) {
    return true;
  }
  let res = '';
  for (let i = 0; i < str.length - 1; i++) {
    // 隣り合う文字を比較し、昇順なら 'u'、降順なら 'd' を記録
    if (findDiff(str[i + 1], str[i]) > 0) {
      res += 'u';
    } else if (findDiff(str[i + 1], str[i]) < 0) {
      res += 'd';
    }
    // 昇順と降順が混在した時点でソート済みではない
    if (res.includes('u') && res.includes('d')) {
      return false;
    }
  }
  return true;
};

console.log(isStringSorted(str));

出力

コンソールには以下のように出力されます。

true

コードの解説

この関数の仕組みを順を追って説明します。

• findDiff: 2つの文字のcharCodeAt()の値(Unicodeコードポイント)の差を返します。正の値なら昇順、負の値なら降順を意味します。
• 早期リターン: 長さが2未満の文字列は必ずソート済みとみなせるため、即座にtrueを返します。
• ループ処理: 隣り合う文字同士を比較し、結果を 'u'(昇順)または 'd'(降順)として記録します。
• 混在の検出: 'u' と 'd' の両方が記録された時点で、文字列が一貫した順序になっていないことが確定するため、falseを返します。

なお、判定条件に res.indexOf('u') を使うと、'u' が存在しない場合に -1 が返され、真偽値として意図しない評価になってしまうため注意が必要です。代わりに res.includes('u') を使うことで、昇順・降順の混在を正しく検出できます。

別のシンプルな実装

より簡潔に書きたい場合は、文字列をソートした結果と比較する方法もあります。

const isSorted = (str = '') => {
  const asc = [...str].sort().join('');
  const desc = [...str].sort().reverse().join('');
  return str === asc || str === desc;
};

console.log(isSorted('adefgjmxz')); // true
console.log(isSorted('zxmfdba'));   // true
console.log(isSorted('dsfdsfva'));  // false

この方法では、元の文字列が昇順ソートした結果または降順ソートした結果と一致するかを確認するだけで、意図が明確で読みやすいコードになります。ただし内部でソート処理が発生するため、非常に長い文字列を扱う場合は、前述の1回のループで完結する線形探索アプローチ(O(n))の方が効率的です。

まとめ

文字列がソート済みかどうかの判定は、隣り合う文字の比較を1回のループで行うことでO(n)の計算量で実現できます。昇順・降順のどちらにも対応させたい場合は、方向の混在を検出する方法がシンプルかつ効率的です。用途や文字列の長さに応じて、2つの実装を使い分けるとよいでしょう。