2017年6月12日月曜日

クイックソートをコーディング

Basic からC言語に移り始めた頃、quick sort に出会い、その速さとシンプルな構造に感動したものである。真のプログラマとはこのようなコードを意図も簡単に次々と書かなければいけないのかと思い、プログラマには絶対になれないと思ったりもした。しかし、その後、職業でであうコードでこのようなコードにであうことはなかった。



その仕組みを知っている現在、ふと、自分でコードを書いてみようと思った。書き終わったあと 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
時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)