Array Sorting Algorithm Design, Implementation, and Analysis

This repository contains the implementation and analysis of various array sorting algorithms. The project includes tasks related to designing and analyzing a custom sorting algorithm, as well as an experimental study comparing multiple sorting algorithms.

Project Structure

• CountingSort1.py: Implementation of the counting sort algorithm for arrays with distinct elements.
• CountingSort2.py: Modified counting sort algorithm to handle arrays with duplicate elements.
• sort_analysis.py: Code for testing and comparing different sorting algorithms.

Tasks

Task 1: Sorting Algorithm Design and Analysis

Part 1: Distinct Elements

1. Algorithm Design: Implement the CountingSort algorithm to sort an array of distinct integers.
2. Time Complexity Analysis: Analyze the time complexity using O-notation.
3. Space Complexity Analysis: Determine the space complexity of the algorithm.
4. Python Implementation: Implement the algorithm in Python (CountingSort1.py) and test it with an array of 20 distinct elements.

Part 2: Handling Duplicate Elements

1. Algorithm Modification: Modify the CountingSort algorithm to handle arrays with duplicate elements.
2. Time Complexity Analysis: Analyze the time complexity of the modified algorithm.
3. Space Complexity Analysis: Determine the space complexity of the modified algorithm.
4. Python Implementation: Implement the modified algorithm in Python (CountingSort2.py) and test it with an array containing duplicates.

Task 2: Experimental Study on Sorting Algorithms

Part 1: System Development

1. Main Menu: Create a system with a main menu for testing sorting algorithms.
   • Option 1: Test an individual sorting algorithm.
   • Option 2: Test multiple sorting algorithms.
   • Option 3: Exit.
2. Individual Algorithm Testing: Allow the user to select and test one of the following algorithms:
   • Selection sort
   • Insertion sort
   • Merge sort
   • Quick sort
   • Heap sort
   • Counting sort
3. Multiple Algorithm Testing: Test all sorting algorithms using the same array and compare their performance.

Part 2: Data Collection and Analysis

1. Comparison Table: Collect data on the number of comparisons and running time for each sorting algorithm over multiple runs and array sizes.
2. Results Analysis: Analyze the results to compare the performance of different sorting algorithms.

How to Run

1. Clone the repository.
2. Run the individual Python files to test specific parts of the project:
   • python CountingSort1.py
   • python CountingSort2.py
   • python sort_analysis.py

License

This project is licensed under the MIT License.

Contact

For any questions or feedback, please comment on repository.