Various Sorting Methods by CCM, a Computational Model Based on Production Rules and Local Evaluation Functions
Kanada, Y., SIG Notes on Symbol Processing, Information Processing Society of Japan, 93-SYM-71-5, pp. 33-40, 1993, Published by IPSJ
[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]
[ Sort and N queens problem demo in Java (Only one type of sorting) ]
Abstract: The author has proposed the Chemical Casting Model (CCM), which is a stochastic computation model whose elements are production rules and evaluation functions that are computed only using local information, and has proposed a computation language SOOC based on CCM. This model is targeted to apply to problems on open systems in which even specifications cannot be clearly written down. However, it is also important to make experiment on applying this model to conventional problems. Thus, CCM is applied to sorting in this paper, and a new sorting method is presented and several sorting methods based on conventional methods, i.e., insertion sort and exchange sort, are presented. The results of experiments are also shown. By these methods, sorting can be done only using one production rule and one evaluation function both of which only refer to local information. Several interesting phenomena caused by computation only using local information are also mentioned.
Introduction to this research theme: CCM: Chemical-Computation Model