================================================================================
         DATA STRUCTURES AND ALGORITHMS (C)
         PRACTICAL LAB SESSION 5: Sorting Algorithms
         State University of Zanzibar (SUZA)
================================================================================

OBJECTIVES:
- Implement and trace basic sorting algorithms
- Implement advanced sorting algorithms (Merge Sort, Quick Sort)
- Analyze and compare sorting algorithm performance
- Understand time complexity and stability

================================================================================
PART A: BASIC SORTING ALGORITHMS
================================================================================

1. Bubble Sort:
   void bubbleSort(int arr[], int n);
   Print array after each pass.
   Test: [64,34,25,12,22,11,90]
   Trace: Show each comparison and swap.

2. Selection Sort:
   void selectionSort(int arr[], int n);
   Print array after each selection.
   Test: [64,25,12,22,11]
   Trace: Show minimum found in each pass.

3. Insertion Sort:
   void insertionSort(int arr[], int n);
   Print array after each insertion.
   Test: [12,11,13,5,6]
   Trace: Show element being inserted into correct position.

4. Bubble Sort with Early Termination:
   Optimize bubble sort to stop if no swaps in a pass.
   void bubbleSortOptimized(int arr[], int n);
   Test with already sorted array to verify it stops early.

5. Sort in Descending Order:
   Modify any sorting algorithm to sort in descending order.
   void sortDescending(int arr[], int n);
   Test: [3,1,4,1,5,9] -> [9,5,4,3,1,1]

================================================================================
PART B: ADVANCED SORTING ALGORITHMS
================================================================================

6. Merge Sort:
   void mergeSort(int arr[], int left, int right);
   void merge(int arr[], int left, int mid, int right);
   Print subarrays being merged at each step.
   Test: [38,27,43,3,9,82,10]

7. Quick Sort:
   void quickSort(int arr[], int low, int high);
   int partition(int arr[], int low, int high);
   Print pivot and partitioned array at each step.
   Test: [10,7,8,9,1,5]

8. Quick Sort with Different Pivot Strategies:
   a) First element as pivot
   b) Last element as pivot
   c) Median of three as pivot
   Compare results on same array.

9. Counting Sort:
   void countingSort(int arr[], int n, int range);
   Test: [4,2,2,8,3,3,1] -> [1,2,2,3,3,4,8]
   Only works for non-negative integers within known range.

10. Sort Strings Alphabetically:
    void sortStrings(char arr[][50], int n);
    Use any sorting algorithm with strcmp.
    Test: ["banana","apple","cherry","date"] -> ["apple","banana","cherry","date"]

================================================================================
PART C: SORTING ANALYSIS
================================================================================

11. Count Comparisons and Swaps:
    Modify Bubble, Selection, and Insertion sort to count comparisons and swaps.
    int bubbleSortCount(int arr[], int n, int *comparisons, int *swaps);
    Compare counts for same array across all three algorithms.

12. Timing Sort Algorithms:
    Use clock() from <time.h> to measure execution time.
    Compare Bubble Sort, Selection Sort, Insertion Sort on arrays of size 1000.
    #include <time.h>
    clock_t start = clock();
    // sort
    clock_t end = clock();
    double time = (double)(end - start) / CLOCKS_PER_SEC;

13. Best/Worst/Average Case Analysis:
    Run each sorting algorithm on:
    a) Already sorted array [1,2,3,...,n]
    b) Reverse sorted array [n,n-1,...,2,1]
    c) Random array
    Record comparisons for each. Verify theoretical complexity.

14. Stability Test:
    Create array of structs { int key; char label; }
    Sort by key. Check if elements with equal keys maintain original order.
    Test: [(3,'a'),(1,'b'),(3,'c'),(2,'d')] -> [(1,'b'),(2,'d'),(3,'a'),(3,'c')]
    Which sorts are stable?

15. Sort Large Dataset:
    Generate random array of 10000 elements.
    Compare Merge Sort vs Quick Sort vs Insertion Sort.
    Display timing results.

================================================================================
PART D: EXTRA PRACTICE (LeetCode / HackerRank Style)
================================================================================

16. [Easy] Sort Colors (LeetCode 75)
    Array with values 0, 1, 2 only. Sort in-place (one pass).
    void sortColors(int arr[], int n);
    Test: [2,0,2,1,1,0] -> [0,0,1,1,2,2]
    Hint: Dutch National Flag problem - use three pointers.

17. [Easy] Merge Sorted Array (LeetCode 88)
    Merge nums2 into nums1 (nums1 has enough space).
    void merge(int nums1[], int m, int nums2[], int n);
    Test: [1,2,3,0,0,0] m=3, [2,5,6] n=3 -> [1,2,2,3,5,6]

18. [Medium] Kth Largest Element (LeetCode 215)
    Find kth largest element in unsorted array.
    int findKthLargest(int arr[], int n, int k);
    Test: [3,2,1,5,6,4] k=2 -> 5
    Hint: Use partition (Quick Select).

19. [Medium] Sort List (LeetCode 148)
    Sort a linked list using merge sort.
    struct Node* sortList(struct Node *head);

20. [Medium] Wiggle Sort II (LeetCode 324)
    Reorder array such that nums[0]<nums[1]>nums[2]<nums[3]...
    void wiggleSort(int arr[], int n);
    Test: [1,5,1,1,6,4] -> [1,4,1,5,1,6]

21. [HackerRank] Insertion Sort Advanced Analysis
    Count the number of shifts (inversions) Insertion Sort makes.
    long countInversions(int arr[], int n);
    Test: [2,1,3,1,2] -> 4 inversions

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