クイックソート（quickSort）を9種類の言語で書いてみた
何故書くか？はこのエントリー書いたので、以下、即本題。 今回は、C言語によるアルゴリズム事典を参考にしたので、C言語は省くことにした。
実行環境はcoding groundというWEB上でコンパイルから実行までしてくれるサービスを使用。
本当は定義したメソッドだけ書いておきたいのだけど、後々動作確認したいと思った時にコピペで済むので前処理等も書いておいた。
JavaScript
function quickSort(arr) {
let q = (head, tail) => {
let i = head;
let j = tail;
let pivot = arr[Math.floor((head + tail) / 2)];
let tmp;
for ( ; ; ) {
while (arr[i] < pivot) {
i++;
}
while (pivot < arr[j]) {
j--;
}
if (i >= j) {
break;
}
tmp = arr[i];
arr[i] = arr[j];
arr[j] = arr[i];
i++;
i--;
}
if (head < i - 1) {
q(head, i-1);
}
if (j + 1 < tail) {
q(j + 1, tail);
}
return arr;
}
}
console.log(quickSort([148, 651, 124, 638, 567, 435, 185, 413, 35]));
PHP
function quickSort($arr) {
function q($arr, $head, $tail) {
$i = $head;
$j = $tail;
$pivot = $arr[floor(($head + $tail) / 2)];
for ( ; ; ) {
while ($arr[$i] < $pivot) {
$i++;
}
while ($pivot < $arr[$j]) {
$j--;
}
if ($i >= $j) {
break;
}
$tmp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
$i++;
$j--;
}
if ($head < $i - 1) {
q($arr, $head, $i-1);
}
if ($j + 1 < $tail) {
q($arr, $j+1, $tail);
}
return $arr;
}
return q($arr, 0, count($arr)-1);
}
$arr = array(651, 148 , 124, 638, 567, 435, 185, 413, 841, 35);
print_r(quickSort($arr));
Perl
use POSIX qw(floor);
my @arr = (148, 651, 124, 638, 567, 435, 185, 413, 841, 353);
print join(",", &quickSort(@arr));
sub quickSort {
my ($arr) = @_;
my $q;
$q = sub {
my ($arr, $head, $tail) = @_;
my $i = $head;
my $j = $tail;
my $pivot = @arr[floor(($head + $tail) / 2)];
my $tmp;
while (1) {
while (@arr[$i] < $pivot) {
$i++;
}
while ($pivot < @arr[$j]) {
$j--;
}
if ($i >= $j) {
last;
}
$tmp = @arr[$i];
@arr[$i] = @arr[$j];
@arr[$j] = $tmp;
$i++;
$j--;
}
if ($head < $i - 1) {
$q->(\@arr, $head, $i-1);
}
if ($j + 1 < $tail) {
$q->(\@arr, $j+1, $tail);
}
return @arr;
};
return $q->(\@arr, 0, $#arr);
}
Python
import math
def quickSort(arr):
def q(head, tail):
i = head
j = tail
pivot = arr[math.floor((head + tail) / 2)]
while True:
while arr[i] < pivot:
i += 1
while pivot < arr[j]:
j -= 1
if i >= j:
break
tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
i += 1
j -= 1
if head < i - 1:
q(head, i-1)
if j + 1 < tail:
q(j+1, tail)
return arr
return q(0, len(arr)-1)
print(quickSort([104, 865, 413, 541, 304, 354, 165, 150]))
Ruby
def quickSort(arr)
# 内部メソッドだが、スコープはトップレベル
def q(arr, head, tail)
i = head
j = tail
pivot = arr[((head + tail) / 2).floor]
while true
while arr[i] < pivot
i += 1
end
while pivot < arr[j]
j -= 1
end
if i >= j
break
end
tmp = arr[i]0
arr[i] = arr[j]
arr[j] = tmp
i += 1
j -= 1
end
if head < i - 1
q(arr, head, i-1)
end
if j + 1 < tail
q(arr, j+1, tail)
end
return arr
end
return q(arr, 0, arr.size-1)
end
arr = [148, 651, 124, 638, 567, 435, 185, 413, 841, 35]
print quickSort(arr)
Go
package main
import (
"fmt"
"math"
)
func main() {
arr := []int{148, 651, 124, 638, 567, 435, 185, 413, 841, 35};
fmt.Println(quickSort(arr));
}
func quickSort(arr []int) []int {
var q func(int, int) []int;
q = func(head int, tail int) []int {
i := head;
j := tail;
pivot := arr[int(math.Floor(float64(head + tail) / 2))];
tmp := 0;
for{
for arr[i] < pivot {
i++;
}
for pivot < arr[j] {
j--;
}
if i >= j {
break;
}
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++
j--;
}
if head < i-1 {
q(head, i-1);
}
if j+1 < tail {
q(j+1, tail);
}
return arr;
}
return q(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 = quickSort(arr);
for(i in result) println(i)
}
fun quickSort(arr: Array<Int>): Array<Int> {
return q(arr, 0, arr.size-1);
}
fun q(arr: Array<Int>, head: Int, tail: Int): Array<Int> {
var i = head;
var j = tail;
var pivot = arr[Math.floor((head + tail).toDouble() / 2).toInt()];
while (true) {
while (arr[i] < pivot) {
i++;
}
while (pivot < arr[j]) {
j--;
}
if (i >= j) {
break;
}
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
if (head < i - 1){
q(arr, head, i - 1);
}
if (j + 1 < tail) {
q(arr, j + 1, tail);
}
return arr;
}
Swift
func quickSort(a: [Int]) -> [Int] {
var arr = a
func q(head: Int, tail: Int) -> [Int] {
var i = head
var j = tail
var pivot = arr[Int(floor(Double(head + tail) / 2))]
while true {
while arr[i] < pivot {
i += 1
}
while pivot < arr[j] {
j -= 1
}
if i >= j {
break;
}
var tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
i += 1
j -= 1
}
if head < i - 1 {
q(head: head, tail: i-1)
}
if j + 1 < tail {
q(head: j+1, tail: tail)
}
return arr
}
return q(head: 0, tail: arr.count-1)
}
print(quickSort(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(", ", quickSort(arr)));
}
static int[] quickSort(int[] arr) {
Func<int, int, int[]> q = null;
q = (head, tail) => {
int i = head;
int j = tail;
int pivot = arr[(int)Math.Floor((double)(head + tail) / 2)];
for ( ; ; ) {
while (arr[i] < pivot) {
i++;
}
while (pivot < arr[j]) {
j--;
}
if (i >= j) {
break;
}
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
if(head < i - 1) {
q(head, i - 1);
}
if (j + 1 < tail) {
q(j + 1, tail);
}
return arr;
};
q(0, arr.Length-1);
return arr;
}
}
