Young Tableaux in the Tasks of Searching and Sorting

Young tableaux are widely known objects studied in combinatorics and related sciences. Today we are going to review how to apply Young tableaux in the context of such standard algorithmic tasks as searching and sorting. From this perspective, Young tableaux are quite close to pyramids. That's how they are actually called in a book by T. Cormen and others.

Young Tableau Notion

Let’s consider a Young tableau as a partially ordered and almost filled numerical matrix. Partial ordering means that each element of such matrix does not exceed the values of its upper and left neighbors (provided that the element has these neighbors). Almost filled means the following: completely filled are first j rows of the matrix (from 0 to (j-1)). In j row l elements are filled the first. All remaining elements are empty. Below is the example of a Young tableau:

According to the provided definition, rows and columns of a Young tableau are in ascending ordered. In particular, the element with a maximum value is in the top left corner. But the location of all the other elements cannot be unambiguously determined. Thus, we can consider Young tableaux as the matrix (table) analogue of partially ordered and almost filled trees.

Elements Insertion and Deletion

To begin with, let’s look at the way we can insert a new x value into a Young table. First of all, write x value into the first empty table cell so that its property of being almost filled would not be broken. If there is a partially filled row in the table, insert a new element into the first free cell of the row. If there is no such row, insert a new element into the first cell of the first empty row. Partial ordering can be broken after the insertion is done. To restore it, perform the element «move up» operation. To achieve that, compare the current x element with its upper and left neighbors. If any of them is less than x, swap it with x. This process of moving x up and to the left of the table goes on till we either face the top left corner, or both neighbors (or just one, if there’s no second one) are not greater or equal to x. The following picture shows the process of inserting «5» into the table:

We are going to delete the greater element only, which is located in the top left corner of the Young tableau. First, let’s move x value to this cell from the last occupied table cell. Then apply the operation of moving the element down. This operation is performed in a similar manner to moving up, but in the other direction (to the right and down) till the current element has a lower and a right neighbor, or these neighbors (or just one) are less than or equal to x. The process of deleting the greater element from the previous table is shown below:

It is obvious that the Young tableau with the described above insertion and deletion operations is actually the implementation of priority queues. It has an interesting peculiarity. Insertion and deletion time is the size of O(max(r,c)) order, in which r and c are the matrix size. If we suppose that r=c, the insertion time will have O(n^0.5) order, where n is the number of elements in the table. We will consider that to store n elements, a square table of the least possible m = int(ceil(sqrt(n))) size is used.

Sorting via Young Tableaux

It's clear that when having the implementation of abstract data type of priority queue, we can organize sorting of the defined numerical sequence X. The scheme of such sorting is quite trivial. At first, we write all the elements from X to the queue, then extract all of them from the queue and write them back to X beginning from the end (i.e. from right to left). Thus, the greatest element will be written at the end of X, the next one – to the next-to-last cell of X, and so on. It is obvious that such sorting time will be asymptotically equal to multiplication of n number of elements in X by the time of elements insertion (deletion) into the queue. Thus, when using a Young tableau as a priority queue, the time complexity of sorting will be equal to O(n^1.5). It means that the suggested algorithm asymptotically occupies an interposition between quadratic (insertion) and linear-logarithmic algorithms (merge) and is a close neighbor of Shell sort.

The described above sorting scheme supposes that a separate data structure is used for the queue storage, i.e. additional memory, in the amount not less than n. Just like in pyramids, it is possible to perform «sorting-in-place», without exceeding the limits of X (array) sequence.
We should note that:

1. each time we extract an element from X, it is automatically inserted into the table, and vice versa (i.e. the total amount of the necessary memory is constant all the time and equals to n);
   
2. usually matrices are stored in computer memory line by line in the form of a one-dimensional array (or we can organize such storage).
   

From these considerations, we will get the following simple sorting algorithm that uses two helper functions: elements MoveUp and MoveDown in a Young tableau. At any time, the left part of X array contains a Young table, while the left one stores X sequence. During the first pas, we start with the table comprising one element and gradually add elements from X into it. During the second pass, we successively extract the greatest element from the table and replace it with the last table element, at the same time shrinking the table size by one. As a result, the arranged X sequence is in ascending order.

from math import *
def YoungTableauSort(X, n):
  m = int(ceil(sqrt(n))) # the table size
  for i in range(1,n): # create a table
    MoveUp(X,i,m) 
  for i in range(1,n): # order the sequence 
    X[0], X[n-i] = X[n-i], X[0]
    MoveDown(X,n-i,m)

def MoveUp(X,i,m):
  while True:
    t = i
    if i%m and X[i-1]X[t]: t = i+1 # check the cell on the right
    if i/m+1X[t]: t = i+m # check the below cell 
    if i==t: return # we are done
    X[i], X[t] = X[t], X[i]
    i = t

Thus, we have a sorting algorithm, which takes O(n^1.5) time at worst.

Search in a Young Tableau

Suppose we want to use a Young tableau (represented by a one-dimensional array like we’ve done before) as a container. What functions can such container support? First of all, a new element insertion, secondly, the greatest element search (we will not have to search for a while as it comes first), the greatest element deletion, conversion to an ordered sequence. The mentioned operations are appropriate for pyramids as well. But Young tableaux are different from pyramids as they provide efficient search of elements. As for pyramids, we can find something except for the greatest element in them only with the help of complete search of all its elements (at worst). As for Young tableaux, we can search any element in O(n^0.5) time. The algorithm of such search will look like as follows. Start the search of x element from the top right table corner. If the current element is equal to the sought one, the search is completed. But if it is less than the sought one, we should move a step to the left, as all below elements will certainly be less than x. If there is nowhere to move, the search is unsuccessful. When the current element is greater than the sought one, move a one cell down. If the current row is the last one, the move is impossible and the search is unsuccessful. If the current row is not the last one, but there is no element below the current one, we should move to the left (checking whether the left edge of the table is reached).

See the code of such function below:

def Find(X,k,m,x): # k – the number of elements in the table 
  i = m-1
  while True:
    if X[i]==x: return i # found
    if X[i]=k: # a move to the left required
      if i%m: i -= 1
      else: return -1
    else: # a move downwards required 
      if i/m

It is easy to make sure that the number of viewed elements of the table during the search execution does not exceed the doubled table size, i.e. it is the size of order O(n^0.5). The following picture depicts an example of searching 4 number in a Young tableau.

Instead of the Summary

We can add the following operations to the ones already mentioned:

• Changing any element value in O(n^0.5) time;
  
• Deleting a random element in O(n^0.5) time;
  
• The least element search, which is executed in constant time, as the least element is located either in the last non-empty cell, or in the last cell of the next-to-last non-empty row.
  

Thus, we can consider Young tableaux as a relatively simple analogue of binary search trees: implementation is quite simple, small requirements for data storage. There are also some drawbacks as execution time of some operations is not logarithmic, but of square root. There is also a problem of overflow: when there is no more space in a table, we can either add a new row (without executing restructurization, but breaking squareness of the table. It can further lead to loss of operation efficiency), or execute a complete restructurization to a new square table of bigger size. The mentioned drawbacks can be partially solved with the help of so-called binary Young tableaux that I am going to describe in the following article.