マージソート（mergeSort）9種類の言語で書いてみた
何故書くか？は前前前前回書いたので、以下、即本題。 今回は、C言語によるアルゴリズム事典を参考にしたので、C言語は省くことにした。
実行環境はcoding groundというWEB上でコンパイルから実行までしてくれるサービスを使用。
本当は定義したメソッドだけ書いておきたいのだけど、後々動作確認したいと思った時にコピペで済むので前処理等も書いておいた。
JavaScript
function margeSort(arr, head, tail) {
let m = (head, tail) => {
if (head < tail) {
let mid = Math.floor((head + tail) / 2);
m(head, mid);
m(mid+1, tail);
let l = arr.slice(head, mid+1);
let r = arr.slice(mid+1, tail+1);
let i = head;
while (l.length > 0 && r.length > 0) {
if (l[0] <= r[0]) {
arr[i++] = l.shift();
} else {
arr[i++] = r.shift();
}
}
while (l.length > 0) {
arr[i++] = l.shift();
}
}
return arr;
}
m(0, arr.length-1);
return arr;
}
console.log(margeSort([148, 651, 124, 638, 567, 435, 185, 413, 35]));
PHP
function margeSort(&$arr) {
function m (&$arr, $head, $tail) {
if ($head < $tail) {
$mid = floor(($head + $tail) / 2);
m($arr, $head, $mid);
m($arr, $mid+1, $tail);
$l = array_slice($arr, $head, $mid+1 - $head);
$r = array_slice($arr, $mid+1, ($tail - $mid));
$i = $head;
while (count($l) > 0 && count($r) > 0) {
if ($l[0] <= $r[0]) {
$arr[$i++] = array_shift($l);
} else {
$arr[$i++] = array_shift($r);
}
}
while (count($l) > 0) {
$arr[$i++] = array_shift($l);
}
}
return $arr;
}
return m($arr, 0, count($arr)-1);
}
$arr = array(651, 148 , 124, 638, 567, 435, 185, 413, 841, 35);
print_r(margeSort($arr));
Perl
use POSIX qw(floor);
my @arr = (148, 651, 124, 638, 567, 435, 185, 413, 841, 35);
print join(",", &margeSort(@arr));
sub margeSort {
my ($arr) = @_;
my $m;
$m = sub {
my ($arr, $head, $tail) = @_;
if ($head < $tail) {
my $mid = floor(($head + $tail) / 2);
$m->(\@arr, $head, $mid);
$m->(\@arr, $mid + 1, $tail);
my @l = @arr[$head .. ($mid+1)];
my @r = @arr[($mid+1) .. ($tail+1)];
my $i = $head;
while ($#l > 0 && $#r > 0) {
if ($l[0] <= $r[0]) {
@arr[$i++] = shift(@l);
} else {
@arr[$i++] = shift(@r);
}
}
while ($#l > 0) {
@arr[$i++] = shift(@l);
}
}
return @arr;
};
return $m->(\@arr, 0, $#arr, $m);
}
Python
import math
def margeSort(arr):
def m(head, tail):
if head < tail:
mid = math.floor((head + tail) / 2)
m(head, mid)
m(mid + 1, tail)
l = arr[head: mid + 1]
r = arr[mid+1: tail+1]
k = head
while len(l) > 0 and len(r) > 0:
if l[0] <= r[0]:
arr[k] = l.pop(0)
else:
arr[k] = r.pop(0)
k += 1
while len(l) > 0:
arr[k] = l.pop(0)
k += 1
return arr
return m(0, len(arr)-1)
arr = [104, 865, 413, 541, 304, 354, 165, 150]
print(margeSort(arr))
Ruby
def margeSort(arr)
# 内部メソッドだが、スコープはトップレベル
def m(arr, head, tail)
if head < tail
mid = ((head + tail) / 2).floor
m(arr, head, mid)
m(arr, mid + 1, tail)
l = arr.slice(Range.new(head, mid + 1, true))
r = arr.slice(Range.new(mid + 1, tail + 1, true))
i = head
while l.size > 0 && r.size > 0 do
if l[0] <= r[0]
arr[i] = l.shift
else
arr[i] = r.shift
end
i += 1
end
while l.size > 0 do
arr[i] = l.shift
i += 1
end
end
return arr
end
return m(arr, 0, arr.size-1)
end
arr = [148, 651, 124, 638, 567, 435, 185, 413, 841, 35]
print margeSort(arr)
Go
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{148, 651, 124, 638, 567, 435, 185, 413, 841, 35};
fmt.Println(margeSort(arr));
}
func margeSort(arr []int) []int {
var m func(int, int) []int;
m = func(head int, tail int) []int {
if head < tail {
mid := int(math.Floor(float64(head + tail) / 2));
m(head, mid);
m(mid + 1, tail);
l := make([]int, len(arr[head:mid+1]), (cap(arr[head:mid+1])+1))
r := make([]int, len(arr[mid+1:tail+1]), (cap(arr[mid+1:tail+1])+1))
copy(l, arr[head:mid+1]);
copy(r, arr[mid+1:tail+1]);
i := head;
for len(l) > 0 && len(r) > 0 {
if l[0] <= r[0] {
arr[i] = l[0];
l = l[1:];
} else {
arr[i] = r[0];
r = r[1:];
}
i++;
}
for len(l) > 0 {
arr[i] = l[0];
l = l[1:];
i++;
}
}
return arr;
}
return m(0, len(arr)-1);
}
Kotlin
fun main(args: Array<String>) {
var arr = arrayOf(148, 651, 124, 638, 567, 435, 185, 413, 841, 35);
var result = margeSort(arr);
for(i in result) println(i)
}
fun margeSort(arr: Array<Int>): Array<Int> {
return m(arr, 0, arr.size-1);
}
fun m(arr: Array<Int>, head: Int, tail: Int): Array<Int> {
if (head < tail) {
var mid = Math.floor((head + tail).toDouble() / 2).toInt();
m(arr, head, mid);
m(arr, mid + 1, tail);
var l = arr.sliceArray(head..(mid));
var i = 0;
var j = mid + 1;
var k = head;
while (i < l.size && j <= tail) {
if (l[i] <= arr[j]) {
arr[k++] = l[i++];
} else {
arr[k++] = arr[j++];
}
}
while (i < l.size){
arr[k++] = l[i++];
}
}
return arr;
}
Swift
import Foundation
import Glibc
func margeSort(a: [Int]) -> [Int] {
var arr = a
func m(head: Int, tail: Int) {
if head < tail {
let mid = Int(floor(Double(head + tail) / 2))
m(head: head, tail: mid)
m(head: mid + 1, tail: tail)
var l = arr[head...mid] // インデックスは0番からではなく、headの値からとなる
var i = head
var j = mid + 1
var k = head
while i <= mid && j <= tail {
if l[i] <= arr[j] {
arr[k] = l[i]
i += 1
} else {
arr[k] = arr[j]
j += 1
}
k += 1
}
while i <= mid {
arr[k] = l[i]
i += 1
k += 1
}
}
}
m(head: 0, tail: arr.count-1)
return arr
}
print(margeSort(a: [867, 104, 413, 541, 304, 354, 165, 150]))
C#
using System.IO;
using System;
class Program
{
static void Main()
{
int[] arr = {148, 651, 124, 638, 567, 435, 185, 413, 841, 35};
Console.WriteLine(string.Join(", ", margeSort(arr)));
}
static int[] margeSort(int[] arr) {
Func<int, int, int[]> m = null;
m = (head, tail) => {
if (head < tail) {
int mid = (int)Math.Floor((double)(head + tail) / 2);
m(head, mid);
m(mid + 1, tail);
int[] l = new int[mid+1-head];
Array.Copy(arr, head, l, 0, mid+1-head);
int i = 0;
int j = mid + 1;
int k = head;
while (i < l.Length && j <= tail) {
if (l[i] <= arr[j]) {
arr[k++] = l[i++];
} else {
arr[k++] = arr[j++];
}
}
while (i < l.Length) {
arr[k++] = l[i++];
}
}
return arr;
};
m(0, arr.Length-1);
return arr;
}
}
