================================================================================
         DATA STRUCTURES AND ALGORITHMS
         HOMEWORK 9: Basic Sorting Algorithms
         State University of Zanzibar (SUZA)
================================================================================

SUBMISSION REQUIREMENTS:
- Submit .c source code file(s) AND handwritten work (scanned/photographed)
- Code must compile and run without errors
- Include your Name, Registration Number, and Date at the top of each file
- VIVA REQUIRED: You must demonstrate and explain your code in person

INTEGRITY DECLARATION:
"I declare that this work is my own. I understand that submitting
AI-generated code or copied work will result in zero marks and
disciplinary action."

Signature: ________________  Date: ________________

================================================================================
PROBLEM 1: Manual Sorting Traces (25 marks) [HANDWRITTEN ONLY]
================================================================================

Given the array: [38, 27, 43, 3, 9, 82, 10]

Trace EACH of the following sorting algorithms step by step:

a) Bubble Sort:
   Show the array after EACH comparison and swap.
   Show the array after each complete pass.
   How many passes? How many comparisons? How many swaps?

b) Selection Sort:
   For each iteration, show:
   - The unsorted portion
   - The minimum found
   - The swap performed
   - The array after the swap

c) Insertion Sort:
   For each element being inserted, show:
   - The key being inserted
   - The comparisons and shifts made
   - The array after insertion

Submit all traces on paper with clear labels.

================================================================================
PROBLEM 2: Implement and Count (30 marks)
================================================================================

Implement all three sorting algorithms with comparison and swap counting:

   void bubbleSort(int arr[], int n, int *comparisons, int *swaps);
   void selectionSort(int arr[], int n, int *comparisons, int *swaps);
   void insertionSort(int arr[], int n, int *comparisons, int *swaps);

Requirements:
a) Each function must count comparisons (each time two elements are compared)
   and swaps (each time two elements exchange positions).

b) Test on the array from Problem 1: [38, 27, 43, 3, 9, 82, 10]
   Print the sorted array and counts.
   Verify your counts match your handwritten traces.

c) Print the array after EACH pass/iteration to show progress:
   Pass 1: [27, 38, 3, 9, 43, 10, 82]
   Pass 2: ...

================================================================================
PROBLEM 3: Performance Comparison (30 marks)
================================================================================

Compare the three sorting algorithms on different input types.

Create three test arrays of size 20:
a) Already sorted: [1, 2, 3, ..., 20]
b) Reverse sorted: [20, 19, 18, ..., 1]
c) Random: Use your registration number digits + random values

For each array type and each algorithm, record:
   - Number of comparisons
   - Number of swaps

Fill in this table:

| Algorithm      | Sorted (C/S) | Reverse (C/S) | Random (C/S) |
|----------------|-------------|----------------|---------------|
| Bubble Sort    |      /      |       /        |       /       |
| Selection Sort |      /      |       /        |       /       |
| Insertion Sort |      /      |       /        |       /       |

Questions to answer:
1. Which algorithm performs best on already-sorted data? Why?
2. Which algorithm performs worst on reverse-sorted data? Why?
3. Which algorithm has the fewest swaps overall? Why?

[HANDWRITTEN] Write your analysis (minimum 5 sentences).

================================================================================
PROBLEM 4: Optimized Bubble Sort (15 marks)
================================================================================

a) Implement optimized bubble sort that:
   - Stops early if no swaps in a pass (already sorted)
   - Tracks the last swap position to reduce comparisons

   void bubbleSortOptimized(int arr[], int n, int *comparisons, int *swaps);

b) Compare with standard bubble sort on the sorted array [1,2,...,20]:
   Standard:  comparisons=___, swaps=___
   Optimized: comparisons=___, swaps=___

c) [HANDWRITTEN] Explain why the optimization works and what the best-case
   time complexity becomes.

================================================================================
VIVA QUESTIONS (be prepared to answer):
================================================================================
1. Sort this array by hand using [algorithm chosen by instructor]: [5, 1, 8, 3, 2]
2. What is the time complexity of Bubble Sort? Best, average, worst case?
3. Which of these three algorithms is stable? What does stability mean?
4. Can you modify Selection Sort to sort in descending order? Do it live.
5. Why does Insertion Sort perform well on nearly-sorted arrays?
6. What is the space complexity of each algorithm?

================================================================================
GRADING RUBRIC:
   Problem 1 (Handwritten Traces):   25 marks
   Problem 2 (Implementation):       30 marks
   Problem 3 (Comparison + Analysis):30 marks
   Problem 4 (Optimization):         15 marks
   Viva Demonstration:               Required (multiplier: 0 or 1)
   Late Penalty: -10% per day
================================================================================