Java で シェルソート[Shell Sort]

はじめに

最近プログラミングテストにハマっていて，ソートの問題があったのですが，
シェルソートに出会ったことがなかったので，まとめます．

シェルソート

シェルソートは挿入ソートが改良されたアルゴリズムです．
挿入ソートでは，隣合う要素同士で比較・交換が行われますが，シェルソートはn個ずつ離れた要素同士で比較・交換を行います．
n個離れた要素を整列する処理をn-ソートと言います．
シェルソートはnの値を段々と小さくして行き，最終的に n=1 となるまで比較・交換を繰り返します． n=1 となった時はほとんど整列が行われている状態で挿入ソートが行われるので，整列が可能となります．

コード

今回は n = 4 とします．

Main.java

import java.util.*;
import java.io.*;


public class Main {
    // Main
    public static void main(String[] args) throws Exception {
        int[] numbers = new int[100];
        Random rand = new Random();

        // ソート前の表示
        System.out.println("ソート前");
        for(int i = 0; i < numbers.length; i++) {
            numbers[i] = rand.nextInt(5);
            System.out.print(numbers[i] + " ");
        }
        
        shellSort(numbers); // シェルソートの実行
        
        // ソート後の表示
        System.out.println("\nソート後");
        for(int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
    }
    
    // シェルソート
    public static void shellSort(int[] numbers) throws Exception {
        int n = 4; // n-ソート
        int tmp; // 配列交換で一時的に保存する領域
        while (n > 0) {
            for (int i = 0; i < numbers.length; i++) {
                int j = i;
                tmp = numbers[i]; // 入れ替え元の配列の中身の保存
                // n-ソートを行う為にindex番号を進める また n個前の配列と比較して交換の必要があったら交換する．
                while ((j >= n) && (numbers[j-n] > tmp)) {
                    numbers[j] = numbers[j - n];
                    j = j - n; // n個 ずつ確認をするための処理
                }
                numbers[j] = tmp; // 最後に更新された配列の中身に，入れ替え元を入れる．
            }
            n -= 1; // n の更新
         }
    }
}

入力

171 269 25 57 57 18 291 273 14 118 292 170 90 129 162 203 233 121 267 81 246 33 259 165 154 104 27 94 57 167 287 260 288 133 165 9 92 105 122 199 195 199 111 195 161 100 193 4 188 140 109 101 1 78 244 205 263 127 22 69 258 293 270 99 191 219 182 150 99 13 293 102 134 110 288 47 9 294 85 91 299 87 79 232 117 168 10 245 293 47 154 119 170 96 232 48 259 103 185 264 

出力

1 4 9 9 10 13 14 18 22 25 27 33 47 47 48 57 57 57 69 78 79 81 85 87 90 91 92 94 96 99 99 100 101 102 103 104 105 109 110 111 117 118 119 121 122 127 129 133 134 140 150 154 154 161 162 165 165 167 168 170 170 171 182 185 188 191 193 195 195 199 199 203 205 219 232 232 233 244 245 246 258 259 259 260 263 264 267 269 270 273 287 288 288 291 292 293 293 293 294 299

終わりに

n によって処理速度は変わりますが，以上のコードでソートはできていそうです．
テストは行っていないので，行い次第更新したいと思います！！！