Implementation of a Young Tableau data structure in Python with build and sort operations, benchmarked on arrays up to 200,000 elements across sorted, reversed, and random input distributions.
A Young Tableau is a 2D matrix where each row and each column is sorted in non-decreasing order. This project implements a Young Tableau class that takes a flat array, arranges it into a near-square matrix, builds the Young Tableau property via a bottom-up sift-down procedure, and then extracts elements in sorted order using repeated extract-min operations. The result is a sorting algorithm based on the Young Tableau data structure.
- Young Tableau construction from an arbitrary array
- Bottom-up build procedure (analogous to heap building)
- Extract-min operation for sorted extraction
- Full sort-via-extraction pipeline
- Benchmarking framework for sorted, reversed, and random inputs
- Array sizes from 20,000 to 200,000 elements
- Young Tableau (Young Matrix)
- Matrix-based data structures
- Sift-down / heapify operations
- Priority queue extraction patterns
- Sorting via data structure operations
- Empirical complexity analysis
YoungTable.py # Young Tableau class and utility functions
Main.py # Demo script: build and sort a random array
randGenTemplate.py # Input generators (random, sorted, reversed)
benchmark/
benchmark.py # Benchmarking framework
randomCase/randomCase.py # Random input benchmark
reversedCase/reversedCase.py # Reverse-sorted input benchmark
sortedCase/sortedCase.py # Already-sorted input benchmark
DS Lab YoungTable 1_231024_121724.txt # Assignment pseudocode specification
DS Lab YoungTable 1_231024_121724.pdf # Assignment description (PDF)
DS Lab YoungTable 1_231024_121724.jpg # Assignment description (image)
AryanGhasemi-Result.xlsx # Benchmark results spreadsheet
The build operation converts an arbitrary 2D matrix into a valid Young Tableau. Starting from the bottom-right corner and working toward the top-left, each cell is "sifted down" — compared with its right and below neighbors, then swapped with the smaller of the two if that neighbor is less than the current cell. This is recursively applied until the Young Tableau property holds. The approach mirrors bottom-up heap construction.
Given a cell at position (i, j), siftDown compares it with:
- The cell directly below: (i+1, j)
- The cell directly to the right: (i, j+1)
If either neighbor is smaller, the current cell is swapped with the smallest neighbor, and siftDown recurses at the new position.
The minimum element is always at position (0, 0) in a valid Young Tableau. To extract it, the value is removed, replaced with infinity, and siftDown is called at (0, 0) to restore the property. This takes O(row + col) time per extraction.
Sorts the entire table by repeatedly extracting the minimum. After n extractions, the elements are in sorted order. Total time is O(n * (sqrt(n) + sqrt(n))) = O(n * sqrt(n)).
Two machines were used. All times in seconds.
| n | Sorted Case | Reversed Case | Random Case |
|---|---|---|---|
| 20,000 | 0.889 | 1.634 | 0.971 |
| 60,000 | 4.414 | 8.234 | 5.174 |
| 100,000 | 9.797 | 15.775 | 11.630 |
| 140,000 | 16.616 | 27.240 | 22.186 |
| 200,000 | 28.317 | 47.913 | 38.903 |
| n | Sorted Case | Reversed Case | Random Case |
|---|---|---|---|
| 40,000 | 0.010 | 3.090 | 1.168 |
| 57,600 | 0.014 | 5.377 | 2.024 |
| 78,400 | 0.018 | 8.624 | 3.262 |
| 90,000 | 0.024 | 10.782 | 4.039 |
- Reversed input is consistently the slowest, requiring the most swaps during the build phase and the deepest sift-down paths during extraction.
- Sorted input is the fastest because the array is already close to satisfying the Young Tableau property; build requires minimal rearrangement.
- Growth is super-linear — the O(n * sqrt(n)) theoretical complexity is visible in the data, with 200K elements taking roughly 28-48 seconds depending on input distribution.
Design Note: The table dimensions are chosen to be as close to square as possible. When the array size is not a perfect square, extra cells are padded with zeros.
| Operation | Time Complexity |
|---|---|
| Build Young Tableau | O(n * sqrt(n)) |
| Extract Min | O(sqrt(n)) |
| Sort (n extractions) | O(n * sqrt(n)) |
| Space | O(n) |
Where n is the total number of elements and the table is approximately sqrt(n) x sqrt(n).
Requires Python 3.x. No external dependencies.
# Run the demo
python Main.py
# Run benchmarks
cd benchmark/randomCase && python randomCase.py
cd ../reversedCase && python reversedCase.py
cd ../sortedCase && python sortedCase.pyThis project demonstrates sorting through a matrix-based data structure rather than traditional array-based comparison sorts. The Young Tableau sort has O(n * sqrt(n)) complexity, which is slower than O(n log n) comparison sorts but provides a useful illustration of how 2D structural invariants can be maintained and exploited for ordering. The benchmarks confirm the theoretical predictions and show that input distribution significantly affects performance due to varying sift-down depths.
Educational project created for the Data Structures course at Shahid Beheshti University.