[LT] SORT/bubble sort
7690 ワード
Bubble Sort
バブル整列の基本構造
2つの隣接要素
arr=[5,4,3,2,1]。
// 전체 배열의 길이만큼 순회하면서 버블정렬을 하게 될 건데, 이전 인덱스 값이 현재 인덱스 값보다 크면 자리를 바꾸는 방식이 버블정렬이다.
//그러니까 첫번째에는 인덱스 0번 값인 5를 가지고 비교를 할텐데,
//arr[0]이 arr[1]보다 크기 때문에 자리를 바꾼다.
>>>> [4,5,3,2,1]
//그리고 두번째에는 arr[1]이 arr[2]인 3보다 크기 때문에,
>>>> [4,3,5,2,1]
//그리고 세번째에는 arr[2]가 arr[3]인 2보다 크기 때문에,
>>>> [4,3,2,5,1]
//마지막으로는 arr[3]이 arr[4]인 1보다 크기 때문에,
>>>> [4,3,2,1,5]
//이런식으로 정렬을 하게 되고, 이것을 버블정렬이라고 부른다.
このようなソートは配列全体の長さを繰り返す.この時点で既に最下位の位置が指定されており、巡回する必要はありません.
したがって,位置を変える行為は(配列全体の長さ−1−位置固定の桁数)巡回するだけでよい.
すなわち,時間複雑度は2回for loopを適用したため平方である.
だから効率的ではないソート方法だと思いますが、他のソートに比べて書きやすくなります.
const swaps = (idx1, idx2, arr) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}
const bubbleSort = function (arr) {
for(let n = 0; n< arr.length; n++){
let cnt = 0
for (let i = 0; i< arr.length-1-n; i++){
if(arr[i] > arr[i+1]){
cnt++
swaps(i, i+1, arr)
}
}
if(cnt === 0){
break;
}
}
return arr
};
最初はこのように答えたが、最後の問題「高級問題」は解決しなかった.効率をこう見ると?の問題は、実は最初は時間の複雑さに関する効率の問題ではないと思っていました.単純にn回のツアーをするので効率が悪いと思っていますが.
コンソールで見ると,nの二乗時間の複雑さを一度からn回に変更することができ,一定の効率をもたらすことができる.
しかし,上記のコードのように書き直し,並べ替えが正しければswapを行わず,コードを行わずに直接戻り,最後の高度な問題が解決された.
以下は手書きコードの内容です.困った时はこう书かせてください.
Reference
この問題について([LT] SORT/bubble sort), 我々は、より多くの情報をここで見つけました https://velog.io/@yrkimyy/LT-SORT-bubble-sortテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol