logo

TechCodeview

バブル ソート – データ構造とアルゴリズムのチュートリアル

バブルソート 最も単純です ソートアルゴリズム これは、隣接する要素の順序が間違っている場合に繰り返し入れ替えることによって機能します。このアルゴリズムは、平均および最悪の場合の時間計算量が非常に高いため、大規模なデータ セットには適していません。

バブルソートアルゴリズム

バブルソートアルゴリズムでは、

  • 左からトラバースして隣接する要素を比較すると、上位の要素が右側に配置されます。
  • このようにして、まず最大の要素を右端に移動させます。
  • このプロセスは、データがソートされるまで、2 番目に大きいものを見つけて配置するという作業を続けます。
バブルソートのおすすめ練習方法 試してみましょう！

バブルソートはどのように機能しますか?

次の図を参考に、バブル ソートの仕組みを理解してみましょう。



Android携帯電話のiPhone絵文字

入力： arr[] = {6, 0, 3, 5}

最初のパス:

最大の要素が正しい位置、つまり配列の最後に配置されます。

バブルソートアルゴリズム: 最大の要素を正しい位置に配置

2 番目のパス:

2 番目に大きい要素を正しい位置に配置します

バブルソートアルゴリズム: 2番目に大きい要素を正しい位置に配置

3回目のパス:

残りの 2 つの要素を正しい位置に配置します。

左結合と右結合

バブルソートアルゴリズム: 残りの要素を正しい位置に配置

  • 総数パスの数: n-1
  • 総数比較の結果: n*(n-1)/2

バブルソートの実装

以下はバブルソートの実装です。内部ループでスワップが発生しなかった場合は、アルゴリズムを停止することで最適化できます。

C++ 
// Optimized implementation of Bubble sort #include  using namespace std; // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {  int i, j;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(arr[j], arr[j + 1]);  交換 = true;  // 内側のループによって 2 つの要素が交換されなかった場合、 // Break if (swapped == false) Break;  } } // 配列を出力する関数 void printArray(int arr[], int size) { int i;  for (i = 0; i< size; i++)  cout << ' ' << arr[i]; } // Driver program to test above functions int main() {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int N = sizeof(arr) / sizeof(arr[0]);  bubbleSort(arr, N);  cout << 'Sorted array: 
';  printArray(arr, N);  return 0; } // This code is contributed by shivanisinghss2110>
C 
// Optimized implementation of Bubble sort #include  #include  void swap(int* xp, int* yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {  int i, j;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]);  交換 = true;  } } // 内側のループによって 2 つの要素が交換されなかった場合、 // Break if (swapped == false) Break;  } } // 配列を出力する関数 void printArray(int arr[], int size) { int i;  for (i = 0; i< size; i++)  printf('%d ', arr[i]); } // Driver program to test above functions int main() {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int n = sizeof(arr) / sizeof(arr[0]);  bubbleSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>
ジャワ 
// Optimized java implementation of Bubble sort import java.io.*; class GFG {    // An optimized version of Bubble Sort  static void bubbleSort(int arr[], int n)  {  int i, j, temp;  boolean swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { // arr[j] と arr[j+1] を入れ替えます temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = 温度;  交換 = true;  // 内側のループによって 2 つの要素が交換されなかった場合、 // Break if (swapped == false) Break;  } } // 配列を出力する関数 static void printArray(int arr[], int size) { int i;  for (i = 0; i< size; i++)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver program  public static void main(String args[])  {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int n = arr.length;  bubbleSort(arr, n);  System.out.println('Sorted array: ');  printArray(arr, n);  } } // This code is contributed // by Nikita Tiwari.>
Python3 
# Optimized Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): swapped = False # Last i elements are already in place for j in range(0, n-i-1): # Traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if (swapped == False): Break # 上記をテストするドライバーコード if __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('ソートされた配列:') for i in range(len(arr)): print('%d' % arr[i], end=' ') # このコードは Suraj krushna Yadav によって変更されています>>
C# 
// Optimized C# implementation of Bubble sort using System; class GFG {  // An optimized version of Bubble Sort  static void bubbleSort(int[] arr, int n)  {  int i, j, temp;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { // arr[j] と arr[j+1] を入れ替えます temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = 温度;  交換 = true;  // 2 つの要素が内部ループによって交換されなかった場合、 // Break if (swapped == false) Break;  } } // 配列を出力する関数 static void printArray(int[] arr, int size) { int i;  for (i = 0; i< size; i++)  Console.Write(arr[i] + ' ');  Console.WriteLine();  }  // Driver method  public static void Main()  {  int[] arr = { 64, 34, 25, 12, 22, 11, 90 };  int n = arr.Length;  bubbleSort(arr, n);  Console.WriteLine('Sorted array:');  printArray(arr, n);  } } // This code is contributed by Sam007>
JavaScript 
// Optimized javaScript implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(arr, n) {  var i, j, temp;  var swapped;  for (i = 0; i < n - 1; i++)   {  swapped = false;  for (j = 0; j < n - i - 1; j++)   {  if (arr[j]>arr[j + 1]) { // arr[j] と arr[j+1] を入れ替えます temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = 温度;  交換 = true;  } } // 2 つの要素が内部ループによって交換されなかった場合、 // Break if (swapped == false) Break;  } } // 配列を出力する関数 function printArray(arr, size) { var i;  for (i = 0; i< size; i++)  console.log(arr[i] + ' '); } // Driver program var arr = [ 64, 34, 25, 12, 22, 11, 90 ]; var n = arr.length; bubbleSort(arr, n); console.log('Sorted array: '); printArray(arr, n); // This code is contributed shivanisinghss2110>
PHP 
 // PHP Optimized implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // Traverse the array from 0 to // n-i-1. Swap if the element  // found is greater than the // next element if ($arr[$j]>$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $swapped = True; // 内側のループによって 2 つの要素が交換されなかった場合、 // Break if ($swapped == False) Break; } } // ドライバーコード $arr = array(64, 34, 25, 12, 22, 11, 90); $len = sizeof($arr);バブルソート($arr); echo 'ソートされた配列: 
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>>>
出力 
Sorted array: 11 12 22 25 34 64 90>

バブルソートの複雑さの分析 :

時間計算量: の上2)
補助スペース: ○(1)

バブルソートの利点:

  • バブルソートは理解しやすく、実装も簡単です。
  • 追加のメモリ空間は必要ありません。
  • これは安定した並べ替えアルゴリズムであり、同じキー値を持つ要素が並べ替えられた出力内で相対的な順序を維持することを意味します。

バブルソートの欠点:

  • バブルソートの時間計算量は O(N2) そのため、大規模なデータセットの場合は非常に遅くなります。
  • バブル ソートは比較ベースの並べ替えアルゴリズムです。つまり、入力データ セット内の要素の相対的な順序を決定するために比較演算子が必要です。場合によっては、アルゴリズムの効率が制限される可能性があります。

バブル ソートに関連するいくつかの FAQ:

バブルソートの境界ケースとは何ですか?

要素がすでにソートされている場合、バブルソートには最小の時間 (n の順序) がかかります。したがって、O(N を避けるために、配列がすでにソートされているかどうかを事前に確認することが最善です。2) 時間の複雑さ。

バブルソートではソートが行われますか?

はい、バブル ソートは、主要なデータ構造を使用せずに、隣接するペアの交換を実行します。したがって、バブル ソート アルゴリズムはインプレース アルゴリズムです。

C++プロトタイプ関数

バブルソートアルゴリズムは安定していますか?

はい、バブル ソート アルゴリズムは安定しています。

バブルソートアルゴリズムはどこで使用されていますか?

バブル ソートはその単純さのため、ソート アルゴリズムの概念を導入するためによく使用されます。コンピューター グラフィックスでは、ほぼソートされた配列内の小さなエラー (わずか 2 つの要素の交換など) を検出し、線形計算量 (2n) だけで修正できる機能が人気です。

例: ポリゴン塗りつぶしアルゴリズムで使用されます。このアルゴリズムでは、境界線が特定の走査線 (x 軸に平行な線) の x 座標によって並べ替えられ、y を増加させると順序が変更されます (2 つの要素が交換されます)。 2本の線の交点。

関連記事：

  • 再帰的バブルソート
  • ソートのためのコーディングの練習
  • バブルソートに関するクイズ
  • バブルソートの複雑さの分析