【アルゴリズム】単純交換ソート（バブルソート/bubble sort）｜基本情報技術者科目B対策

単純交換法(バブルソート)は、ソートアルゴリズムの中でも基本的なアルゴリズムです。

具体的なコードをみて、動かして体感してもらえればと思います！

ソート（整列）とは？？
単純交換ソート（バブルソート）とは？？
どんなときに使う？
単純交換ソート（バブルソート）の実装例（プログラム）
まとめ

ソート（整列）とは？？

ソートとは、複数のデータが並んだ列を、何らかの順序に基いて順番通りになるよう並べ替える(整列させる)こと。
数値を大きい順または小さい順に並べたり、文字をアルファベット順や五十音順に並べたり、日時を古い順または新しい順に並べ替えることが該当する。

また、コンピュータによるデータ処理でソート（整列）手順を定式化したアルゴリズムをソートアルゴリズムと言っています。

ソートアルゴリズムにも種類があり、場面に応じた使い分けが必要です。

＜ソートアルゴリズム例＞

・単純交換ソート（バブルソート）

・単純選択ソート

・単純挿入ソート

・クイックソート

・ヒープソート　　等

単純交換ソート（バブルソート）とは？？

単純交換ソート（バブルソート）とは、「隣り合う2つの要素の大小関係を比較・調べて、必要に応じて交換を繰り返す」という整列手順・ソートアルゴリズムのことを指します。

例えば、リストを昇順に整列させる手順の場合、下記のようになる。

先頭の要素'a'と隣り合う次の要素'b'の値を比較する。
要素'a'が要素'b'より大きい場合、要素'a'と要素'b'の値を交換する。（要素'a'が要素'b'より大きくない場合、交換は発生しない。）
先頭の要素を'b'に移動させ、要素'b'と隣り合う要素'c'の値を比較/交換する。
先頭の要素を'c','d','e'...と移動しながら比較/交換をリストの終端まで繰り返す。
対象の要素と比較した最も大きい値を持つ要素がリストの終端へ移動されている。
リストの終端には対象の要素と比較した最も大きい値が入っているため、リストの終端の位置をずらして(要素数をひとつ減らして)手順1〜5を繰り返す。

このように総当たりで比較を行い、条件に一致する交換を実行することでソート（整列）が完了される。

どんなときに使う？

単純交換ソート（バブルソート）は、総当りで比較をしており、シンプルなアルゴリズムです。

そのため、データ量が少ないときに実装されます。

ただ、シンプルであるがゆえに処理に時間がかかります。よって、ヒープソートなどのより早い処理が利用されることが多いです。

単純交換ソート（バブルソート）の実装例（プログラム）

実装例は下記です。Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう！

Online PHP/Java/C++... editor and compiler | paiza.IO

＜実装例＞

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        int[] data = {1, 4, 3, 5, 2, 6};
        
        //単純交換ソート（バブルソート）のプログラム（コメント）
        for(int i=0; i < data.length-1; i++) {
            for(int j =i+ 1; j < data.length-1; j++) {
                if(data[i] > data[j]){
                    int tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
        }  
        
        //配列を表示させるプログラム（コメント）
        for(int i = 0; i < data.length; i++) {
            System.out.println(data[i]);
        }
    }
}