================================================================================
         DATA STRUCTURES AND ALGORITHMS
         ASSIGNMENT 9: Sorting Algorithm Visualizer & Benchmarker
         State University of Zanzibar (SUZA)
================================================================================

ANTI-PLAGIARISM NOTICE:
This assignment requires LIVE DEMONSTRATION (viva). You must:
1. Explain every function in your code
2. Modify your code on the spot when asked
3. Answer questions about your design choices
4. Submit a HANDWRITTEN analysis document
AI-generated or copied code will result in ZERO marks.

UNIQUE SEED REQUIREMENT:
Use your registration number as the random seed for array generation.
This ensures each student has unique test data.
   srand(YOUR_REG_NUMBER);

================================================================================
PROJECT DESCRIPTION
================================================================================

Build a sorting algorithm visualizer and benchmarker that demonstrates
how different sorting algorithms work and compares their performance.

================================================================================
REQUIREMENTS
================================================================================

PART 1: IMPLEMENT 5 SORTING ALGORITHMS (30 marks)

Each algorithm must be implemented as a separate function:

   void bubbleSort(int arr[], int n);
   void selectionSort(int arr[], int n);
   void insertionSort(int arr[], int n);
   void mergeSort(int arr[], int left, int right);
   void quickSort(int arr[], int low, int high);

Helper functions:
   void merge(int arr[], int left, int mid, int right);
   int partition(int arr[], int low, int high);

All sorting functions must use global counters:
   long comparisons = 0;
   long swaps = 0;

PART 2: VISUAL MODE (25 marks)

For arrays of size <= 20, display each step of the sorting process:

Example (Bubble Sort on [5, 3, 8, 1, 4]):

   === Bubble Sort ===
   Initial: [5, 3, 8, 1, 4]

   Pass 1:
   Compare 5 and 3: SWAP  -> [3, 5, 8, 1, 4]
   Compare 5 and 8: OK    -> [3, 5, 8, 1, 4]
   Compare 8 and 1: SWAP  -> [3, 5, 1, 8, 4]
   Compare 8 and 4: SWAP  -> [3, 5, 1, 4, 8]
   After pass 1: [3, 5, 1, 4, 8]

   Pass 2:
   ...

   Sorted: [1, 3, 4, 5, 8]
   Comparisons: 10, Swaps: 4

For Quick Sort, show pivot selection and partition:
   Pivot: 4
   Before partition: [5, 3, 8, 1, 4]
   After partition:  [3, 1, 4, 8, 5]  (pivot at index 2)

For Merge Sort, show split and merge:
   Split: [5, 3, 8] and [1, 4]
   Merge: [3, 5, 8] + [1, 4] -> [1, 3, 4, 5, 8]

PART 3: BENCHMARK MODE (30 marks)

Test all 5 algorithms on arrays of size: 100, 1000, 5000, 10000

For each size, test on:
a) Random array (use your reg number as seed)
b) Already sorted array
c) Reverse sorted array
d) Array with many duplicates (values 1-10 only)

Record and display:
- Number of comparisons
- Number of swaps (where applicable)
- Execution time in milliseconds

Use clock() for timing:
   #include <time.h>
   clock_t start = clock();
   // sort
   clock_t end = clock();
   double ms = (double)(end - start) * 1000.0 / CLOCKS_PER_SEC;

Output format:
   ================================================================
   BENCHMARK RESULTS (Seed: [YOUR_REG_NUMBER])
   ================================================================
   Array Size: 1000 | Type: Random
   ----------------------------------------------------------------
   Algorithm      | Comparisons | Swaps    | Time (ms)
   ----------------------------------------------------------------
   Bubble Sort    | 499,500     | 251,234  | 12.45
   Selection Sort | 499,500     | 999      | 8.32
   Insertion Sort | 250,123     | 250,123  | 6.78
   Merge Sort     | 8,976       | N/A      | 0.45
   Quick Sort     | 10,234      | 3,456    | 0.38
   ================================================================

PART 4: REPORT GENERATION (15 marks)

Generate a report file "sorting_report.txt" containing:
1. All benchmark results in tabular format
2. Analysis section answering:
   - Which algorithm is fastest for random data?
   - Which is fastest for sorted data?
   - Which has fewest comparisons overall?
   - At what array size does O(n^2) become noticeably slower than O(n log n)?

================================================================================
MENU INTERFACE
================================================================================

   === Sorting Algorithm Visualizer & Benchmarker ===
   Registration Number: [YOUR_REG]

   1. Visual Mode (small arrays, step-by-step)
   2. Benchmark Mode (large arrays, performance comparison)
   3. Single Algorithm Test
   4. Generate Report
   0. Exit

================================================================================
HANDWRITTEN ANALYSIS (Required)
================================================================================

Submit on paper:
1. Time complexity table for all 5 algorithms (best, average, worst)
2. Space complexity for each algorithm
3. Which algorithms are stable? Prove with example.
4. Draw the recursion tree for mergeSort on array of size 8
5. Explain why Quick Sort's worst case is O(n^2) but average is O(n log n)
6. From your benchmark results, at what n does Merge Sort outperform Insertion Sort?

================================================================================
GRADING RUBRIC
================================================================================

| Component                     | Marks |
|-------------------------------|-------|
| 5 sorting algorithms correct  |   30  |
| Visual mode display           |   25  |
| Benchmark mode                |   30  |
| Report generation             |   15  |
| Total                         |  100  |

Viva Demonstration: Required (multiplier: 0 or 1)

================================================================================
VIVA QUESTIONS:
================================================================================
1. Explain the partition algorithm in Quick Sort step by step.
2. Why is Merge Sort O(n log n) in ALL cases?
3. Your benchmark shows [X] - explain why this result makes sense.
4. Change Quick Sort to use median-of-three pivot selection (live).
5. Add Counting Sort to your benchmarker (live).
6. What would happen if you used Quick Sort on an array of all identical elements?

================================================================================