Algorithm Efficiency Analysis

Overview

This project is focused on comparing the runtime efficiency of five classic sorting algorithms and analyzing their performance at scale using the Bridges platform. We will explore Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, and Quicksort, as well as Java's built-in Arrays.sort() method, and visualize their performance on large input datasets.

Visualizations

Using the Bridges platform, I generated line graphs to illustrate the performance of each sorting algorithm. The graphs compare the runtime of these algorithms as input sizes increase, providing insights into their efficiencies under various conditions.

Linear Growth Benchmark: Bubble Sort vs Java Sort

This graph compares the performance of Bubble Sort and Java's Arrays.sort() method using a linear progression of input sizes. The inefficiency of Bubble Sort becomes evident as the input size increases.

Follow the link for full visualization: Graph 1

Geometric Growth Benchmark: Bubble Sort, Insertion Sort, and Java Sort

This graph compares Bubble Sort, Insertion Sort, and Java's Arrays.sort() method using a geometric progression of input sizes. As seen, Java's Arrays.sort() consistently outperforms the others for larger input sizes.

Follow the link for full visualization: Graph 2

Project Structure

The project includes the following components:

• SortingRuntimes.java: Contains the main code to generate the Bridges visualizations and compare the sorting algorithms.
• MySorts.java: Implements the five sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, and Quicksort.
• Quicksort.java: Includes the partition and quicksort methods.
• QuicksortTest.java: Contains unit tests for the Quicksort implementation, ensuring correctness and efficiency.

Algorithms Analyzed

The five classic sorting algorithms used in this analysis are as follows:

1. Bubble Sort
   Best-case: Θ(n²)
   Worst-case: Θ(n²)
   Average-case: Θ(n²)

2. Insertion Sort
   Best-case: Θ(n)
   Worst-case: Θ(n²)
   Average-case: Θ(n²)

3. Selection Sort
   Best-case: Θ(n²)
   Worst-case: Θ(n²)
   Average-case: Θ(n²)

4. Merge Sort
   Best-case: Θ(n log n)
   Worst-case: Θ(n log n)
   Average-case: Θ(n log n)

5. Quicksort
   Best-case: Θ(n log n)
   Worst-case: Θ(n²)
   Average-case: Θ(n log n)

6. Java’s Arrays.sort()
   Typically implemented using Timsort, which combines Merge Sort and Insertion Sort principles to offer a runtime of Θ(n log n).

Key Findings

• Best Performance: Java's Arrays.sort() and Merge Sort consistently outperform the other algorithms, scaling well with large datasets.
• Worst Performance: Bubble Sort and Insertion Sort perform poorly on large input sizes, with runtimes increasing quadratically.
• Impact of Algorithm Choice: For large datasets, choosing an efficient algorithm (like Quicksort or Merge Sort) can drastically reduce runtimes, as demonstrated in the visualizations.

How to Run the Project

To run this project and generate the visualizations:

1. Clone the repository:

   git clone https://github.com/cmontilha/AlgorithmEfficiencyAnalysis.git

2. Open the project in your favorite IDE (I personally prefer IntelliJ).
3. Add your Bridges credentials in SortingRuntimes.java.
4. Run the main method in SortingRuntimes.java to generate the graphs.

Conclusion

This project demonstrates the importance of selecting the right sorting algorithm when dealing with large datasets. While simple algorithms like Bubble Sort may work for small inputs, they become inefficient as the input size increases. Linearithmic algorithms like Quicksort and Merge Sort should be preferred for better performance on larger scales.

License

This project is licensed under the MIT License.