Sorting in construction of resolutions of combinatorial designs
DOI:
https://doi.org/10.55630/mem.2024.53.057-064Keywords:
sorting, classification algorithm, combinatorial design, design resolutionAbstract
There are different kinds of sorting algorithms. Each algorithm has its own advantages and disadvantages depending on the data they process. We are interested in the performance of sorting algorithms in the case of construction of resolutions of combinatorial designs. Studying their performance for this special class of problems will give us the opportunity to improve, if possible, the speed of our software for solving similar problems. We use C++ and, for part of our investigations, the computer algebra system GAP.
References
A. Betten. The packings of PG(3,3). Des. Codes Cryptogr., 79, no. 3 (2016), 583–595.
I. Bouyukliev, S. Bouyuklieva, S. Kurz. Computer Classification of Linear Codes. IEEE T Inform. Theory, 67, no. 12 (2021), 7807–7814.
M. Braun. Construction of a point-cyclic resolution in PG(9,2). Innovations in Incidence Geometry: Algebraic, Topological and Combinatorial, 3, no. 1 (2006), 33–50.
J. Clement, Th. Nguyen Thi, B. Vallee. Towards a Realistic Analysis of Some Popular Sorting Algorithms. Combinatorics, Probability and Computing, 24, no. 1 (2015), 104–144.
C. J. Colbourn, A. Rosa. Triple Systems. Oxford, Clarendon Press, 1999.
M. Dzhumalieva-Stoeva, I. G. Bouyukliev, V. Monev. Construction of self-orthogonal codes from combinatorial designs. Probl. Inf. Transm., 48 (2012), 250–258 .
I. A. Faradˇzev. Constructive enumeration of combinatorial objects, In Probl`emes Combi- natoires et Th´eorie des Graphes, (Universit´e d’Orsay, July 9 – 13, 1977). Colloq. Internat. du C.N.R.S., 260 (1978), 131–135.
GAP – Groups, Algorithms, Programming – a System for Computational Discrete Algebra, http://www.gap-system.org/. Last accessed 21 December 2023.
GAP – Reference Manual, Release 4.12.2, 2022-12-18, the GAP Group. Last accessed 21 December 2023.
A. Gruner, M. Huber. New Combinatorial Construction Techniques for Low-Density Parity-Check Codes and Systematic Repeat-Accumulate Codes. IEEE T Commun., 60, no. 9 (2012), 2387–2395.
Handbook of Combinatorial Designs, C. Colbourn, J. Dinitz,(eds.) 2nd edn. In: Rosen, K. (eds.) Discrete mathematics and its applications, Boca Raton, FL., CRC Press 2007.
S. J. Johnson, S. R. Weller. Resolvable 2-designs for regular low-density parity-check codes. IEEE T Commun., 51, no. 9 (2003), 1413–1419.
P. Kaski, P. O¨ sterg˚ard. Classification algorithms for codes and designs. Berlin, Springer, 2006.
R. Koetter, F. R. Kschischang. Coding for errors and erasures in random network coding. IEEE T Inform. Theory, 54 (2008), 3579–3591.
D. E. Knuth. The art of computer programming 3: Sorting and Searching, 2nd edn. Addison-Wesley, 1998.
A. Kumar, S. Maitra. Resolvable block designs in construction of approximate real MUBs that are sparse. Cryptogr. Commun., 14 (2022), 527–549 .
M. Markov, Y. Borissov. Computing the Weight Distribution of the Binary Reed-Muller Code R(4,9). arXiv:2309.10462.
D. R. Musser. Introspective Sorting and Selection Algorithms. Software: Practice and Experience, 27, no. 8 (1997), 983–993.
O. R. Peters. Pattern-defeating Quicksort. arXiv./abs/2106.05123, 2021.
A. R. Prince. The cyclic parallelisms of PG(3,5). Eur. J. Combin., 19, no. 5 (1998), 613–616.
G. F. Royle. An orderly algorithm and some applications in finite geometry. Discrete Math, 185, no. 1–3 (1998), 105–115.
A. Sabah, S. Abu-Naser, Y. Helles, R. Abdallatif, F. Y. A. Abu Samra, A. H. Abu Taha, N. M. Massa, A. A. Hamouda. Comparative Analysis of the Performance of Popular Sorting Algorithms on Datasets of Different Sizes and Characteristics. Int. J. Academic Eng. Research (IJAER), 7, no. 6 (2023), 76–84.
J. Sarmiento. Resolutions of PG(5,2) with point-cyclic automorphism group. J. Combin. Des., 8, no. 1 (2000), 2–14.
Software Testing Help, Sorting Techniques In C++, https://www.softwaretestinghelp. com/sorting-techniques-in-cpp/. Last accessed 21 December 2023.
B. Subbarayudu, L. L. Gayatri, P. S. Nidhi, P. Ramesh, R. G. Reddy, K. K. Reddy C. Comparative Analysis on Sorting and searching Algorithms. Int. J. Civil Eng. Technol. (IJCIET), 8, no. 1 (2017), 955–978.
S. Topalova, S. Zhelezova. Backtrack Search for Parallelisms of Projective Spaces, In: Flocchini P., Moura L. (eds.) Combinatorial Algorithms, IWOCA 2021. Lect. Notes Com- put. Sci., vol. 12757, (2021), 544–557.
S. Topalova, S. Zhelezova. Transitive Deficiency One Parallelisms of PG(3,7). Mathe- matics, 11 (2023), 2458.
S. Topalova, S. Zhelezova. Point-cyclic KTS(45). 18th Annual Meeting of the Bulgarian Section of SIAM, BGSIAM’23 Extended abstracts (2023), 48–49.
A Computer Science portal, https://www.geeksforgeeks.org/cocktail-sort/. Last ac- cessed 21 December 2023.
CodersLegacy, https://coderslegacy.com/comparison-of-sorting-algorithms/. Last accessed 21 December 2023.
