Sorting Jagged Arrays to Assess Solutions to Transportation Problems

About the authors:

Ivan N. Tkachenko, Senior Software Engineer, Ltd. «Technocom» (Tyumen); tkachenko@technocom.tech

Mikhail V. Grigorev, Cand. Sci. (Tech.), Associate Professor, Department of Program and System Engineering, Tyumen State University; m.v.grigorev@utmn.ru

Inna I. Grigoreva, Cand. Sci. (Tech.), Associate Professor, Department of Program and System Engineering, Tyumen State University; i.i.grigoreva@utmn.ru

Abstract:

This article explores the ways of sorting the jagged arrays for ordering rows in descending order by two criteria. A jagged array is a representation of the solutions of the problem of finding the optimal path, in which each row is one of the solutions. The purpose of sorting is to select the most significant solutions and then reduce the number of objects stored in the reachability matrix. Reducing the number of objects does not affect the dimensionality of the reachability matrix, but reduces the amount of memory needed to store the cells of the matrix. The task is described on the example of assessing the solutions to the transport task of cargo delivery. In the article, when sorting rows of jagged arrays, the priority of some cells of the array row is assumed over the others, that is, the first cell exerts a greater value on the result than the second, and the second cell has more than the third, etc.

The result of the study is the formalization of the rules of eight different approaches to sorting — by the number of variants of combining the two sorting criteria, the algorithm is given and the estimation of computational complexity is given. The criteria for sorting are the key length and key value. All eight approaches provide different sorting results. For each approach, the operations necessary to achieve the desired result are described and analyzed with provided examples. In each case, a problem is formulated and formalized.

The algorithm for sorting the jagged arrays is based on generating a text representation of the row key. The article only considers sorting rows, sorting columns in the article is not considered.

Conclusions are drawn about which of the described approaches provide the best sorting speed and why. On the example of the problem of cargo transportation, it is described to what effect the choice of this or that approach to sorting will result.

References:

1. Knut D. E. 2007. Iskusstvo programmirovaniya [The Art of Computer Programming], vol. 3. Sortirovka i poisk [Sorting and Searching]. Moscow: Williams.
2. Concatenation. Accessed on June 29, 2017. https://en.wikipedia.org/wiki/Concatenation
3. Corman Th. H., Leisserson Ch. I., Rivest R. L., Stein C. 2006. Algoritmy: postroyeniye i analiz [Introduction to Algorithms]. 2nd ed. Moscow: Williams.
4. Schildt H. 2011. C# 4.0. Polnoye rukovodstvo [C # 4.0. The Complete Reference]. Moscow: Williams.
5. American National Standard for Information Systems. Coded Character Sets — 7-Bit American National Standard Code for Information Interchange (7-Bit ASCII) ANSI-X3.4-1986 (R 2007), 2007.