バブルソート
3321 ワード
バブルソートとは
バブルソートは、ソートアルゴリズムです.ソートアルゴリズムはデータ構造をソートするために使用されます.バブルソート
動作方法
バブルソートでは、配列内の各要素をループします.内部ループでは、要素を次の要素と比較します.現在の要素が大きい場合、要素を交換します
ステップ1
配列をとる関数を作成します.配列をループする
for
ループを作成します.function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
}
}
ステップ2
最初の
for
ループの内側に内部ループを作ります.function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
}
}
}
ステップ3
現在の要素が次の値より大きいかどうかを調べます.もしそうならば、我々は彼らを交換します.スワップするには、現在の要素を格納する
temp
変数を作成します.次に、次の要素の値を現在の要素の値に設定します.最後に、次の要素を最初の要素を格納したtemp
の値に設定します.function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}
ステップ4
ソートされた配列を返す
関数Bubblesort ( array ) { { } { } { 0 } { 0 }を指定します
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
return array;
}リファクタリングと最適化
これはかなり簡単です.あなたが密接に見えるならば、我々はループ全体にわたって進行しているが、終わりの要素がすでにソートされているにもかかわらず、我々はまだ配列全体をループしています.つの単純なリファクタを使用して、より良いコードを作ることができます.最初のループでは、最初からループするのではなく、最後からループすることができます.これは、最後にソートされた要素をもう一度ループしないようにします.
for(let i = array.length; i > 0; i--) {
for(let j = 0; j < array.length; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
我々が作ることができるもう一つの微調整は、外側のループの' i ' - 1が内側のループの' J 'より大きい限り、内部のループが走るということです.したがって、今では内側のループもソートされた要素を除外します.私たちは- 1を行い、比較されている要素を数えないようにします.関数Bubblesort ( array ) { { } { } { 0 } { 0 }を指定します
for(let i = array.length; i > 0; i--) {
for(let j = 0; j < i - 1; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}ビッグO表記
バブルソートの大きなo表記はO ( nは2に昇格)
Reference
この問題について(バブルソート), 我々は、より多くの情報をここで見つけました https://dev.to/akashshyam/bubble-sort-f12テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol