この記事では、バブルソートアルゴリズムについて説明します。バブルソートの作業手順は最も簡単です。この記事は、バブルソートが試験問題として出題される可能性がある学生にとって、非常に役立ち、興味深いものとなるでしょう。したがって、そのテーマについて話し合うことが重要です。
フレームtkinter
バブル ソートは、意図した順序にならなくなるまで、隣接する要素を繰り返し交換します。配列要素の動きが水の中の気泡の動きに似ているため、バブル ソートと呼ばれます。水中の泡は水面まで上昇します。同様に、バブルソートの配列要素は各反復で最後に移動します。
使い方は簡単ですが、現実世界ではバブル ソートのパフォーマンスが低いため、主に教育ツールとして使用されます。大規模なデータセットには適していません。バブル ソートの平均および最悪の場合の複雑さは次のとおりです。 の上2）、 どこ n 項目数です。
バブルショートは主に以下の場合に使用されます。
- 複雑さは関係ありません
- シンプルでショートコードが好ましい
アルゴリズム
以下に示すアルゴリズムでは、次のように仮定します。 到着しました の配列です n 要素。想定される スワップ アルゴリズム内の関数は、指定された配列要素の値を交換します。
begin BubbleSort(arr) for all array elements if arr[i] > arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort
バブルソートアルゴリズムの仕組み
それでは、バブルソートアルゴリズムの仕組みを見てみましょう。
バブル ソート アルゴリズムの動作を理解するために、ソートされていない配列を取り上げてみましょう。バブルソートの複雑さはわかっているので、短くて正確な配列を取得しています。 の上2）。
配列の要素を次のようにします -
最初のパス
ソートは最初の 2 つの要素から開始されます。どちらが大きいかを比較してみましょう。
ここで、32 は 13 より大きい (32 > 13) ため、すでにソートされています。次に、32 と 26 を比較してください。
ここで、26 は 36 より小さいため、スワップが必要です。交換後の新しい配列は次のようになります -
では、32 と 35 を比較してください。
ここで、35 は 32 より大きいです。したがって、これらはすでにソートされているため、交換する必要はありません。
ここで、比較は 35 と 10 の間になります。
ここで、10 はソートされていない 35 よりも小さいです。ですので、交換が必要となります。これで、配列の最後に到達しました。最初のパスの後、配列は次のようになります -
次に、2 番目の反復に進みます。
2回目のパス
2 回目の反復でも同じプロセスが続きます。
地図Java
ここで、10 は 32 より小さいため、スワップが必要です。交換後の配列は次のようになります -
次に、3 回目の反復に進みます。
3回目のパス
3 回目の反復でも同じプロセスが続きます。
ここで、10 は 26 より小さいため、スワップが必要です。交換後の配列は次のようになります -
次に、4 番目の反復に進みます。
4回目のパス
同様に、4 回目の反復の後、配列は -
したがって、スワップは必要ないため、配列は完全にソートされます。
バブルソートの複雑さ
ここで、バブル ソートの時間計算量を最良のケース、平均的なケース、最悪のケースで見てみましょう。バブルソートの空間の複雑さも見ていきます。
1. 時間計算量
| 場合 | 時間計算量 |
|---|---|
| 最良の場合 | の上） |
| 平均的なケース | の上2) |
| 最悪の場合 | の上2) |
2. 空間の複雑さ
| 空間の複雑さ | ○(1) |
| 安定した | はい |
- バブルソートの空間計算量は O(1) です。バブルソートでは入れ替えのために余分な変数が必要になるからです。
- 最適化されたバブル ソートの空間複雑さは O(2) です。これは、最適化されたバブル ソートでは 2 つの追加の変数が必要になるためです。
ここで、最適化されたバブル ソート アルゴリズムについて説明します。
最適化されたバブルソートアルゴリズム
バブル ソート アルゴリズムでは、配列がすでにソートされている場合でも比較が行われます。そのため、実行時間が長くなります。
それを解決するには、追加の変数を使用できます 交換した。 に設定されています 真実 スワップが必要な場合。それ以外の場合は、次のように設定されます 間違い。
反復後に、スワップが必要ない場合、変数の値を変更すると便利です。 交換された になるだろう 間違い。 これは、要素がすでに並べ替えられており、それ以上の反復は必要ないことを意味します。
この方法により、実行時間が短縮され、バブル ソートも最適化されます。
最適化されたバブルソートのアルゴリズム
bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] > array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort
バブルソートの実装
ここで、さまざまなプログラミング言語でのバブル ソートのプログラムを見てみましょう。
Javaの文字列に等しい
プログラム： C言語でバブルソートを実装するプログラムを書きます。
#include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are -
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are -
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
before sorting array elements are -
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>'); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - ' + ' <br>'); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;> 出力
プログラム： PHPでバブルソートを実装するプログラムを作成します。
<?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>'; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>'; printArray($a); ?> </5;> 出力
プログラム： Pythonでバブルソートを実装するプログラムを書きます。
a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print(\' after sorting array elements are - \') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:>