整列JavaScript(3)整列選択と整列挿入
17277 ワード
ソートの選択
定義#テイギ#
ソートの選択とは、最小のアイテムを見つけて、そのアイテムを現在の位置に挿入するソート方法です.
これは前述した泡の並べ替えよりも良い方法である.
コード#コード#
選択ソートを実装するコードは次のとおりです.
function selectionSort(items) {
// 배열간 element를 교환해주는 함수 생성
const swap = (array, index1, index2) => {
const temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
let min;
for (let i=0;i<items.length;i++) {
min = i;
// 더 작은 항목이 있는지 배열의 나머지를 확인한다.
for (let j=i+1;j<items.length;j++) {
if (items[j] < items[min]) min = j;
}
// 현재 위치가 최소항목 위치가 아니라면 항목 교환
if (i != min) swap(items, i, min);
}
return items;
}
選択ソートもバブルソートと同様に二重複文を用いたため,時間的複雑度はO(n^2)であった.整列挿入
定義#テイギ#
ソートの挿入は、配列を順番に検索しながら、ソートされていない項目を配列の左側の位置合わせ部分に移動するソート方法です.次に、位置合わせされた画像を挿入します.
コード#コード#
挿入ソートコードを記述するには、次の手順に従います.
const insertionSort = function (arr) {
// TODO: 여기에 코드를 작성합니다.
// value; // 현재 비교중인 값
// i; // 정렬 X 인덱스
let j; // 정렬 o 인덱스
for (let i=0;i<arr.length;i++) {
let value = arr[i];
for (j=i-1;j > -1 && arr[j] > value;j--) {
arr[j+1] = arr[j];
}
arr[j+1] = value;
}
return arr;
};
上のコードは、ソート関数を選択するパラメータに配列を追加しただけです.位置合わせ関数を挿入するのもArrayです.prototype.sort()関数のようにコールバック関数を加えることもできます.
パラメータでコールバック関数を追加するコードを次に示します.
const insertionSort = function (arr, transform = (item) => item) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (transform(arr[i]) >= transform(sorted[i - 1])) {
sorted.push(arr[i]);
} else {
for (let j = 0; j < i; j++) {
if (transform(arr[i]) <= transform(sorted[j])) {
const left = sorted.slice(0, j);
const right = sorted.slice(j);
sorted = left.concat(arr[i], right);
break;
}
}
}
}
return sorted;
};
上のコードは、下のコードのarr[i]部分をコールバック関数に変換する関数値です.const insertionSort = function (arr) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (arr[i] >= sorted[i - 1]) {
sorted.push(arr[i]);
} else {
for (let j = 0; j < i; j++) {
if (arr[i] <= sorted[j]) {
const left = sorted.slice(0, j);
const right = sorted.slice(j);
sorted = left.concat(arr[i], right);
break;
}
}
}
}
return sorted;
};
Reference
この問題について(整列JavaScript(3)整列選択と整列挿入), 我々は、より多くの情報をここで見つけました https://velog.io/@porupit0122/JavaScript-정렬-3-선택-정렬과-삽입-정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol