We show that exchanging of pairs in an array which are in incorrect order leads to sorted array. It justifies correctness of Bubble Sort, Insertion Sort, and Quicksort.
@article{bwmeta1.element.doi-10_2478_v10037-011-0015-4,
author = {Grzegorz Bancerek},
title = {Sorting by Exchanging},
journal = {Formalized Mathematics},
volume = {19},
year = {2011},
pages = {93-102},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_v10037-011-0015-4}
}
Grzegorz Bancerek. Sorting by Exchanging. Formalized Mathematics, Tome 19 (2011) pp. 93-102. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_v10037-011-0015-4/
[1] Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990.
[2] Grzegorz Bancerek. Ordinal arithmetics. Formalized Mathematics, 1(3):515-519, 1990.
[3] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990.
[4] Grzegorz Bancerek. Sequences of ordinal numbers. Formalized Mathematics, 1(2):281-290, 1990.
[5] Grzegorz Bancerek. Directed sets, nets, ideals, filters, and maps. Formalized Mathematics, 6(1):93-107, 1997.
[6] Grzegorz Bancerek. Mizar analysis of algorithms: Preliminaries. Formalized Mathematics, 15(3):87-110, 2007, doi:10.2478/v10037-007-0011-x.[Crossref]
[7] Grzegorz Bancerek. Veblen hierarchy. Formalized Mathematics, 19(2):83-92, 2011, doi: 10.2478/v10037-011-0014-5.[Crossref] | Zbl 1276.03044
[8] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990.
[9] Grzegorz Bancerek and Andrzej Trybulec. Miscellaneous facts about functions. Formalized Mathematics, 5(4):485-492, 1996.
[10] Czesław Byliński. Basic functions and operations on functions. Formalized Mathematics, 1(1):245-254, 1990.
[11] Czesław Byliński. Binary operations. Formalized Mathematics, 1(1):175-180, 1990.
[12] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990.
[13] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990.
[14] Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357-367, 1990.
[15] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990.
[16] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990.
[17] Andrzej Trybulec. On the sets inhabited by numbers. Formalized Mathematics, 11(4):341-347, 2003.
[18] Wojciech A. Trybulec and Grzegorz Bancerek. Kuratowski - Zorn lemma. Formalized Mathematics, 1(2):387-393, 1990.
[19] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990.
[20] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825-829, 2001.
[21] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990.
[22] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Formalized Mathematics, 1(1):85-89, 1990.