Quick Sort and Count Sort algorithm analysis in Big O Notation

This exercise focuses on the analysis of two popular algorithms - Quick Sort and Count Sort - using Big O Notation to evaluate their temporal and spatial complexities. The analysis is done through sample code provided in the MainApp.java class which tests each algorithm. The CountSort.java class contains the implementation of Count Sort, while the QuickSort.java class contains the implementation of Quick Sort.

The report discusses the efficiency and scalability concerns of both algorithms and provides a critical comparison of their designs.

In the code:

• MainApp.java – A Main class with a main() method for running. The main() method contains sample code that tests each algorithm.
• CountSort.java – A class containing an implementation of Count Sort.
• QuickSort.java – A class containing an implementation of Quick Sort.

Big O Reference

Terminology

• Temporal complexity
  • How long the algorithm takes to run.
  • Obtained by counting the number of comparisons and the number of copies required.
• Spatial complexity
  • The resources the algorithm requires.
  • Obtained by counting the number of additional array elements necessary to perform the algorithms.

Report preview

• Open the report file to see the full analysis.
  • Page (2)