Sort an array using Young tableau

In this post, we will see how to sort N2 numbers in increasing order using a N x N Young tableau in O(N3) time.


 

A N x N Young tableau is an N x N matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be infinity, which indicates an empty entry. Thus, a Young tableau can be used to hold n <= N2 finite numbers.

 
Consider reading below article on Young tableau as a prerequisite of this post:

Young Tableau | Insert, Search, Extract-Min, Delete, Replace

 
To sort an array using Young tableau, we insert each of its values into an empty Young tableau one at a time. Afterwards, we repeatedly call the Extract-Min routine on Young tableau until the tableau is empty and put the returned values back into the original array.

Here’s a C++ program that demonstrates it:

 

Download   Run Code

Output:

1 2 3 4 5 6 7 8

 
Constructing a O(N x N) Young tableau from O(N2) keys takes O(N3) time. Also, the extractMin() routine is called O(N*N) times which runs in linear time. So, the overall time complexity of the proposed solution is O(N3) for O(N2) keys. The auxiliary space used by the program is O(N2) for constructing a N x N Young tableau.

In order word, the sorting procedure runs in O(n1.5) time and O(n) space where n is the size of the input.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of