新年のご挨拶とマージソート

ご挨拶

もう新年を迎えて2週間も経ってしまいましたが、新年あけまして、おめでたくないですが、皆様にとって良い一年になりますように。

当ブログは去年の末におかげさまで閲覧数が10000を超えました。一般的なブログの閲覧数とは雲泥の差ではありますが、なんとなく嬉しいです。今後もバタバタしながらも、時間を見つけて記事を書いていこうと思います。

新年早々に感染爆発・緊急事態宣言とえげつない状況となってしまいましたが、我々ができることは手洗い、うがい、目洗い、マスク、自粛のみ。それ以外はどうしようもできないことなので、自分でできることは全てやって、だめならだめでしょうがない、という気持ちで生きていきましょう。

今年もどうぞよろしくお願いいたします。

Nim版マージソート

Nimのalgorithmモジュールのsortがそもそもマージソートで実装されているらしいので、このプログラムは全く無意味なような気がしますが、私の勉強になるので書きました。ちなみにこのプログラムにそのalgorithmモジュールをインポートしているのですが、fill関数を使うためだけにインポートしています。これはtempという配列をMAX_DATA個の0で満たすために使っています。


import algorithm

const MAX_DATA: int = 7

proc mergeSort(arr: var array[MAX_DATA, int],
               temp: var array[MAX_DATA, int], l: int, r: int) =
  
  if l >= r:
    return

  var
    mid: int = (l + r) div 2
    i: int
    j: int

  mergeSort(arr, temp, l, mid)
  mergeSort(arr, temp, mid + 1, r)

  for i in l..mid:
    temp[i] = arr[i]

  j = r
  for i in (mid + 1)..r:
    temp[i] = arr[j]
    dec(j)

  i = l
  j = r
  for k in l..r:
    if temp[i] <= temp[j]:
      arr[k] = temp[i]
      inc(i)
    else:
      arr[k] = temp[j]
      dec(j)

  return

proc main() =
  var
    arr: array[MAX_DATA, int] = [5,4,6,2,7,1,3]
    temp: array[MAX_DATA, int]
    l: int = 0
    r: int = MAX_DATA - 1

  temp.fill(0)

  mergeSort(arr, temp, l, r)
  echo arr

when isMainModule:
  main()

ひさびさにNimを使った気がします。

Rust版マージソート

Rustのsort関数もソースコードを見てみると、マージソートで実装されているようですが、Nimと同様勉強のために……


const MAX_DATA: usize = 10;

fn merge_sort(
    arr: &mut [i32],
    temp: &mut [i32],
    l: &mut usize,
    r: &mut usize)
{
    if l >= r { return; }

    let mut mid: usize = (*l + *r) / 2;
    let mut mid_tmp: usize = mid + 1;

    merge_sort(arr, temp, l, &mut mid);
    merge_sort(arr, temp, &mut mid_tmp, r);

    for i in *l..=mid {
        temp[i] = arr[i];
    }

    let mut j: usize = *r;
    
    for i in mid_tmp..=*r {
        temp[i] = arr[j];
        j -= 1;
    }

    let mut i: usize = *l;
    let mut j: usize = *r;

    for k in *l..=*r {
        if temp[i] <= temp[j] {
            arr[k] = temp[i];
            i += 1;
        } else {
            arr[k] = temp[j];
            j -= 1;
        }
    }
}

fn main() {
    let mut arr: [i32; MAX_DATA] = [3,6,1,7,2,0,4,5,9,8];
    let mut temp: [i32; 10] = [0; 10];
    
    for i in 0..MAX_DATA {
        print!("{} ", &arr[i]);
    }
    print!("\n");
    let mut l: usize = 0;
    let mut r: usize = MAX_DATA - 1;

    merge_sort(&mut arr, &mut temp, &mut l, &mut r);

    for i in 0..MAX_DATA {
        print!("{} ", &arr[i]);
    }
    print!("\n");
}

2021/01/15