その仕組みを知っている現在、ふと、自分でコードを書いてみようと思った。書き終わったあと wiki などに掲載されたいるコードと比較してみると、若干無駄があることに気づいた。また、データを分割する際の中央値の選び方が、大事であることも改めて認識することとなった。
１．perl でクイックソート
#! /usr/bin/perl
for($i=0;$i<100000;$i++) {
push(@LIST,100000-$i);
}
#&pr();
&qsort(\@LIST,0,scalar(@LIST)-1);
#&pr();
sub mid3 {
my($x,$y,$z) = @_;
if ($x < $y) {
if ($y < $z) {return($y);} elsif ($z < $x) {return($x);} else {return($z);}
}
else {
if ($z < $y) {return($y);} elsif ($x < $z) {return($x);} else {return($z);}
}
}
sub qsort {
my($LIST,$s,$e) =@_;
# my($target) = $$LIST[$s];
my($target) = $$LIST[$s + int(($e-$s)/2)];
# my($target) = &mid3($$LIST[$s],$$LIST[int($s + ($e - $s)/2)],$$LIST[$e]);
my($sp) = $s;
my($ep) = $e;
while(1) {
while($$LIST[$sp]<$target && ($sp+1)<$ep) {
$sp++;
}
while($$LIST[$ep]>=$target && ($sp+1)<$ep) {
$ep--;
}
if ($$LIST[$sp]>$$LIST[$ep]) {
my($tmp) = $$LIST[$ep];
$$LIST[$ep] = $$LIST[$sp];
$$LIST[$sp] = $tmp;
}
if (($sp+1) == $ep) {
last;
}
}
if ($sp - $s > 0) {
&qsort($LIST,$s,$sp);
}
if ($e - $ep > 0) {
&qsort($LIST,$ep,$e);
}
}
sub pr {
printf("========\n");
foreach $no (@LIST) {
printf("%d\n",$no);
}
}
２．ruby でクイックソート
#! /usr/bin/ruby
def pr(list)
printf("======================\n")
list.each do |no|
printf("%d\n", no)
end
end
def mid3(x,y,z)
if (x < y) then
if (y < z) then return(y) elsif (z < x) then return(x) else return(z) end
else
if (z < y) then return(y) elsif (x < z) then return(x) else return(z) end
end
end
def sort(list,s,e)
# target = list[s]
target = list[s + (e-s)/2]
# target = mid3(list[s],list[s + (e-s)/2],list[e])
sp = s
ep = e
while true do
while list[sp] < target && sp+1 < ep do
sp += 1
end
while list[ep] >= target && sp+1 < ep do
ep -= 1
end
if (list[sp] > list[ep])
tmp = list[ep]
list[ep] = list[sp]
list[sp] = tmp
end
if (sp + 1 == ep)
break
end
end
if ((sp - s) > 0)
sort(list,s,sp)
end
if ((e - ep) > 0)
sort(list,ep,e)
end
end
#list = [ 10,9,8,7,6,5,4,3,2,1 ]
list = []
for no in 1..100000 do
list.push(100000-no)
end
#pr(list)
sort(list,0,list.length-1)
#pr(list)
３．python でクイックソート
#! /usr/bin/python
import sys
def pr(list):
print "============"
for no in list:
print no
def mid3(x,y,z):
if (x < y):
if (y < z):
return(y)
elif (z < x):
return(x)
else:
return(z)
else:
if (z < y):
return(y)
elif (x < z):
return(x)
else:
return(z)
def sort(list,s,e):
# target = list[s]
target = list[s+(e-s)/2]
# target = mid3(list[s],list[s + (e-s)/2],list[e])
sp = s
ep = e
while 1:
while list[sp] < target and sp + 1 < ep:
sp += 1
while list[ep] >= target and sp + 1 < ep:
ep -= 1
if list[sp] > list[ep]:
tmp = list[ep]
list[ep] = list[sp]
list[sp] = tmp
if sp + 1 == ep:
break
if sp - s > 0:
sort(list,s,sp)
if e - ep > 0:
sort(list,ep,e)
#list = [ 10,9,8,7,6,5,4,3,2,1 ]
list = []
for no in range(0, 100000):
list.append(100000-no)
#pr(list)
#sys.setrecursionlimit(10000)
sort(list,0,len(list)-1)
#pr(list)
４．lisp でクイックソート
#! /usr/bin/clisp
(defun pr(list max)
(format t "============~%")
(dotimes (no max)
(format t "~A~%" (aref list no))))
(defun mid3(x y z)
(if (< x y)
(cond
((< y z) y)
((< z x) x)
(t z))
(cond
((< z y) y)
((< x z) x)
(t z))))
(defun mysort(list s e)
;; (setq target (elt list s))
(setq target (aref list (+ s (floor (/ (- e s) 2)))))
;; (setq target (mid3 (aref list s) (aref list (+ s (floor (/ (- e s) 2)))) (aref list e)))
(setq sp s)
(setq ep e)
(loop
(loop
(if (and (< (aref list sp) target) (< (+ sp 1) ep))
(setq sp (+ sp 1))
(return)))
(loop
(if (and (>= (aref list ep) target) (< (+ sp 1) ep))
(setq ep (- ep 1))
(return)))
(if (> (aref list sp) (aref list ep))
(progn
(setf tmp (aref list ep))
(setf (aref list ep) (aref list sp))
(setf (aref list sp) tmp)))
(if (= (+ sp 1) ep)
(progn
(return))))
(if (> (- sp s) 0)
(progn
(mysort list s sp)))
(if (> (- e ep) 0)
(progn
(mysort list ep e))))
(setq max 100000)
(setq list (make-array max))
(dotimes (no max)
(setf (aref list no) (- max no)))
;;(pr list max)
(mysort list 0 (- (length list) 1))
;;(pr list max)
５．java でクイックソート
import java.io.*;
import java.util.*;
class sort {
void pr(List<Integer>list) {
System.out.printf("======\n");
for(int no:list) {
System.out.printf("%d\n",no);
}
}
int mid3(int x, int y, int z) {
if (x < y) {
if (y < z) return y; else if (z < x) return x; else return z;
} else {
if (z < y) return y; else if (x < z) return x; else return z;
}
}
void sort(List<Integer>list,int s,int e) {
// int target = list.get(s);o
int target = list.get(s+(e-s)/2);
// int target = mid3(list.get(s),list.get(s + (e-s)/2),list.get(e));
int sp = s;
int ep = e;
while(true) {
while(list.get(sp) < target && sp + 1 < ep) {
sp++;
}
while(list.get(ep) >= target && sp + 1 < ep) {
ep--;
}
if (list.get(sp) > list.get(ep)) {
int tmp = list.get(ep);
list.set(ep,list.get(sp));
list.set(sp,tmp);
}
if (sp + 1 == ep) {
break;
}
}
if (sp - s > 0) {
sort(list,s,sp);
}
if (e - ep > 0) {
sort(list,ep,e);
}
}
public static void main(String args[]) {
List<Integer>list = new ArrayList<Integer>();
for(int i=0;i<100000;i++) {
list.add(100000-i);
}
sort obj = new sort();
// obj.pr(list);
obj.sort(list,0,list.size()-1);
// obj.pr(list);
}
}
６．C でクイックソート
#include <stdio.h>
#include <stdlib.h>
void
pr(int *list,int max)
{
int i = 0;
printf("========\n");
for(i=0;i<max;i++) {
printf("%d\n",list[i]);
}
}
int
mid3(int x, int y, int z) {
if (x < y) {
if (y < z) return y; else if (z < x) return x; else return z;
} else {
if (z < y) return y; else if (x < z) return x; else return z;
}
}
void
sort(int *list,int s,int e)
{
// int target = list[s];
int target = list[s+(e-s)/2];
// int target = mid3(list[s], list[s + (e - s) / 2], list[e]);
int sp = s;
int ep = e;
while(1) {
while(list[sp]<target && sp+1 < ep) {
sp++;
}
while(list[ep]>=target && sp+1 < ep) {
ep--;
}
if (list[sp]>list[ep]) {
int tmp = list[ep];
list[ep] = list[sp];
list[sp] = tmp;
}
if (sp + 1 == ep) break;
}
if(sp - s > 0) {
sort(list,s,sp);
}
if(e - ep > 0) {
sort(list,ep,e);
}
}
int
main(int argc,char *argv[])
{
int max = 100000;
int i = 0;
int *list = calloc(sizeof(int),max);
for(i=0;i<max;i++) {
list[i] = max - i;
}
// pr(list,max);
sort(list,0,max-1);
// pr(list,max);
}
７．速度比較
=== perl === real 0m0.408s user 0m0.384s sys 0m0.004s === ruby === real 0m0.201s user 0m0.192s sys 0m0.008s === python === real 0m0.301s user 0m0.296s sys 0m0.004s === clisp === real 0m4.362s user 0m4.200s sys 0m0.152s === java === real 0m0.288s user 0m0.396s sys 0m0.048s === C === real 0m0.014s user 0m0.012s sys 0m0.000s
