Grid Sort Method

Introduction

My article aims at a "new" way of sorting whole numbers. Usually, the complexity of the sorting algorithm is O (n * log₂ (n) ).

But, this does not take into account the advantage of the properties of integers.

Background

One of my friends said that there exists a sorting algorithm whose complexity is O (n). 

When he said that, I thought it was impossible to get such an algorithm.

But, we have never found such an algorithm on the Internet. That is why I am writing this article, which I claim to be true.

Overview of sorting algorithms

Here I will explore a list of sorting algorithms. I refer to the book "Numerical Recipes in C" (1999, second edition) written by William H. Press, William T. Vetterling, Saul A. Teukolsky and Brian P. Flannery.

Above all, chapter eight of this book shows most sorting algorithms with source code in C language and explanations.

Some practical knowledge of techniques for sorting is an indispensable part of any good programmer's expertise. We would not want to consider yourself expert in numerical techniques while remaining ignorant of so basic a subject.

Here, more specifically, are the tasks that this chapter will deal with :

1. Sort, i.e., rearrange, an array of numbers into numerical order.
2. Rearrange an array into numerical order while performing the corresponding rearrangement of one or more additional arrays, so that the correspondence between elements in all arrays is maintained.
3. Given an array, prepare an index table for it, i.e., a table of pointers telling which number array element comes first in numerical order, which second, and so on.
4. Given an array, prepare a rank table for it, i.e., a table telling what is the numerical rank of the first array element, the second array element, and so on.
5. Select the Mth largest element from an array.

For the basic task of sorting N elements, the best algorithms require on the order of several times n log₂ n operations. The algorithm inventor tries to reduce the constant in front of this estimate to as small a value as possible.

Two of the best algorithms are "QuickSort", invented by the inimitable C.A.R. Hoare, and "Heapsort" invented by J.W.J. Williams.

For large n (say > 1000), Quicksort is faster, on most machines, by a factor of 1.5 or 2; it requires a bit of extra memory, however, and is a moderately complicated program. Heapsort is a true "sort in place," and is somewhat more compact to program and therefore a bit easier to modify for special purposes.

 

Grid Sort Method

This is the introduction of an idea to sort the elements with numbers.

The property of a grid is a cut in a separate order with two dimensional values.
This idea indicates that for a number there are two other variables and the equation is simply the distance of the pythagoras, usually used for the Cartesian coordinate port in the polar coordinates.

The following paragraphs explore this idea from the beginning with an example and adapt the algorithm to be true.

Later in this document, I show this algorithm that classifies n elements containing numbers.

Example

Suppose I want to sort this list of numbers

11  62  88  30  5  45  13  70  76

I can give another permutation of this list of numbers. But, there is only one permutation of these numbers which is in an ascending numerical order.

I propose to play with this example to show the grid that helps to sort.

This grid shows on the horizontal lines the digits of the unit of any number. Then, on the vertical columns, there are 10 possible digits of tens for a number less than or equal to 99.

And now, to sort the list, I have to read this grid from top to bottom, then from left to right.

Anticipation Test

Anticipating the process of an algorithm is important to visualize all the risks and to prove that the algorithm may be true or have an error test that leaves an error in the result.

Grid is a model to understand that a random list of numbers is simply an instance of multiple permutations obtained from the beginning by the corresponding ordered list.

In addition, the place to fill a list of 100 numbers without duplicates is to browse the grid. If the list contains duplicate numbers, it is important to count the number of duplicates. Then, you keep this counter in a list for each number of duplicates.

Healing improvements

Using a grid to store numbers and sort them through the grid in an ordered iteration is a good idea.

However, the exact algorithm is not exactly a grid for storing digits. The grid must be filled with a cut of each number. The product of columns and rows must be equal to the number of elements in the list.

The grid could have three or four dimensions; But, with a two-dimensional grid, I have to take the nearest square so that the number of elements in the list is equal to p².

So for a three-dimensional grid, I have to take the closest cubic so that the number of elements is equal to p³.

Mathematics and algebra show that there exists a two-dimensional grid that is numerically equal to a three-dimensional grid.
With this assertion, we could instead use a two-dimensional grid to store all the items on the list to sort. But, this may not be true for all list sizes.

In the latter context, the list is simply divided into two parts; The remaining part could be placed inside the last cell of the grid.

Algorithm complexity

According to the sorting method of the grid, its complexity is O (n).

First, the list is iterated once, so you need "n" number of laps.

Second, you have two ways :

1. You recreate the list in ascending (or descending) order by reading the grid. Complexity changes with + "b²".
2. The grid has special formatting: for example, two-digit numbers are modeled in the grid with 20 integer values of 10 bits. 10 values are designed to handle horizontal lines and 10 other values are for vertical columns.

The first option calls your algorithm to have a complexity identical to b², where b is the cut of each value in the list.

The second option is the best way to implement the grid.

Adaptive complexity

When there are N elements in a list and each element has a maximum of k digits, there is an optimal number of the grid dimension (2, 3 or more) and the cardinal of each dimension, also called in algebra, Ker(F).

Sum of successive numbers

The sum of the successive numbers is

When I try to position in a grid and there are 15 elements, I can create a grid of 5 lines and 6 columns. This is the grid I made

Conclusion

This equation is a second degree polynomial. The 1 in this equation means that it is a progression with only 1 turn for each new element.
If it were not 1, it could be a number that emits each term by a continuous distance as such, each term being spaced by the same distance.

Finally, two equations give the distance and the solution the sum of all the elements and the largest of them (identified by the variable x).

 

Thus, the algorithm is iterative. If you encounter a square in u, draw the grid with rows and columns provided by the product of x + u and u.

Incremental playback is too expensive

Although I can calculate the exact position of each item and exchange with others, I can not browse a list to find a particular item and where to place it.

Similarly, I can not insert an item into a sorted list because the inserted item is moving all of the following items.

 

Points of Interest

While I studied computer science, I learned the main needs of a sorting algorithm.

In particular, a sorting algorithm is true until we find an example with a specific list of numbers and the result of which is an unordered list. This is the logic of Hoare and the logic of Hoare's proof.

Then, while I tell a new sorting algorithm, the main search is to prove that this algorithm will always be the result of an ordered list. To do this, first of all, take the time to use it and explore the organic model to make sure it is a true sorting algorithm.

History

First version of this article.

In a few days, I will continue to find a sorting algorithm that could combine mathematics and algorithmic optimization.