@Liberty
Posted at

Javaでバブルソート

Javaアルゴリズム
More than 5 years have passed since last update.

帰ってきてからなんかやろうと思っても纏まった時間が取れないため、

そんな時はアルゴリズムを解いていきます。

１日１個、半年もやれば１８０個です。

地道にやっていきます。

AOJのように予め課題が用意されていると取っ付きやすいですね。

そんな訳で今回は


バブルソート

簡単に言うと、ある配列の末尾と末尾−１の数を比較しソートしていくアルゴリズムです。

そんなに補足は必要ないと思いますが一応例を書くと

例

* 配列 6 4 5 3 1 2

並び替えの順序は

* 6 4 5 3 1 2 // 1 < 2なので何もしない

* 6 4 5 1 3 2 // 3 < 1なので入れ替え

* 6 4 1 5 3 2 // 5 < 1なので入れ替え

* 6 1 4 5 3 2 // 4 < 1なので入れ替え

* 1 6 4 5 3 2 // 6 < 1なので入れ替え

* 1 6 4 5 2 3 // また末尾の数値を比較し、 3 > 2なので入れ替え

・・・省略 

package aoj.sort;



import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;



public class BubbleSort {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 問題を解く為に入力を受けているだけなので無視してください。

        int elementNum = Integer.parseInt(br.readLine());

        String line = br.readLine();

        int[] numArray = parseInt(getSplitLine(line));



                // ここからバブルソート

        int count = 0;

        for (int i = 0; i < numArray.length - 1; i++) {

            for (int j = numArray.length - 1; j > i; j--) {

                if (numArray[j - 1] > numArray[j]) {

                    int tmpNum = numArray[j - 1];

                    numArray[j - 1] = numArray[j];

                    numArray[j] = tmpNum;

                    count++;

                }

            }

        }

        System.out.println(Arrays.toString(numArray)

                .replaceAll("[\\[\\],]", ""));

        System.out.println(count);

    }



    private static String[] getSplitLine(String line) {

        return line.split("\\s");

    }



    private static int[] parseInt(String[] line) {

        int[] numArray = new int[line.length];

        for (int i = 0; i < line.length; i++) {

            numArray[i] = Integer.parseInt(line[i]);

        }

        return numArray;

    }



}

バブルソートは

データの総数を num とすると、比較回数は　num(num-1)/2　回。

になるようです。

流石にもう少し難しいものに手を出したいですが、ペースを崩さず

基本をしっかり思い出しましょう。。。

土日はScalaでBDDでも書きたいと思います。

Edit request
7