LoginSignup
kok1219
@kok1219 (koki kobayashi)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

javascript　sortメソッドを使用せずに配列の並び替え

Q&A

Closed

JavaScriptsort配列並び替え降順

解決したいこと

sortメソッドを使用せずに配列の並び替えをしたいです。
どんなやり方があるでしょうか？
ご教示いただきたいです。

スクリーンショット 2022-02-15 22.19.59.png

該当するソースコード

ソースコードを入力
送信 

let array = [];

button.addEventListener('click', function (){
  let textBox = document.getElementById('input');
  let inputValue = textBox.value;
  let output = inputValue;
  let num = document.getElementById('input').value;


  if(!isNaN(num)){
  array.push(num);
  array.sort(function(a,b){
    return (a-b)
  });

  console.log(array);

  } else {
  alert("数値以外が入力されています");
  return document.getElementById('input').value = "";
  }

  document.getElementById('outputArea').textContent = Array.from(new Set(array));
  document.getElementById('input').value = "";


});

0

2Answer

blue32a
@blue32a

ソートアルゴリズムを使って、自分でソートすることができます。

中でも簡単なものはバブルソートで「隣接する要素と比較し順序が逆であれば入れ替える」というのを繰り返していくものです。

0Like
PondVillege
@PondVillege

クイックソート1で書いておきます．定義は，

{\rm qsort(L)} = \left\{\begin{array}{lrl}
[] & {\rm if} & L = [] \\
{\rm qsort}(L_1) + [x] + {\rm qsort}(L_2) & {\rm if} & L = [x] + L'
\end{array}\right.

where

L_1 = [y\ \  |\ \  y \in L'\ \  {\rm and}\ \  y \le x] \\
L_2 = [y\ \  |\ \  y \in L'\ \  {\rm and}\ \  y > x]

になります．コードで実現すると

let array = [6, 10, 11, 69, 4, 20, 1, 31, 15, 71, 99];

function qsort(L) {
	if (L.length == 0) return [];
	let x = L.shift();
	let [L1, L2] = [[], []];
	L.forEach((y) => {
		if (y <= x) L1.push(y);
		else L2.push(y);
	});
	return qsort(L1).concat([x].concat(qsort(L2)));
}

console.log(qsort(array));

になります．
先の解答にあるバブルソートは計算量が$O(N^2)$，クイックソートは平均計算量が$O(N {\rm log} N)$になります．

ただ，クイックソートはHoareさんのような天才でなければ思いつかないので課題で実装されるなら無難にバブルソートをお勧めします．

  1. C.A.R. Hoare, "Quicksort," The Computer Journal, Volume 5, Issue 1, 1962, Pages 10-16, https://doi.org/10.1093/comjnl/5.1.10 ↩

0Like

Comments

  1. @kok1219

    Questioner

    バブルソート調べたらすごくわかりやすかったです！
    ありがとうございます！！

Your answer might help someone💌

LoginSign Up