Young Tables in Search and Sort Tasks
Jung's tables are a widely known (in narrow circles) type of objects studied in combinatorics and related sciences: reference , reference , book . Below we consider the use of a particular type of Young table with reference to such standard algorithmic problems as search and sorting. From this point of view, Jung's tables are very close to the pyramids, in fact, this is how they are positioned in the Kormen and co textbook (exercises in the section on pyramids).
Let us call the Young table a partially ordered almost filled numerical matrix. Partial ordering means that each element of such a matrix does not exceed the values of its upper and left neighbors (provided that these elements have such neighbors). Almost full means the following: the first j rows of the matrix (from zero to (j-1) -th) are completely filled in the table, the first l elements are filled in the j-th row, all the remaining rows are empty. An example of a Young table is shown in the following figure.
According to our definition, the rows and columns of the Young table are ordered in descending order. In particular, the largest element of the table is in its upper left corner. However, the location of all other elements is already not clearly defined. Thus, Young table can be considered as a matrix (tabular) analogue of partially-ordered almost filled trees, known in the world as pyramids.
First, let's look at how to insert a new value of x into the Young table. To do this, we first write the value of x in the first free cell of the table, so that its almost full property is not violated. If the table does not have the end of a filled row, then insert a new element in the first free cell of this row. If there is no such line, then we will insert a new element into the first (zero) cell of the first empty line. After the insertion is completed, only the partial order property can be broken. To restore it perform the operation of lifting the item. For this, the current element x is compared with its upper and left neighbors. If any of these neighbors is a smaller x, then swap x with the smaller of the neighbors. This process of moving x up and to the left on the table continues until we rest in the upper left corner, or both neighbors (or one, if there is no second one) turn out to be larger or equal to x. The following figure shows the process of inserting the number 5 in the table from the first figure.
Only the largest element located in its upper left corner will be deleted from the Young table. First, we transfer the value x from the last occupied cell of the table to this cell, after which we apply the element descent operation. This operation is performed in the same way as lifting, but in the other direction (right and down), until the current element has lower and right neighbors, or these neighbors (or only one, if there is no second) are less or equal to x. The process of deleting the largest element from the table from the last figure is shown below.
It is obvious that the Young table with the above insert and delete operations is actually an implementation of the ADT Queue with priority. An interesting feature of this implementation is that the time of insertion and deletion is of the order of O (max (r, c)), where r and c are the dimensions of the matrix. If we assume that r = c, then we get that the insertion time is of the order O (n 0.5 ), where n is the number of elements in the table. Below we will assume that a square table of the smallest possible size m = int (ceil (sqrt (n))) is used to store the n elements.
')
It is clear that with the implementation of the ADT Queue with priority, you can organize the sorting of a given numerical sequence X. The scheme of such sorting is trivial: first write all their X elements into the queue, then remove all the elements from the queue and write and return to X starting from the end (t. e. right to left). Thus, the largest element will be written at the end of X, the next largest - in the penultimate cell X, etc. It is obvious that the time of such sorting will be asymptotically equal to the product of the number n of elements in X by the time of insertion (deletion) of elements into the queue. Those. when using the Young table as a priority queue, the sorting complexity will be O (n 1.5 ). This means that the proposed algorithm asymptotically occupies an intermediate position between the quadratic (inset) and linear-logarithmic algorithms (merge) and is a close neighbor of Shell sort.
The described general sorting scheme assumes that a separate data structure is used to store the queue, i.e. additional memory volume is not less than n. However, as for pyramids, it is possible for Young's tables to sort by place, without going beyond the sequence (array) of X. To do this, note that 1) every time an element is removed from X, it is immediately inserted into the table and vice versa i.e. the total amount of necessary memory remains constant all the time and equal to n); 2) usually matrices are stored in computer memory line by line in the form of, essentially, a one-dimensional array (or we ourselves can organize such a storage scheme). Based on these considerations, we obtain the following simple sorting algorithm, which uses two auxiliary functions of lifting (MoveUp) and descending (MoveDown) of elements in the Young table. At each moment of time, the left part of the array X contains the Young table, the right - the sequence X. In the first pass, we start with a table in one element and gradually add elements from X to it. with the last element of the table, at the same time reducing the size of the table by one. This leads to the fact that the newly built sequence X is ordered in ascending order.
So, we have an in-place sorting algorithm that works during O (n 1.5 ) in the worst case.
Suppose we want to use a Young table (represented by a one-dimensional array, as was done above) as a container. What functions can support such a container? First of all, the insertion of a new element, secondly, the search for the largest element (especially not to look for it, since this element is the first), removal of the largest element, conversion to an ordered sequence. The listed operations are also inherent in the pyramids. What distinguishes Young's tables about the pyramids is the ability to effectively search for items. Finding anything other than the largest element in the pyramid can only be done by exhaustively searching all its elements (at worst). But in the Young table, the search for any element can be performed at the same time of the order O (n 0.5 ). The algorithm for such a search is as follows. We start the search for the element x from the upper right corner of the table (in a one-dimensional array it is the element with the number m-1). If the current item is equal to the search, the search is completed. If the current element is less than the desired one, then move the table one step to the left, because all elements below will be obviously smaller x. If there is nowhere to move, the search is declared unsuccessful. If the current element is greater than the desired one, then it is necessary to move down one cell. If the current line is the last one, then the shift is not possible - the search is unsuccessful. If the current line is not the last, but there is no current element at the bottom, then it is necessary to shift to the left again (with a check to reach the left edge of the table). The code for this function is shown below.
It is easy to make sure that the number of elements scanned in a table when performing a search does not exceed twice the size of the table, i.e. again, it is of the order of O (n 0.5 ). An example of finding the number 4 in the Young table is shown in the following figure.
To the above operations on Young table, you can add 1) change the value of any element in time O (n 0.5 ); 2) removal of an arbitrary element in time O (n 0.5 ); 3) search for the smallest element that is generally performed in constant time, since the smallest element, by virtue of the definition of the Young table, is located either in the last non-empty cell or in the last cell of the last but one non-empty row.
Thus, Young's tables can be considered as a relatively simple analogue of binary search trees, advantages: ease of implementation, low overhead costs for data storage; shortcomings: the execution time of the main operations is not logarithmic, but root-root, the overflow problem is after the place in the table ends, we can either add a new row (without performing full restructuring, but violating the squareness of the table, which may further reduce efficiency of operations), or perform a complete restructuring of a new larger square table. These deficiencies are partially solved with the help of the so-called binary Young tables, which I will try to write about sometime in the near future.
The concept of Young table
Let us call the Young table a partially ordered almost filled numerical matrix. Partial ordering means that each element of such a matrix does not exceed the values of its upper and left neighbors (provided that these elements have such neighbors). Almost full means the following: the first j rows of the matrix (from zero to (j-1) -th) are completely filled in the table, the first l elements are filled in the j-th row, all the remaining rows are empty. An example of a Young table is shown in the following figure.
According to our definition, the rows and columns of the Young table are ordered in descending order. In particular, the largest element of the table is in its upper left corner. However, the location of all other elements is already not clearly defined. Thus, Young table can be considered as a matrix (tabular) analogue of partially-ordered almost filled trees, known in the world as pyramids.
Insert and delete items
First, let's look at how to insert a new value of x into the Young table. To do this, we first write the value of x in the first free cell of the table, so that its almost full property is not violated. If the table does not have the end of a filled row, then insert a new element in the first free cell of this row. If there is no such line, then we will insert a new element into the first (zero) cell of the first empty line. After the insertion is completed, only the partial order property can be broken. To restore it perform the operation of lifting the item. For this, the current element x is compared with its upper and left neighbors. If any of these neighbors is a smaller x, then swap x with the smaller of the neighbors. This process of moving x up and to the left on the table continues until we rest in the upper left corner, or both neighbors (or one, if there is no second one) turn out to be larger or equal to x. The following figure shows the process of inserting the number 5 in the table from the first figure.
Only the largest element located in its upper left corner will be deleted from the Young table. First, we transfer the value x from the last occupied cell of the table to this cell, after which we apply the element descent operation. This operation is performed in the same way as lifting, but in the other direction (right and down), until the current element has lower and right neighbors, or these neighbors (or only one, if there is no second) are less or equal to x. The process of deleting the largest element from the table from the last figure is shown below.
It is obvious that the Young table with the above insert and delete operations is actually an implementation of the ADT Queue with priority. An interesting feature of this implementation is that the time of insertion and deletion is of the order of O (max (r, c)), where r and c are the dimensions of the matrix. If we assume that r = c, then we get that the insertion time is of the order O (n 0.5 ), where n is the number of elements in the table. Below we will assume that a square table of the smallest possible size m = int (ceil (sqrt (n))) is used to store the n elements.
')
Sort using Young table
It is clear that with the implementation of the ADT Queue with priority, you can organize the sorting of a given numerical sequence X. The scheme of such sorting is trivial: first write all their X elements into the queue, then remove all the elements from the queue and write and return to X starting from the end (t. e. right to left). Thus, the largest element will be written at the end of X, the next largest - in the penultimate cell X, etc. It is obvious that the time of such sorting will be asymptotically equal to the product of the number n of elements in X by the time of insertion (deletion) of elements into the queue. Those. when using the Young table as a priority queue, the sorting complexity will be O (n 1.5 ). This means that the proposed algorithm asymptotically occupies an intermediate position between the quadratic (inset) and linear-logarithmic algorithms (merge) and is a close neighbor of Shell sort.
The described general sorting scheme assumes that a separate data structure is used to store the queue, i.e. additional memory volume is not less than n. However, as for pyramids, it is possible for Young's tables to sort by place, without going beyond the sequence (array) of X. To do this, note that 1) every time an element is removed from X, it is immediately inserted into the table and vice versa i.e. the total amount of necessary memory remains constant all the time and equal to n); 2) usually matrices are stored in computer memory line by line in the form of, essentially, a one-dimensional array (or we ourselves can organize such a storage scheme). Based on these considerations, we obtain the following simple sorting algorithm, which uses two auxiliary functions of lifting (MoveUp) and descending (MoveDown) of elements in the Young table. At each moment of time, the left part of the array X contains the Young table, the right - the sequence X. In the first pass, we start with a table in one element and gradually add elements from X to it. with the last element of the table, at the same time reducing the size of the table by one. This leads to the fact that the newly built sequence X is ordered in ascending order.
from math import * def YoungTableauSort(X, n): m = int(ceil(sqrt(n))) # for i in range(1,n): # MoveUp(X,i,m) for i in range(1,n): # X[0], X[ni] = X[ni], X[0] MoveDown(X,ni,m) def MoveUp(X,i,m): while True: t = i if i%m and X[i-1]<X[t]: t = i-1 # if i/m and X[im]<X[t]: t = im # if i==t: return # X[i], X[t] = X[t], X[i] i = t def MoveDown(X,k,m): # k - i = 0 while True: t = i if i%m+1<m and i+1<k and X[i+1]>X[t]: t = i+1 # if i/m+1<m and i+m<k and X[i+m]>X[t]: t = i+m # if i==t: return # X[i], X[t] = X[t], X[i] i = t So, we have an in-place sorting algorithm that works during O (n 1.5 ) in the worst case.
Search Young table
Suppose we want to use a Young table (represented by a one-dimensional array, as was done above) as a container. What functions can support such a container? First of all, the insertion of a new element, secondly, the search for the largest element (especially not to look for it, since this element is the first), removal of the largest element, conversion to an ordered sequence. The listed operations are also inherent in the pyramids. What distinguishes Young's tables about the pyramids is the ability to effectively search for items. Finding anything other than the largest element in the pyramid can only be done by exhaustively searching all its elements (at worst). But in the Young table, the search for any element can be performed at the same time of the order O (n 0.5 ). The algorithm for such a search is as follows. We start the search for the element x from the upper right corner of the table (in a one-dimensional array it is the element with the number m-1). If the current item is equal to the search, the search is completed. If the current element is less than the desired one, then move the table one step to the left, because all elements below will be obviously smaller x. If there is nowhere to move, the search is declared unsuccessful. If the current element is greater than the desired one, then it is necessary to move down one cell. If the current line is the last one, then the shift is not possible - the search is unsuccessful. If the current line is not the last, but there is no current element at the bottom, then it is necessary to shift to the left again (with a check to reach the left edge of the table). The code for this function is shown below.
def Find(X,k,m,x): # k - i = m-1 while True: if X[i]==x: return i # if X[i]<x or i/m+1<m and i+m>=k: # if i%m: i -= 1 else: return -1 else: # if i/m<m-1 and i+m<k: i += m else: return -1 It is easy to make sure that the number of elements scanned in a table when performing a search does not exceed twice the size of the table, i.e. again, it is of the order of O (n 0.5 ). An example of finding the number 4 in the Young table is shown in the following figure.
Instead of conclusion
To the above operations on Young table, you can add 1) change the value of any element in time O (n 0.5 ); 2) removal of an arbitrary element in time O (n 0.5 ); 3) search for the smallest element that is generally performed in constant time, since the smallest element, by virtue of the definition of the Young table, is located either in the last non-empty cell or in the last cell of the last but one non-empty row.
Thus, Young's tables can be considered as a relatively simple analogue of binary search trees, advantages: ease of implementation, low overhead costs for data storage; shortcomings: the execution time of the main operations is not logarithmic, but root-root, the overflow problem is after the place in the table ends, we can either add a new row (without performing full restructuring, but violating the squareness of the table, which may further reduce efficiency of operations), or perform a complete restructuring of a new larger square table. These deficiencies are partially solved with the help of the so-called binary Young tables, which I will try to write about sometime in the near future.
Source: https://habr.com/ru/post/121800/
All Articles