選択ソート《ソートアルゴリズム》

素朴なソートアルゴリズムメニュー【選択ソート】

問題【選択ソート】
Task
選択ソートを実装して i 行目に i 回目のループ処理終了時の 配列 を出力してね。

【選択ソート】コード 1/2

reader.on('close', () => {
   const selection_sort = (A, N) => {
      for (let i = 0; i < N - 1; i++) {
         let min = A[i];  // A[i] を 最小値と仮定
         let min_index = i;  // i を最小値の添字と仮定
         for (let j = i + 1; j < N; j++) {
            if (A[j] < min) {  // A[j] が 仮最小値より小さければ…
            min = A[j];  // 仮最小値を A[j] とする
            min_index = j;  // j を最小値の添字とする
         }
      }
      [A[i], A[min_index]] = [A[min_index], A[i]];  // A[i] と 最小値を入替
      console.log(...A);  // A[i] までソート処理終了時の配列を出力
      }
   };
   const n = Number(lines[0]);  // 要素数
   const arr = lines[1].split(' ').map(Number);  // ソートする要素
   selection_sort(arr, n);
});
hogeちゃんの画像

選択ソート…。とりあえず 解説どおり実装しました。最小値を探索して A[i] と最小値を入れ替えれば最終的に昇順に並べ替えられました。

top

【選択ソート】コード 2/2

reader.on('close', () => {
   const selection_sort = (A, N) => {
      for (let i = 0; i < N - 1; i++) {
         const Min = Math.min(...A.slice(i));  // A[i] ~ A[N - 1] の最小値
         const min_index = A.slice(i).indexOf(Min) + i;  // A[i] ~ A[N - 1] の最小値 の A の添字
         [A[i], A[min_index]] = [A[min_index], A[i]];  // A[i] と A[i] ~ A[N - 1] の最小値を入替
         console.log(...A);
      }
   };
   const n = Number(lines[0]);  // 要素数
   const arr = lines[1].split(' ').map(Number);  // ソートする要素
   selection_sort(arr, n);
});
hogeちゃんの画像

こっちのほうがスッキリ書けるけど 実行時間は同じでした。

top

コメント