ソート（並べ替え）③: バブルソート

バブルソートの定義

データ列の隣り合う（となりあう）要素を比較し交換することを繰り返すことによりデータ列をソート

• バブルとは「泡（あわ）」の意味で、ソートの過程でデータが移動する様子が、水中で泡が浮かんでいくように見えることからこの名前がついています。

左の要素と比較し、左の方が大きければ交換する

---

バブルソートのPseudo Code

bubble_sort(A : 配列, n : Aの要素数)
    for i = 0 to n-2
        for j = n-1 down to i+1
            if a[j-1] > a[j] then
                swap(a[j-1], a[j])

 

---

バブルソートの時間複雑度

 O(n^2) 

 

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
        
        for(int i = 0; i < n-1; i++){
            for(int j = n -1 ; j > i; j--)
            {
                if(nums[j-1] > nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
            
            Console.WriteLine(string.Join(" ", nums));
        }
    }
}