Journal of Formalized Mathematics
Volume 12, 2000
University of Bialystok
Copyright (c) 2000 Association of Mizar Users

Insert Sort on SCMPDS


Jing-Chao Chen
Shanghai Jiaotong University

Summary.

The goal of this article is to examine the effectiveness of ``for-loop'' and ``while-loop'' statements on SCMPDS by insert sort. In this article, first of all, we present an approach to compute the execution result of ``for-loop'' program by ``loop-invariant'', based on Hoare's axioms for program verification. Secondly, we extend the fundamental properties of the finite sequence and complex instructions of SCMPDS. Finally, we prove the correctness of the insert sort program described in the article.

This research is partially supported by the National Natural Science Foundation of China Grant No. 69873033.

MML Identifier: SCPISORT

The terminology and notation used in this paper have been introduced in the following articles [20] [5] [6] [19] [2] [16] [18] [4] [12] [7] [1] [10] [8] [9] [11] [3] [14] [13] [17] [15]

Contents (PDF format)

  1. Preliminaries
  2. Computing the Execution Result of For-Loop Program by Loop-Invariant
  3. A Program for Insert Sort
  4. The Property of Insert Sort and Its Correctness

Bibliography

[1] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.
[2] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
[3] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
[4] Grzegorz Bancerek and Andrzej Trybulec. Miscellaneous facts about functions. Journal of Formalized Mathematics, 8, 1996.
[5] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[6] Czeslaw Bylinski. The modification of a function by a function and the iteration of the composition of a function. Journal of Formalized Mathematics, 2, 1990.
[7] Jing-Chao Chen. Computation and program shift in the SCMPDS computer. Journal of Formalized Mathematics, 11, 1999.
[8] Jing-Chao Chen. Computation of two consecutive program blocks for SCMPDS. Journal of Formalized Mathematics, 11, 1999.
[9] Jing-Chao Chen. The construction and computation of conditional statements for SCMPDS. Journal of Formalized Mathematics, 11, 1999.
[10] Jing-Chao Chen. The construction and shiftability of program blocks for SCMPDS. Journal of Formalized Mathematics, 11, 1999.
[11] Jing-Chao Chen. Recursive Euclide algorithm. Journal of Formalized Mathematics, 11, 1999.
[12] Jing-Chao Chen. The SCMPDS computer and the basic semantics of its instructions. Journal of Formalized Mathematics, 11, 1999.
[13] Jing-Chao Chen. The construction and computation of while-loop programs for SCMPDS. Journal of Formalized Mathematics, 12, 2000.
[14] Jing-Chao Chen and Piotr Rudnicki. The construction and computation of for-loop programs for SCMPDS. Journal of Formalized Mathematics, 11, 1999.
[15] Jaroslaw Kotowicz. Functions and finite sequences of real numbers. Journal of Formalized Mathematics, 5, 1993.
[16] Yatsuka Nakamura and Andrzej Trybulec. A mathematical model of CPU. Journal of Formalized Mathematics, 4, 1992.
[17] Piotr Rudnicki. The \tt for (going up) macro instruction. Journal of Formalized Mathematics, 10, 1998.
[18] Andrzej Trybulec and Yatsuka Nakamura. Some remarks on the simple concrete model of computer. Journal of Formalized Mathematics, 5, 1993.
[19] Michal J. Trybulec. Integers. Journal of Formalized Mathematics, 2, 1990.
[20] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.

Received June 14, 2000

[ Download a postscript version, MML identifier index, Mizar home page]