基本情報対策：科目B「挿入ソート」

科目Bの問題を解いている時にトレースミスが多く、その原因としてそもそもを知らない、理解していない状態だったため、トレースミスをした問題をコードに起こして紐解いていくことにしました。平日は毎日投稿を目指します。

挿入ソートとは

基本挿入法アルゴリズムの一つ

以下の場合に導入を検討する
①データセットが小さい場合:
挿入ソートは、データセットの要素数が比較的小さい場合に効果的です。データセットが少ない場合、挿入ソートの実行時間は他の高度なソートアルゴリズムよりも短くなる傾向があります。

②部分的にソートされたデータが存在する場合:
すでにソートされている範囲に新たな要素を挿入するため、部分的にソートされたデータに対しては高い効率を発揮します。

③データセットがほぼソートされている場合:
ほぼソートされたデータでは、挿入ソートは比較回数を最小限に抑えながらソートを行うことができます。

ただし、データセットが非常に大きい場合やランダムな順序で並んでいる場合には、挿入ソートは効率的ではありません。そのような場合には、マージソートやクイックソートなどの高速なソートアルゴリズムが一般的に選択されます。

投稿①　「挿入ソート」

Main.java

import java.util.Arrays;

public class Main {
    public static int[] intoSortMachine(int[] array){
        int tmp;
        int j;
        for(int i =1; i<array.length; i++){
            tmp = array[i]; //<= 比較対象を格納する
            j = i;  // <= iは直接操作できないため　jで代用してデクリメントを行う

            while( j > 0 && array[j-1] > tmp ){
//                ↑　Jが0より大きいすなわち配列要素からはみ出ない事
//                　　　　　　　　↑前の配列要素より小さい時に条件が成立する。

//              ソート処理
                array[j] = array[j-1];  //tmpより大きい要素を後ろに移動する
                j--;                    //Jの値を-1してさらに前の要素と比較を行う
            }

            array[j] = tmp;       //場所が確定した時、配列要素を格納する
            System.out.println(Arrays.toString(array));

        }
        return array;
    }
}

MainTest.java

import org.junit.Test;


import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

public class MainTest {
    @Test
    public void testIntoSortMachine() {
        // テスト用のデータ
        int[] array = {5,1,4,3,2};
        // 期待される結果
        int[] expected = {1,2,3,4,5};
        // テスト対象のメソッドを実行
        int[] sortedArray = Main.intoSortMachine(array);
        // 期待される結果と実際の結果を比較
        assertArrayEquals(expected, sortedArray);

//  [1, 5, 4, 3, 2]
//  [1, 4, 5, 3, 2]
//  [1, 3, 4, 5, 2]
//  [1, 2, 3, 4, 5]
//  １つの値を前に持っていく作業をしているだけ。
    }
}

蓋を開けてみたらシンプルでした。

ポイント①
変数jは 変数iを格納するのですが、ここで格納する理由は変数iを直接操作することができない為、代わりに変数jに担当してもらっていたことが理解できました。

for(int i =1; i<array.length; i++){
            tmp = array[i]; //<= 比較対象を格納する
            j = i;  // <= iは直接操作できないため　jで代用してデクリメントを行う

ポイント②
疑似言語で見た時、内容が理解できずトレースができなかった箇所。ここも紐解いてみたら意外とシンプルでした。

   while( j > 0 && array[j-1] > tmp ){
//         ↑　Jが0より大きいすなわち配列要素からはみ出ない事
//                ↑前の配列要素より小さい時に条件が成立する。

ポイント③
ソートの処理をここで実施している。

array[j] = array[j-1]; 
//tmpより大きい要素を後ろに移動する
    j--;                   
//Jの値を-1してさらに前の要素と比較を行う

あとは繰り返し条件を抜けたら終了した配列番号に格納する

array[j] = tmp;       
//場所が確定した時、配列要素を格納する

これを繰り返したのち、ソートが完了する

// テスト用のデータ
int[] array = {5,1,4,3,2};　
//実行結果
//  [1, 5, 4, 3, 2]
//  [1, 4, 5, 3, 2]
//  [1, 3, 4, 5, 2]
//  [1, 2, 3, 4, 5]
//  １つの値を前に持っていく作業をしているだけ。

だれかの参考になればうれしいです^^