初めに・・・
シェルソートが分からない・・・。
でも某競技プログラミングをやる上で必要になってくるだろうアルゴリズムだし・・・。
今回はそんなことを思ってググりながらふらふらしてる方向けの記事です。(自分含め)
ではやっていきます。
配列をテキトーに用意しましょう。
今回は・・・100個のint型の配列でいっか。
100個を個々に設定していくのはだるいので、ランダムに決めてもらいましょう。
ランダムに0~100までの数字をJavaくんに考えてもらいます。
public static void main(String[] args) {
Random r = new Random();
int [] nums = new int[100];
for (int i = 0; i < nums.length; i++) {
nums[i] = r.nextInt(100);
}
現段階で出力してみましょう。
↓のコードをペッと貼り付けたら出力されます。
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
次に、シェルソートを考えていきます。
staticメソッドにシェルソートを記述します。これによって、呼び出すだけでソートが完了している！！！という状態させ.....たいですね。そのために準備をします。
今回は、10ブロック単位で一旦ソートをかけ、次に2ブロック単位でソートをかける2段構えにします。(なお、これによるメリットは不明。メリット究明中。現在動くことを優先します・・・。)
まず、Mainメソッドの中にこいつを記述。
int[] sortBox = {9, 1};//10ブロック単位、2ブロック単位でソートやるお('ω')
insertion(nums, nums.length, sortBox, sortBox.Length);
↑で、自分も9と1じゃねえか！！！と思っていました。
ですが、配列を考えるとき、Javaでは配列は0から始まりますよね？
1と書いても0番目の配列、1番目の配列の2個考慮して入れ替え・・・とかになりますよね？そういうことです。
メインメソッドの外、いわゆるクラスに不随するstaticメソッドを書きたいので、howToSortクラスの下あたりにでも↓を書きましょうか。
insertionでシェルソートを呼び出して、その後にシェルソートをさせる感じ。
static void insertion(int[] nums, int numsLength, int[] sortBox, int sortBoxLength) {
for(int i = 0; i < sortBoxLength; i++){
shellsort(nums, numsLength, sortBox[i]);
}
}
読みにくいですが、insertionには配列①と①の長さ、ソート用のメモ書きみたいな配列②と②の長さを渡しています。シェルソートに渡していくのは、①の整列したい配列、①の長さ、あとはどれだけのブロック単位でやっていくか(今回は10ブロック単位か2ブロック単位)、です。
次に、肝心なシェルソート中身を考えます。手っ取り早く、まずはコードをどうぞ。
static void shallSort(int[] nums, int numsLength, int sortNum) {
for (int i = sortNum; i < numsLength; i++) {
int tmp = nums[i]; //一時保存
int j = i - sortNum;//0~90
while (j >= 0 && nums[j] > tmp) { //j 0以上、nums値が一時保存より大きい間
nums[j + sortNum] = nums[j];//9単位、1ずつ
j -= sortNum;//j に〇単位ずつ・・・のやつを減算。
}
nums[j + sortNum] = tmp;//抜けたらtmpに保存されてたやつをjの最小値に代入。
}
for文はまず、10単位でソートかけたいので9スタート(配列で言う0から見て10個目)。そこから99番目の配列までブン回します。
tmp は一時保存のための変数。一旦、配列の9番目(10個目)を退避。
iから9を引いて、それをjに保存。numsの長さまでするので変動域は90まで。
while文はjが0以上の時かつ、nums[j]が一時保存より大きい場合回ります。
9番目(一時保存)と0番目(j)を比較してずらす。
jから9を引いて、0以下になる、もしくはソートが完了していればwhile文が抜けます。
while文が抜けたらtmpに保存されているjの最小値をnums[j+sortNum]に代入。
そうするとアラ不思議！ソートが済んでいますとさ！
ソース全体は以下の通り。
public class HowToSort {
public static void main(String[] args) {
Random r = new Random();
int [] nums = new int[100];
for (int i = 0; i < nums.length; i++) {
nums[i] = r.nextInt(100);
}
//ソート前表示。
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
//改行
System.out.println();
int[] sortBox = {9,1};
insertion(nums, nums.length, sortBox, sortBox.length);
//ソート後表示。
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
}
private static void insertion(int[] nums, int numsLength, int[] sortBox, int sortBoxLength) {
for (int i = 0; i < sortBoxLength; i++) {
shallSort(nums, numsLength, sortBox[i]);
}
}
private static void shallSort(int[] nums, int numsLength, int sortNum) {
for (int i = sortNum; i < numsLength; i++) {
int tmp = nums[i];
int j = i - sortNum;
while (j >= 0 && nums[j] > tmp) {
nums[j + sortNum] = nums[j];
j -= sortNum;
}
nums[j + sortNum] = tmp;
}
}
}
やってみた感想
うーん・・・わからん！！！
という思いがあふれ出る中に、ミリぐらいわかった気持ちになれた気がします。
じゃあなぜそうなるのか、といった話は長くなるのでまた今度考えるとして、書き方や必要な情報はわかってきました。
他の方のシェルソートのソースを見てる限り、省略できる部分もあるような気がするのでいろいろな記事を見てこれからも学習していこうと思います。