Performance Comparison of Java and Python Implementations: Elementary
Sorting Algorithms and Union-Find Data Structures:
[Link]
The purpose of this study is to compare the runtime performance of several
fundamental algorithms implemented in two different programming languages:
Java and Python.
The analysis focuses on two algorithmic categories from Algorithms, 4th Edition
by Robert Sedgewick and Kevin Wayne:
Elementary Sorting Algorithms
Union–Find (Disjoint Set Union) Data Structures
To ensure fairness, both languages execute the exact same inputs, loaded from
shared text files. By doing so, the comparison reflects both:
the efficiency of the programming language, and
the theoretical efficiency of the algorithm itself.
2. Methodology
2.1 Shared Input for Sorting Algorithms
A file named [Link] was created containing a randomly generated list of
100,000 integers.
Both Java and Python:
1. Read this file,
2. Create a fresh copy of the list for each test,
3. Run the sorting algorithm,
4. Record the elapsed time.
This ensures that each algorithm runs on identical unsorted data.
2.2 Shared Input for Union–Find Algorithms
A second file, [Link], contains 1,000,000 pairs of integers (p, q)
representing union/connected operations. Each Union–Find implementation:
1. Initializes a structure with N sites,
2. Processes all (p, q) pairs in the same order,
3. Performs connected(p, q) and union(p, q) operations exactly as described
in the textbook.
This setup guarantees repeatability and fairness between Python and Java
results.
3. Algorithms Evaluated
3.1 Sorting Algorithms
All sorting algorithms come directly from Algorithms, 4th Edition and were
re-implemented faithfully in Python.
Selection Sort — $O(N^2)$
o Repeatedly finds the minimum element and places it at the start.
Insertion Sort — $O(N^2)$
o Builds a sorted portion of the list by inserting elements one by one.
Shell Sort — approximately $O(N^{3/2})$
o Uses Sedgewick's 3*h + 1 increment sequence.
o A significantly faster generalization of insertion sort.
3.2 Union–Find Algorithms
The following structures were analyzed, matching exactly the textbook
implementations:
Quick-Find — $O(N^2)$ worst-case
o Very fast find(), extremely slow union().
Quick-Union — tree-based structure
o Union operations create trees that may become tall.
Weighted Quick-Union — $O(\log N)$
o Each union attaches the smaller tree to the larger one, drastically
reducing height.
Weighted Quick-Union with Path Compression — $\approx O(N)$
o Nearly linear running time. Considered "almost constant time" per
operation.
Here is the complete report translated into English.
Performance Comparison of Java and Python Implementations:
Elementary Sorting Algorithms and Union-Find Data Structures
1. Introduction
The purpose of this study is to compare the runtime performance of several
fundamental algorithms implemented in two different programming
languages: Java and Python.
The analysis focuses on two algorithmic categories from Algorithms, 4th
Edition by Robert Sedgewick and Kevin Wayne:
Elementary Sorting Algorithms
Union–Find (Disjoint Set Union) Data Structures
To ensure fairness, both languages execute the exact same inputs, loaded
from shared text files. By doing so, the comparison reflects both:
the efficiency of the programming language, and
the theoretical efficiency of the algorithm itself.
2. Methodology
2.1 Shared Input for Sorting Algorithms
A file named [Link] was created containing a randomly generated list of
100,000 integers.
Both Java and Python:
1. Read this file,
2. Create a fresh copy of the list for each test,
3. Run the sorting algorithm,
4. Record the elapsed time.
This ensures that each algorithm runs on identical unsorted data.
2.2 Shared Input for Union–Find Algorithms
A second file, [Link], contains 1,000,000 pairs of integers (p, q)
representing union/connected operations.
Each Union–Find implementation:
1. Initializes a structure with N sites,
2. Processes all (p, q) pairs in the same order,
3. Performs connected(p, q) and union(p, q) operations exactly as described
in the textbook.
This setup guarantees repeatability and fairness between Python and Java
results.
3. Algorithms Evaluated
3.1 Sorting Algorithms
All sorting algorithms come directly from Algorithms, 4th Edition and were
re-implemented faithfully in Python.
Selection Sort — $O(N^2)$
o Repeatedly finds the minimum element and places it at the start.
Insertion Sort — $O(N^2)$
o Builds a sorted portion of the list by inserting elements one by one.
Shell Sort — approximately $O(N^{3/2})$
o Uses Sedgewick's 3*h + 1 increment sequence.
o A significantly faster generalization of insertion sort.
3.2 Union–Find Algorithms
The following structures were analyzed, matching exactly the textbook
implementations:
Quick-Find — $O(N^2)$ worst-case
o Very fast find(), extremely slow union().
Quick-Union — tree-based structure
o Union operations create trees that may become tall.
Weighted Quick-Union — $O(\log N)$
o Each union attaches the smaller tree to the larger one, drastically
reducing height.
Weighted Quick-Union with Path Compression — $\approx O(N)$
o Nearly linear running time. Considered "almost constant time" per
operation.
4. Python Implementations
4.1 Python Sorting Code
4.2 Python Union–Find Code
5. Java Implementations
Below are the Java measurement structures. Sorting algorithms such as
[Link](), [Link](), and [Link]() come directly from the algs4
library.
5.2 Java Union–Find Measurement Code
This code is compatible with the QuickFindUF, QuickUnionUF,
WeightedQuickUnionUF, and WeightedQuickUnionUPC (with path
compression) classes from algs4.
6. Experimental Results and Analysis
All tests were conducted on the [Link] (100,000 items) and [Link]
(1,000,000 pairs) files.
6.1 Sorting Algorithms Results
The dramatic difference between the quadratic ($O(N^2)$) algorithms and the
$O(N^{3/2})$ Shell Sort is evident in the results below.
Table 1: Sorting Algorithm Runtimes (100,000 Item List)
| Algorithm | Theoretical Complexity | Python (Seconds) | Java (Seconds) |
| :--- | :--- | :--- | :--- |
| Selection Sort | $O(N^2)$ | [Link] | [Link] |
| Insertion Sort | $O(N^2)$ | [Link] | [Link] |
| Shell Sort (3h+1) | $\approx O(N^{3/2})$ | [Link] | [Link] |
Analysis:
1. Language Speed: As expected, Java, with its Just-In-Time (JIT)
compiler, ran each algorithm faster than interpreted Python.
2. Algorithm Power: This is the most important finding. Shell Sort
running on Python ([Link] seconds) is orders of magnitude faster than
Selection Sort ([Link] seconds) and Insertion Sort ([Link] seconds)
running on Java. This proves that algorithm choice is a more dominant
performance factor than language choice.
3. Quadratic Slowness: The quadratic nature of Selection Sort and Insertion
Sort makes them practically unusable for a list of 100,000 items.
6.2 Union–Find Algorithms Results
The tests on 1,000,000 pairs of operations demonstrate the massive practical
impact of theoretical efficiency improvements.
Table 2: Union–Find Algorithm Runtimes (1,000,000 Operations)
| Algorithm | Theoretical Complexity (M ops) | Python (Seconds) | Java
(Seconds) |
| :--- | :--- | :--- | :--- |
| Quick-Find | $O(MN)$ | [Link] | [Link] |
| Quick-Union | $O(MN)$ (worst) | [Link] | [Link] |
| Weighted Quick-Union | $O(M \log N)$ | [Link] | [Link] |
| WQU + Path Compression | $\approx O(M)$ | [Link] | [Link] |
Analysis:
1. Quick-Find's Collapse: The $O(N)$ cost of the union() operation makes
this algorithm a showstopper for 1 million operations. It must scan the
entire array for each union.
2. Algorithmic Leap: While moving to Quick-Union is an improvement,
the real gain comes from WeightedQuickUnion. Keeping the trees
balanced drastically improves performance.
3. Optimal Solution: Adding Path Compression makes the algorithm nearly
linear-time, yielding the fastest results in both Java and Python.
4. Language vs. Algorithm: The speedup from (Java) Quick-Find to
(Python) WQU+PC is thousands of times greater than the slowdown
from switching from Java to Python.
7. Conclusion and Evaluation
This study strongly validates two important principles in algorithm design and
performance evaluation:
1. Algorithmic Complexity Dominates Language Choice.
The most striking result is that a fast algorithm in a slow language (Python Shell
Sort) dramatically outperforms a slow algorithm in a fast language (Java
Selection Sort). The theoretical efficiency of the algorithm is the most important
factor in performance.
2. Language Efficiency Matters (But is Secondary).
When comparing the same algorithm apples-to-apples (e.g., Java Shell Sort vs.
Python Shell Sort), Java is consistently faster due to its JVM optimizations,
whereas Python is limited by its interpreter. This difference is most pronounced
in CPU-bound tasks.
The enormous performance gaps observed in the Union–Find structures (from
Quick-Find to WQU+PC) perfectly summarize the importance of "choosing the
right data structure and algorithm" as emphasized in Algorithms, 4th Edition.
Final Message: Programming language affects performance, but algorithm
choice defines it.