簡単
ソート：乱れた配列を昇順または降順に並べ替えること。ソートのアルゴリズムには、バブルソート、選択ソート、挿入ソート、サブサンプションソート、クイックソートなどがあります。
検索 ： 配列内の要素の添え字を検索します。配列の indexOf メソッド。検索アルゴリズムには、逐次検索、バイナリ検索...
ソート1：バブルソート
/**
* 時間の複雑さはO(n^2)
* 空間の複雑さはO(1)
*
* 1最初のラウンドでは、現在の要素と次の要素が比較され、1ラウンド後に最大値が最後の場所に移動する。
* 2 n-1
*/
Array.prototype.bubbleSort = function () {
for(let i = 0; i < this.length-1; i++){// n-1
for (let j = 0; j < this.length - 1 -i; j++) { //各歩行の後、k番目に大きいものを最後に押す
if (this[j] > this[j + 1]) {
const temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
}
}
}
var arr = [5,4,3,2,1];
arr.bubbleSort();
ソート2：セレクションソート
/**
* 時間の複雑さはO(n^2)
* 空間の複雑さはO(1)
*
* 1最初のラウンドでは、現在の最小値と現在の値を比較し、最小値の位置を見つける。
* 2 n-1
*/
Array.prototype.selectionSort = function(){
for(let i = 0; i < this.length; i++){ // n-1
let indexMin = i;
for (let j = i; j < this.length; j++) { //最初のラウンドで最小値を見つけ、それを1位にする
if (this[indexMin] > this[j]) {
indexMin = j;
}
}
if (indexMin != i){
const temp = this[i];
this[i] = this[indexMin];
this[indexMin] = temp;
}
}
}
const arr = [5, 4, 3, 2, 1];
arr.selectionSort();
ソート3：挿入ソート
/**
* 時間の複雑さはO(n^2)
* 空間の複雑さはO(1)
*
* 12番目の要素から始めて、その前の番号と比較する。その前に並べなければならない
* 2 n-1
*/
Array.prototype.insertionSort = function(){
for(let i = 1; i < this.length; i++){
for (let j = i; j > 0; j--) {//正しい場所を見つけるために前進する
if (this[j] < this[j - 1]) {
const temp = this[j];
this[j] = this[j-1];
this[j-1] = temp;
} else {
break;
}
}
}
}
let arr =[5, 3, 4, 2, 1];
arr.insertionSort();
ソート4：サブサンプション
/**
*
* 時間の複雑さの合計はO(n*logn)
* 1二分法：配列を2つに分割し、個々の数値に分割されるまで再帰的に部分配列を「分割」する。時間の複雑さはO(logn)
* 2マージ：2つの数値を順序付き配列にマージし、すべての部分配列が完全な配列にマージされるまで、順序付き配列をマージする。時間の複雑さはO(n)
*
* アルゴリズムのステップ
* 1最終的にソートされた配列を格納するために、新しい配列resを作成する。
* 22つの順序付き配列の先頭を比較し、小さい方をキューから取り出し、resにプッシュする。
* 3配列にまだ値がある場合は、ステップ2を繰り返す
*/
Array.prototype.mergeSort = function () {
const rec = function (arr) {
if(arr.length == 1){
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, arr.length);
let orderLeft = rec(left);
let orderRight = rec(right);
let res = [];
while (orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length){
res.push(orderLeft[0] > orderRight[0] ? orderRight.shift() : orderLeft.shift());
} else if (orderLeft.length){
res.push(orderLeft.shift())
} else {
res.push(orderRight.shift())
}
}
return res;
}
const res = rec(this);
return res.forEach((n, i) => {
this[i] = n;
});
}
let arr = [5,4,3,2,1];
arr.mergeSort();
ソート5：クイックソート
/**
* 再帰的な時間の複雑さはO(logn)
* パーティショニング操作の時間複雑度はO(n)
* 時間の複雑さの合計はn(n*logn)
*
* アルゴリズムのステップ
* パーティショニング：配列から任意のデータムを選択し、データムより小さい要素はすべてデータムの前に、データムより大きい要素はすべてデータムの後ろに配置する。
* 再帰：ベンチマーク前後のサブ配列の再帰的分割
*
*/
Array.prototype.quickSort = function(){
const rec = function(arr){
if(arr.length <= 1){
return arr;
}
let left = [];
let right = [];
let mid = arr[0];
for(let i = 1; i < arr.length; i++){
if(arr[i] < mid){
left.push(arr[i])
} else {
right.push(arr[i]);
}
}
return [...rec(left), mid, ...rec(right)];
}
const res = rec(this);
res.forEach((n, i) => {
this[i] = n;
});
}
let arr = [5,4,3,2,1];
arr.quickSort();
検索1：逐次検索
/**
* 逐次検索
* 時間の複雑さはO(n)
*/
Array.prototype.sequentialSearch = function(target){
for (let i = 0; i < this.length; i++) {
if (this[i] === target){
return i;
}
}
return -1;
}
const res = [1,2,3,4,5].sequentialSearch(6);
console.log(res);
検索2：二分法検索
/**
* 時間の複雑さはO(logn)
* 前提条件配列は順序配列である
*
* アルゴリズムのアイデア
* 1配列の真ん中の要素から検索を開始し、真ん中の要素がちょうどターゲット値であれば、検索は終了する。
* 2ターゲット値が真ん中の要素より大きいか小さい場合、真ん中の要素より大きいか小さい配列の半分を検索する。
*/
Array.prototype.binarySearch = function (target) {
let low = 0;
let high = this.length -1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (this[mid] > target){
high = mid - 1;
} else if (this[mid] < target){
low = mid + 1;
} else {
return mid;
}
}
return -1;
}
const res = [1, 2, 3, 4, 5].binarySearch(6);
console.log(res);
