# Module 7: Searching & Sorting By the end of this module, students will be able to: - Understand fundamental searching algorithms and their applications - Implement linear and binary search algorithms - Understand various sorting algorithms and their characteristics - Analyze time and space complexity of searching and sorting algorithms - Compare different algorithms and choose appropriate ones for specific problems - Implement sorting algorithms in C - Optimize searching and sorting operations - Apply searching and sorting to solve real-world problems # 1. Introduction to Searching ### 1.1 What is Searching? **Searching** is the process of finding a particular element or checking if an element exists in a data structure (array, linked list, tree, etc.). **Real-World Analogies:** - Finding a book in a library - Searching for a contact in your phone - Looking up a word in a dictionary - Finding a file on your computer **Types of Searching:** 1. **Linear Search** - Sequential search through elements 2. **Binary Search** - Divide and conquer approach (requires sorted data) 3. **Jump Search** - Jumping ahead by fixed steps 4. **Interpolation Search** - Improved binary search for uniformly distributed data 5. **Exponential Search** - Finding range then binary search *Note: There's actually a lot more searching algorithms, but we'll focus on the most common ones.* ### 1.2 Why Study Searching Algorithms? **Importance:** - One of the most common operations in programming - Critical for database queries - Essential for data retrieval systems - Foundation for more complex algorithms - Performance impact on large datasets **Performance Metrics:** - **Best Case:** Minimum number of comparisons - **Average Case:** Expected number of comparisons - **Worst Case:** Maximum number of comparisons - **Space Complexity:** Extra memory required # 2. Linear Search ### 2.1 Concept **Linear Search** (also called Sequential Search) checks every element in the array sequentially until the target is found or the end is reached. **How it works:** 1. Start from the first element 2. Compare each element with the target 3. If match found, return the position 4. If end reached without match, return -1 **Visual Representation:** ``` Array: [10, 25, 30, 15, 40, 35] Target: 15 Step 1: Check 10 ≠ 15 Step 2: Check 25 ≠ 15 Step 3: Check 30 ≠ 15 Step 4: Check 15 = 15 ✓ Found at index 3! ``` ### 2.2 Implementation #### Basic Linear Search ```c #include int linearSearch(int arr[], int n, int target) { for (int i = 0; i < n; i++) { if (arr[i] == target) { return i; // Return index if found } } return -1; // Return -1 if not found } int main() { int arr[] = {10, 25, 30, 15, 40, 35}; int n = sizeof(arr) / sizeof(arr[0]); int target = 15; int result = linearSearch(arr, n, target); if (result != -1) { printf("Element %d found at index %d\n", target, result); } else { printf("Element %d not found\n", target); } return 0; } ``` #### Linear Search with Count ```c int linearSearchCount(int arr[], int n, int target, int *comparisons) { *comparisons = 0; for (int i = 0; i < n; i++) { (*comparisons)++; if (arr[i] == target) { return i; } } return -1; } // Usage int main() { int arr[] = {10, 25, 30, 15, 40, 35}; int n = sizeof(arr) / sizeof(arr[0]); int target = 15; int comparisons = 0; int result = linearSearchCount(arr, n, target, &comparisons); printf("Result: %d\n", result); printf("Comparisons made: %d\n", comparisons); return 0; } ``` #### Find All Occurrences ```c void linearSearchAll(int arr[], int n, int target) { int found = 0; printf("Element %d found at indices: ", target); for (int i = 0; i < n; i++) { if (arr[i] == target) { printf("%d ", i); found = 1; } } if (!found) { printf("Not found"); } printf("\n"); } int main() { int arr[] = {10, 25, 30, 25, 40, 25}; int n = sizeof(arr) / sizeof(arr[0]); linearSearchAll(arr, n, 25); // Output: Element 25 found at indices: 1 3 5 return 0; } ``` ### 2.3 Complexity Analysis | Case | Time Complexity | Description | |------|----------------|-------------| | Best Case | O(1) | Element found at first position | | Average Case | O(n) | Element found in middle | | Worst Case | O(n) | Element at last position or not found | | Space Complexity | O(1) | No extra space needed | **Visualization:** ``` Best Case (1 comparison): [15, 25, 30, ...] → Found immediately! Average Case (n/2 comparisons): [10, 25, 30, 15, ...] → Found in middle Worst Case (n comparisons): [10, 25, 30, 40, 35, 15] → Found at end or [10, 25, 30, 40, 35, 20] → Not found (checked all) ``` ### 2.4 Advantages and Disadvantages **Advantages:** - Simple to implement - Works on unsorted arrays - No preprocessing required - Works well for small datasets - No extra memory needed **Disadvantages:** - Slow for large datasets - Inefficient compared to other algorithms - Time complexity increases linearly **When to Use:** - Small datasets (n < 100) - Unsorted data - When simplicity is priority - When data changes frequently # 3. Binary Search ### 3.1 Concept **Binary Search** is a fast search algorithm that works on sorted arrays by repeatedly dividing the search interval in half. **Prerequisites:** - Array must be sorted - Random access to elements (arrays work well) **How it works:** 1. Compare target with middle element 2. If match found, return position 3. If target is smaller, search left half 4. If target is larger, search right half 5. Repeat until found or search space is empty **Visual Representation:** ``` Sorted Array: [10, 15, 25, 30, 35, 40, 50] Target: 35 Step 1: Check middle (30) [10, 15, 25, 30, | 35, 40, 50] ^ 35 > 30, search right half Step 2: Check middle of right half (40) [35, 40, 50] ^ 35 < 40, search left half Step 3: Check middle of remaining (35) [35] ^ 35 = 35, Found at index 4! ``` ### 3.2 Implementation #### Iterative Binary Search ```c #include int binarySearch(int arr[], int n, int target) { int left = 0; int right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // Avoid overflow // Check if target is at mid if (arr[mid] == target) { return mid; } // If target is greater, ignore left half if (arr[mid] < target) { left = mid + 1; } // If target is smaller, ignore right half else { right = mid - 1; } } return -1; // Element not found } int main() { int arr[] = {10, 15, 25, 30, 35, 40, 50}; int n = sizeof(arr) / sizeof(arr[0]); int target = 35; int result = binarySearch(arr, n, target); if (result != -1) { printf("Element %d found at index %d\n", target, result); } else { printf("Element %d not found\n", target); } return 0; } ``` **Why `mid = left + (right - left) / 2`?** ```c // This can overflow for large values: int mid = (left + right) / 2; // This is safer: int mid = left + (right - left) / 2; // Example of overflow: // left = 2^30, right = 2^30 // (left + right) = 2^31 → overflow in 32-bit int // left + (right - left) / 2 = no overflow ``` #### Recursive Binary Search ```c int binarySearchRecursive(int arr[], int left, int right, int target) { // Base case: element not found if (left > right) { return -1; } int mid = left + (right - left) / 2; // Element found at mid if (arr[mid] == target) { return mid; } // Search in left half if (arr[mid] > target) { return binarySearchRecursive(arr, left, mid - 1, target); } // Search in right half return binarySearchRecursive(arr, mid + 1, right, target); } // Wrapper function int binarySearch(int arr[], int n, int target) { return binarySearchRecursive(arr, 0, n - 1, target); } ``` #### Binary Search with Comparison Count ```c int binarySearchCount(int arr[], int n, int target, int *comparisons) { int left = 0; int right = n - 1; *comparisons = 0; while (left <= right) { int mid = left + (right - left) / 2; (*comparisons)++; if (arr[mid] == target) { return mid; } if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } int main() { int arr[] = {10, 15, 25, 30, 35, 40, 50, 60, 70, 80}; int n = sizeof(arr) / sizeof(arr[0]); int target = 35; int comparisons = 0; int result = binarySearchCount(arr, n, target, &comparisons); printf("Result: %d\n", result); printf("Comparisons: %d\n", comparisons); printf("Linear search would need: %d comparisons\n", result + 1); return 0; } ``` ### 3.3 Complexity Analysis | Case | Time Complexity | Description | |------|----------------|-------------| | Best Case | O(1) | Element found at middle | | Average Case | O(log n) | Typical search | | Worst Case | O(log n) | Element at edge or not found | | Space Complexity | O(1) iterative, O(log n) recursive | Stack space for recursion | **Comparison with Linear Search:** ``` Array size: 1,000,000 elements Linear Search: - Average: 500,000 comparisons - Worst: 1,000,000 comparisons Binary Search: - Average: 20 comparisons - Worst: 20 comparisons Speed improvement: ~50,000x faster! ``` **Growth Comparison:** ``` n Linear Search Binary Search 10 10 4 100 100 7 1,000 1,000 10 10,000 10,000 14 100,000 100,000 17 ``` ### 3.4 Binary Search Variations #### Find First Occurrence ```c int findFirstOccurrence(int arr[], int n, int target) { int left = 0; int right = n - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; right = mid - 1; // Continue searching in left half } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } ``` **Visual Example:** ``` Array: [10, 20, 20, 20, 30, 40] Target: 20 Regular binary search might return index 1, 2, or 3 First occurrence will always return index 1 ``` #### Find Last Occurrence ```c int findLastOccurrence(int arr[], int n, int target) { int left = 0; int right = n - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; left = mid + 1; // Continue searching in right half } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } ``` #### Count Occurrences ```c int countOccurrences(int arr[], int n, int target) { int first = findFirstOccurrence(arr, n, target); if (first == -1) { return 0; // Element not found } int last = findLastOccurrence(arr, n, target); return last - first + 1; } int main() { int arr[] = {10, 20, 20, 20, 30, 40}; int n = sizeof(arr) / sizeof(arr[0]); int count = countOccurrences(arr, n, 20); printf("20 occurs %d times\n", count); // Output: 20 occurs 3 times return 0; } ``` #### Find Insert Position ```c int searchInsertPosition(int arr[], int n, int target) { int left = 0; int right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; // Position where target should be inserted } int main() { int arr[] = {10, 20, 30, 50, 60}; int n = sizeof(arr) / sizeof(arr[0]); printf("Insert 25 at position: %d\n", searchInsertPosition(arr, n, 25)); printf("Insert 35 at position: %d\n", searchInsertPosition(arr, n, 35)); printf("Insert 70 at position: %d\n", searchInsertPosition(arr, n, 70)); return 0; } ``` ### 3.5 When to Use Binary Search **Use Binary Search when:** - Data is sorted - Need fast searching (large datasets) - Data doesn't change frequently - Random access is available (arrays) **Don't use Binary Search when:** - Data is unsorted (sorting overhead) - Small datasets (linear search is simpler) - Data changes frequently - Sequential access only (linked lists) # 4. Introduction to Sorting ### 4.1 What is Sorting? **Sorting** is the process of arranging elements in a specific order (ascending or descending). **Why Sort?** 1. **Faster Searching:** Enables binary search 2. **Data Organization:** Makes data easier to understand 3. **Algorithm Requirements:** Many algorithms require sorted input 4. **Data Presentation:** Better user experience 5. **Finding Duplicates:** Easier with sorted data **Real-World Examples:** - Sorting contacts alphabetically - Arranging files by date - Organizing products by price - Ranking search results - Leaderboards in games ### 4.2 Sorting Algorithm Categories **1. By Complexity:** - **Simple:** Bubble, Selection, Insertion Sort - O(n²) - **Efficient:** Merge, Quick, Heap Sort - O(n log n) - **Special:** Counting, Radix, Bucket Sort - O(n) **2. By Method:** - **Comparison-based:** Compare elements to sort - **Non-comparison:** Use element properties **3. By Stability:** - **Stable:** Preserves relative order of equal elements - **Unstable:** May change relative order **4. By Memory:** - **In-place:** O(1) extra space - **Out-of-place:** O(n) extra space ### 4.3 Sorting Algorithm Comparison Table | Algorithm | Best | Average | Worst | Space | Stable | Method | |-----------|------|---------|-------|-------|--------|--------| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Exchange | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Selection | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Insertion | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Divide & Conquer | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Divide & Conquer | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Selection | | Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Non-comparison | | Radix Sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Yes | Non-comparison | # 5. Simple Sorting Algorithms ### 5.1 Bubble Sort #### Concept **Bubble Sort** repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. **How it works:** 1. Compare adjacent elements 2. Swap if in wrong order 3. Repeat for all elements 4. After each pass, largest element "bubbles" to the end **Visual Example:** ``` Initial: [64, 34, 25, 12, 22, 11, 90] Pass 1: [34, 64, 25, 12, 22, 11, 90] → 64 > 34, swap [34, 25, 64, 12, 22, 11, 90] → 64 > 25, swap [34, 25, 12, 64, 22, 11, 90] → 64 > 12, swap [34, 25, 12, 22, 64, 11, 90] → 64 > 22, swap [34, 25, 12, 22, 11, 64, 90] → 64 > 11, swap [34, 25, 12, 22, 11, 64, 90] → 64 < 90, no swap → 90 is in correct position! Pass 2: [25, 34, 12, 22, 11, 64, 90] ...continues until sorted... Final: [11, 12, 22, 25, 34, 64, 90] ``` #### Implementation **Basic Bubble Sort:** ```c #include void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // Last i elements are already in place for (int j = 0; j < n - i - 1; j++) { // Swap if element is greater than next if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, n); bubbleSort(arr, n); printf("Sorted array: "); printArray(arr, n); return 0; } ``` **Optimized Bubble Sort (with flag):** ```c void bubbleSortOptimized(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; // Flag to detect if any swap happened for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = 1; } } // If no swaps, array is sorted if (swapped == 0) { break; } } } ``` **Why Optimization Helps:** ``` Nearly sorted array: [11, 12, 22, 25, 34, 64, 63] Without optimization: 6 passes (always) With optimization: 2 passes (stops when no swaps) For already sorted array: [11, 12, 22, 25, 34, 64, 90] Without: O(n²) With: O(n) - only 1 pass! ``` **Bubble Sort with Visualization:** ```c void bubbleSortVisualize(int arr[], int n) { printf("\n=== Bubble Sort Visualization ===\n"); for (int i = 0; i < n - 1; i++) { printf("\nPass %d:\n", i + 1); int swapped = 0; for (int j = 0; j < n - i - 1; j++) { printf(" Compare %d and %d: ", arr[j], arr[j + 1]); if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; printf("Swap → "); swapped = 1; } else { printf("No swap → "); } printArray(arr, n); } if (swapped == 0) { printf(" Array is sorted!\n"); break; } } } ``` #### Complexity Analysis **Time Complexity:** - Best Case: O(n) - already sorted (with optimization) - Average Case: O(n²) - Worst Case: O(n²) - reverse sorted **Space Complexity:** O(1) - in-place sorting **Comparisons and Swaps:** ``` For array of size n: - Comparisons: n(n-1)/2 - Swaps (worst case): n(n-1)/2 Example with n=5: - Comparisons: 5×4/2 = 10 - Maximum swaps: 10 ``` #### When to Use **Use Bubble Sort when:** - Educational purposes - Very small datasets (n < 10) - Nearly sorted data (with optimization) - Simplicity is priority **Don't use when:** - Large datasets - Performance is critical - Production code ### 5.2 Selection Sort #### Concept **Selection Sort** divides the array into sorted and unsorted parts, repeatedly selects the minimum element from unsorted part and places it at the beginning. **How it works:** 1. Find minimum element in unsorted part 2. Swap with first element of unsorted part 3. Move boundary of sorted part 4. Repeat until array is sorted **Visual Example:** ``` Initial: [64, 25, 12, 22, 11] ↑ unsorted part Pass 1: Find minimum (11) [64, 25, 12, 22, 11] ↑ minimum [11, 25, 12, 22, 64] → swap 11 and 64 ↑ ↑ unsorted part sorted Pass 2: Find minimum (12) [11, 25, 12, 22, 64] ↑ minimum [11, 12, 25, 22, 64] → swap 12 and 25 ↑ ↑ ↑ unsorted sorted Pass 3: Find minimum (22) [11, 12, 25, 22, 64] ↑ minimum [11, 12, 22, 25, 64] → swap 22 and 25 Pass 4: Find minimum (25) [11, 12, 22, 25, 64] ↑ already minimum No swap needed Final: [11, 12, 22, 25, 64] ``` #### Implementation ```c #include void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // Find minimum element in unsorted part int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // Swap minimum with first element of unsorted part if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, n); selectionSort(arr, n); printf("Sorted array: "); printArray(arr, n); return 0; } ``` **Selection Sort with Visualization:** ```c void selectionSortVisualize(int arr[], int n) { printf("\n=== Selection Sort Visualization ===\n"); for (int i = 0; i < n - 1; i++) { printf("\nPass %d: ", i + 1); // Print sorted part printf("Sorted["); for (int k = 0; k < i; k++) { printf("%d", arr[k]); if (k < i - 1) printf(", "); } printf("] "); int minIndex = i; printf("Finding minimum in unsorted part...\n"); for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } printf(" Minimum: %d at index %d\n", arr[minIndex], minIndex); if (minIndex != i) { printf(" Swapping %d and %d\n", arr[i], arr[minIndex]); int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } else { printf(" Already in correct position\n"); } printf(" Result: "); printArray(arr, n); } } ``` **Finding Maximum (Descending Order):** ```c void selectionSortDescending(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // Find maximum element in unsorted part int maxIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] > arr[maxIndex]) { // Changed to > maxIndex = j; } } // Swap if (maxIndex != i) { int temp = arr[i]; arr[i] = arr[maxIndex]; arr[maxIndex] = temp; } } } ``` #### Complexity Analysis **Time Complexity:** - Best Case: O(n²) - Average Case: O(n²) - Worst Case: O(n²) - **Always O(n²)** regardless of input! **Space Complexity:** O(1) - in-place sorting **Comparisons and Swaps:** ``` For array of size n: - Comparisons: n(n-1)/2 (always) - Swaps: O(n) - maximum n-1 swaps Advantage: Minimum number of swaps! ``` **Comparison with Bubble Sort:** ``` Array: [5, 4, 3, 2, 1] Bubble Sort: - Comparisons: 10 - Swaps: 10 Selection Sort: - Comparisons: 10 - Swaps: 2 (only swap 5↔1, then 4↔2) → Selection Sort better when swaps are expensive! ``` #### Stability Issue Selection Sort is **NOT stable**: ``` Input: [4a, 3, 4b, 2] Output: [2, 3, 4b, 4a] ← Order of 4a and 4b changed! Why? When we swap 4a with 2, 4b comes before 4a ``` #### When to Use **Use Selection Sort when:** - Swaps are expensive (writing to flash memory) - Small datasets - Memory writes must be minimized - Simplicity needed **Don't use when:** - Stability required - Large datasets - Performance critical ### 5.3 Insertion Sort #### Concept **Insertion Sort** builds the final sorted array one item at a time by inserting each element into its correct position. **Analogy:** Like sorting playing cards in your hand: - Pick one card at a time - Insert it into correct position among sorted cards - Shift other cards to make space **How it works:** 1. Start with second element 2. Compare with elements in sorted part (left side) 3. Shift larger elements to the right 4. Insert element in correct position 5. Repeat for all elements **Visual Example:** ``` Initial: [12, 11, 13, 5, 6] Pass 1: Insert 11 [12, 11, 13, 5, 6] ↑ ↑ sorted | to insert 12 > 11, shift 12 right [11, 12, 13, 5, 6] ↑ ↑ sorted Pass 2: Insert 13 [11, 12, 13, 5, 6] ↑ ↑ ↑ sorted | to insert 13 > 12, already in position [11, 12, 13, 5, 6] ↑ ↑ ↑ sorted Pass 3: Insert 5 [11, 12, 13, 5, 6] ↑ ↑ ↑ ↑ sorted | to insert 13 > 5, shift right → [11, 12, 13, 13, 6] 12 > 5, shift right → [11, 12, 12, 13, 6] 11 > 5, shift right → [11, 11, 12, 13, 6] Insert 5 at position 0 → [5, 11, 12, 13, 6] Pass 4: Insert 6 [5, 11, 12, 13, 6] ↑ ↑ ↑ ↑ ↑ sorted | to insert 13 > 6, shift right → [5, 11, 12, 13, 13] 12 > 6, shift right → [5, 11, 12, 12, 13] 11 > 6, shift right → [5, 11, 11, 12, 13] 5 < 6, insert at position 1 → [5, 6, 11, 12, 13] Final: [5, 6, 11, 12, 13] ``` #### Implementation **Basic Insertion Sort:** ```c #include void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; // Element to be inserted int j = i - 1; // Move elements greater than key one position ahead while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // Insert key at correct position arr[j + 1] = key; } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, n); insertionSort(arr, n); printf("Sorted array: "); printArray(arr, n); return 0; } ``` **Insertion Sort with Visualization:** ```c void insertionSortVisualize(int arr[], int n) { printf("\n=== Insertion Sort Visualization ===\n"); printf("Initial: "); printArray(arr, n); for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; printf("\nPass %d: Insert %d\n", i, key); printf(" Sorted part: ["); for (int k = 0; k < i; k++) { printf("%d", arr[k]); if (k < i - 1) printf(", "); } printf("]\n"); int shifts = 0; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; shifts++; } arr[j + 1] = key; printf(" Shifts: %d\n", shifts); printf(" Result: "); printArray(arr, n); } } ``` **Descending Order:** ```c void insertionSortDescending(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // Change condition to arr[j] < key while (j >= 0 && arr[j] < key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } ``` **Binary Insertion Sort (Optimization):** ```c // Find position using binary search int binarySearch(int arr[], int item, int low, int high) { while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == item) { return mid + 1; } else if (arr[mid] < item) { low = mid + 1; } else { high = mid - 1; } } return low; } void binaryInsertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; // Find position using binary search int pos = binarySearch(arr, key, 0, i - 1); // Shift elements for (int j = i - 1; j >= pos; j--) { arr[j + 1] = arr[j]; } // Insert key arr[pos] = key; } } ``` **Insertion Sort for Linked List:** ```c struct Node { int data; struct Node *next; }; void sortedInsert(struct Node **head, struct Node *newNode) { // If list is empty or new node should be first if (*head == NULL || (*head)->data >= newNode->data) { newNode->next = *head; *head = newNode; return; } // Find position to insert struct Node *current = *head; while (current->next != NULL && current->next->data < newNode->data) { current = current->next; } newNode->next = current->next; current->next = newNode; } void insertionSortList(struct Node **head) { struct Node *sorted = NULL; struct Node *current = *head; while (current != NULL) { struct Node *next = current->next; sortedInsert(&sorted, current); current = next; } *head = sorted; } ``` #### Complexity Analysis **Time Complexity:** - Best Case: O(n) - already sorted - Average Case: O(n²) - Worst Case: O(n²) - reverse sorted **Space Complexity:** O(1) - in-place sorting **Detailed Analysis:** ``` Best Case (sorted): [1, 2, 3, 4, 5] - Comparisons: n-1 (each element compared once) - Shifts: 0 - Time: O(n) Worst Case (reverse sorted): [5, 4, 3, 2, 1] - Comparisons: 1+2+3+...+(n-1) = n(n-1)/2 - Shifts: Same as comparisons - Time: O(n²) Average Case (random): - Comparisons: ~n²/4 - Shifts: ~n²/4 - Time: O(n²) ``` **Performance on Different Inputs:** ```c void testInsertionSort() { // Already sorted int sorted[] = {1, 2, 3, 4, 5}; printf("Sorted array: Fast! O(n)\n"); // Reverse sorted int reverse[] = {5, 4, 3, 2, 1}; printf("Reverse array: Slow! O(n²)\n"); // Nearly sorted int nearlySorted[] = {1, 2, 4, 3, 5}; printf("Nearly sorted: Fast! O(n)\n"); // Few elements out of place int fewMoves[] = {2, 1, 3, 4, 5}; printf("Few out of place: Fast!\n"); } ``` #### Advantages 1. **Simple implementation** 2. **Stable** - preserves relative order 3. **In-place** - O(1) extra space 4. **Adaptive** - O(n) for nearly sorted data 5. **Online** - can sort as data arrives **Stability Example:** ``` Input: [4a, 3, 4b, 2] Output: [2, 3, 4a, 4b] ← Order preserved! ``` #### When to Use **Use Insertion Sort when:** - Small datasets (n < 50) - Nearly sorted data - Stability required - Online sorting (data arriving in real-time) - Linked lists (no shifting overhead) **Don't use when:** - Large datasets - Random data - Performance critical **Real-World Applications:** 1. Sorting small files 2. Hybrid sorting (used in TimSort) 3. Online algorithms 4. Sorting linked lists # 6. Efficient Sorting Algorithms ### 6.1 Merge Sort #### Concept **Merge Sort** is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves. **Divide and Conquer Strategy:** 1. **Divide:** Split array into two halves 2. **Conquer:** Recursively sort each half 3. **Combine:** Merge the two sorted halves **Visual Example:** ``` Initial Array: [38, 27, 43, 3, 9, 82, 10] DIVIDE Phase: [38, 27, 43, 3, 9, 82, 10] / \ [38, 27, 43, 3] [9, 82, 10] / \ / \ [38, 27] [43, 3] [9, 82] [10] / \ / \ / \ | [38] [27] [43] [3] [9] [82] [10] MERGE Phase: [38] [27] [43] [3] [9] [82] [10] \ / \ / \ / | [27, 38] [3, 43] [9, 82] [10] \ / \ / [3, 27, 38, 43] [9, 10, 82] \ / [3, 9, 10, 27, 38, 43, 82] ``` #### Implementation **Merge Sort Algorithm:** ```c #include #include // Merge two sorted subarrays void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; // Size of left subarray int n2 = right - mid; // Size of right subarray // Create temporary arrays int *L = (int*)malloc(n1 * sizeof(int)); int *R = (int*)malloc(n2 * sizeof(int)); // Copy data to temporary arrays for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } // Merge the temporary arrays back int i = 0; // Initial index of left subarray int j = 0; // Initial index of right subarray int k = left; // Initial index of merged array while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // Copy remaining elements of L[] while (i < n1) { arr[k] = L[i]; i++; k++; } // Copy remaining elements of R[] while (j < n2) { arr[k] = R[j]; j++; k++; } free(L); free(R); } // Main merge sort function void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // Sort first half mergeSort(arr, left, mid); // Sort second half mergeSort(arr, mid + 1, right); // Merge the sorted halves merge(arr, left, mid, right); } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {38, 27, 43, 3, 9, 82, 10}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, n); mergeSort(arr, 0, n - 1); printf("Sorted array: "); printArray(arr, n); return 0; } ``` **Merge Sort with Visualization:** ```c void mergeSortVisualize(int arr[], int left, int right, int depth) { if (left < right) { // Print indentation based on recursion depth for (int i = 0; i < depth; i++) printf(" "); printf("Divide: ["); for (int i = left; i <= right; i++) { printf("%d", arr[i]); if (i < right) printf(", "); } printf("]\n"); int mid = left + (right - left) / 2; mergeSortVisualize(arr, left, mid, depth + 1); mergeSortVisualize(arr, mid + 1, right, depth + 1); merge(arr, left, mid, right); // Print result after merge for (int i = 0; i < depth; i++) printf(" "); printf("Merge: ["); for (int i = left; i <= right; i++) { printf("%d", arr[i]); if (i < right) printf(", "); } printf("]\n"); } } ``` **Iterative Merge Sort:** ```c void mergeSortIterative(int arr[], int n) { // Start with merge subarrays of size 1, then 2, 4, 8, ... for (int currSize = 1; currSize < n; currSize *= 2) { // Pick starting index of left sub array for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) { // Find ending point of left subarray int mid = leftStart + currSize - 1; // Find ending point of right subarray int rightEnd = (leftStart + 2 * currSize - 1 < n - 1) ? leftStart + 2 * currSize - 1 : n - 1; // Merge subarrays if (mid < rightEnd) { merge(arr, leftStart, mid, rightEnd); } } } } ``` #### Complexity Analysis **Time Complexity:** - Best Case: O(n log n) - Average Case: O(n log n) - Worst Case: O(n log n) - **Always O(n log n)!** **Space Complexity:** O(n) - requires temporary arrays **Why O(n log n)?** ``` Tree height: log₂(n) levels Work at each level: n comparisons/copies Total work = height × work per level = log₂(n) × n = O(n log n) Example with n=8: Level 0: [8 elements] → n operations Level 1: [4,4] → n operations (4+4) Level 2: [2,2,2,2] → n operations (2+2+2+2) Level 3: [1,1,1,1,1,1,1,1] → n operations Total levels = log₂(8) = 3 Total operations = 3n = O(n log n) ``` **Comparison with Simple Sorts:** ``` n=1,000: - Insertion Sort: ~500,000 operations - Merge Sort: ~10,000 operations → 50x faster! n=1,000,000: - Insertion Sort: ~500 billion operations - Merge Sort: ~20 million operations → 25,000x faster! ``` #### Advantages and Disadvantages **Advantages:** 1. **Guaranteed O(n log n)** - always efficient 2. **Stable** - preserves relative order 3. **Predictable** - no worst-case scenarios 4. **Good for linked lists** - O(1) space possible 5. **Parallelizable** - can sort halves independently **Disadvantages:** 1. **O(n) space** - requires temporary storage 2. **Not in-place** - not memory efficient 3. **Overhead** - slower than Quick Sort in practice 4. **Not adaptive** - doesn't benefit from sorted data #### When to Use **Use Merge Sort when:** - Guaranteed O(n log n) required - Stability is important - Working with linked lists - External sorting (large files) - Parallel processing available **Don't use when:** - Memory is limited - In-place sorting required - Small datasets (overhead not worth it) ### 6.2 Quick Sort #### Concept **Quick Sort** is a divide-and-conquer algorithm that picks a pivot element and partitions the array around it, then recursively sorts the subarrays. **How it works:** 1. **Choose Pivot:** Select an element as pivot 2. **Partition:** Rearrange so elements < pivot are left, elements > pivot are right 3. **Recursively sort:** Sort left and right subarrays **Visual Example:** ``` Initial: [10, 80, 30, 90, 40, 50, 70] Pick pivot = 70 (last element) Partition: [10, 30, 40, 50] 70 [80, 90] ← less than 70 greater than 70 → Recursively sort left: [10, 30, 40, 50] Pick pivot = 50 [10, 30, 40] 50 [] Recursively sort right: [80, 90] Pick pivot = 90 [80] 90 [] Final: [10, 30, 40, 50, 70, 80, 90] ``` **Partitioning Process:** ``` Array: [10, 80, 30, 90, 40, 50, 70] Pivot: 70 (last element) i = -1 (tracks position of smaller elements) j = 0 (scans through array) j=0: arr[0]=10 < 70 → swap arr[++i] with arr[j] [10, 80, 30, 90, 40, 50, 70] i j=1: arr[1]=80 > 70 → no swap [10, 80, 30, 90, 40, 50, 70] i j=2: arr[2]=30 < 70 → swap arr[++i] with arr[j] [10, 30, 80, 90, 40, 50, 70] i j=3: arr[3]=90 > 70 → no swap j=4: arr[4]=40 < 70 → swap arr[++i] with arr[j] [10, 30, 40, 90, 80, 50, 70] i j=5: arr[5]=50 < 70 → swap arr[++i] with arr[j] [10, 30, 40, 50, 80, 90, 70] i Finally: Place pivot at i+1 [10, 30, 40, 50, 70, 90, 80] ↑ pivot in place ``` #### Implementation **Quick Sort with Last Element as Pivot:** ```c #include // Swap two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // Partition function int partition(int arr[], int low, int high) { int pivot = arr[high]; // Choose last element as pivot int i = low - 1; // Index of smaller element for (int j = low; j < high; j++) { // If current element is smaller than pivot if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } // Place pivot in correct position swap(&arr[i + 1], &arr[high]); return i + 1; } // Quick sort function void quickSort(int arr[], int low, int high) { if (low < high) { // Partition index int pi = partition(arr, low, high); // Recursively sort elements before and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {10, 80, 30, 90, 40, 50, 70}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, n); quickSort(arr, 0, n - 1); printf("Sorted array: "); printArray(arr, n); return 0; } ``` **Quick Sort with Middle Element as Pivot:** ```c int partitionMiddle(int arr[], int low, int high) { int mid = low + (high - low) / 2; int pivot = arr[mid]; // Move pivot to end swap(&arr[mid], &arr[high]); int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return i + 1; } ``` **Quick Sort with Random Pivot:** ```c #include #include int partitionRandom(int arr[], int low, int high) { // Generate random pivot index srand(time(NULL)); int randomIndex = low + rand() % (high - low + 1); // Move pivot to end swap(&arr[randomIndex], &arr[high]); return partition(arr, low, high); } void quickSortRandom(int arr[], int low, int high) { if (low < high) { int pi = partitionRandom(arr, low, high); quickSortRandom(arr, low, pi - 1); quickSortRandom(arr, pi + 1, high); } } ``` **Quick Sort with Visualization:** ```c void quickSortVisualize(int arr[], int low, int high, int depth) { if (low < high) { // Print indentation for (int i = 0; i < depth; i++) printf(" "); printf("Sorting: ["); for (int i = low; i <= high; i++) { printf("%d", arr[i]); if (i < high) printf(", "); } printf("] Pivot=%d\n", arr[high]); int pi = partition(arr, low, high); // Print result for (int i = 0; i < depth; i++) printf(" "); printf("Result: ["); for (int i = low; i <= high; i++) { if (i == pi) printf("*"); printf("%d", arr[i]); if (i == pi) printf("*"); if (i < high) printf(", "); } printf("]\n"); quickSortVisualize(arr, low, pi - 1, depth + 1); quickSortVisualize(arr, pi + 1, high, depth + 1); } } ``` **Three-Way Partitioning (for duplicates):** ```c void quickSort3Way(int arr[], int low, int high) { if (low >= high) return; int pivot = arr[high]; int i = low; int lt = low; // Elements < pivot int gt = high; // Elements > pivot while (i <= gt) { if (arr[i] < pivot) { swap(&arr[lt++], &arr[i++]); } else if (arr[i] > pivot) { swap(&arr[i], &arr[gt--]); } else { i++; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt + 1, high); } ``` #### Complexity Analysis **Time Complexity:** - Best Case: O(n log n) - balanced partitions - Average Case: O(n log n) - Worst Case: O(n²) - unbalanced partitions **Space Complexity:** O(log n) - recursion stack **Best Case (Balanced Partition):** ``` Each partition divides array in half [8 elements] / \ [4] [4] / \ / \ [2] [2] [2] [2] / \ / \ / \ / \ [1][1][1][1] [1][1][1][1] Height = log₂(n) Work per level = n Total = O(n log n) ``` **Worst Case (Unbalanced Partition):** ``` Sorted or reverse sorted with bad pivot choice [5, 4, 3, 2, 1] pivot = 1 ↓ [1] [5, 4, 3, 2] pivot = 2 ↓ [2] [5, 4, 3] pivot = 3 ↓ [3] [5, 4] ↓ [4] [5] Height = n Work = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²) ``` **Avoiding Worst Case:** 1. **Random Pivot:** Makes worst case unlikely 2. **Median-of-Three:** Use median of first, middle, last 3. **Three-Way Partition:** Handle duplicates efficiently #### Advantages and Disadvantages **Advantages:** 1. **Fast in practice** - usually faster than Merge Sort 2. **In-place** - O(log n) space only 3. **Cache-friendly** - good locality of reference 4. **Parallelizable** - can sort partitions independently **Disadvantages:** 1. **Unstable** - doesn't preserve relative order 2. **O(n²) worst case** - rare but possible 3. **Not adaptive** - doesn't benefit from sorted data 4. **Recursive** - stack overflow for deep recursion #### Pivot Selection Strategies **1. Last Element (Simple):** ```c int pivot = arr[high]; ``` - Simple but vulnerable to sorted input **2. First Element:** ```c int pivot = arr[low]; ``` - Same issue as last element **3. Middle Element:** ```c int mid = low + (high - low) / 2; int pivot = arr[mid]; ``` - Better for sorted input **4. Random Element:** ```c int randomIndex = low + rand() % (high - low + 1); int pivot = arr[randomIndex]; ``` - Probabilistically avoids worst case **5. Median-of-Three:** ```c int medianOfThree(int arr[], int low, int high) { int mid = low + (high - low) / 2; if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]); if (arr[low] > arr[high]) swap(&arr[low], &arr[high]); if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]); return mid; } ``` - Best practical choice #### When to Use **Use Quick Sort when:** - Average case performance matters - Memory is limited (in-place) - Cache performance important - Large datasets - Stability not required **Don't use when:** - Worst case must be avoided - Stability required - Small datasets - Stack space is limited **Comparison with Merge Sort:** ``` Quick Sort Merge Sort Time (avg): O(n log n) O(n log n) Time (worst): O(n²) O(n log n) Space: O(log n) O(n) Stable: No Yes In-place: Yes No Cache: Better Worse Practice: Faster Slower ``` # 7. Comparison of Sorting Algorithms ### 7.1 Performance Summary ```c // Test all sorting algorithms #include void testSortingAlgorithms() { int sizes[] = {100, 1000, 10000}; for (int s = 0; s < 3; s++) { int n = sizes[s]; printf("\n=== Array Size: %d ===\n", n); // Test each algorithm int *arr = generateRandomArray(n); clock_t start = clock(); bubbleSort(arr, n); clock_t end = clock(); printf("Bubble Sort: %.4f seconds\n", (double)(end - start) / CLOCKS_PER_SEC); // Repeat for other algorithms... free(arr); } } ``` ### 7.2 When to Use Which Algorithm **Decision Tree:** ``` Is n < 50? ├─ Yes → Use Insertion Sort (simple, fast for small n) └─ No → Is stability required? ├─ Yes → Use Merge Sort └─ No → Is memory limited? ├─ Yes → Use Quick Sort (in-place) └─ No → Use Merge Sort (guaranteed O(n log n)) ``` **By Data Characteristics:** ``` Nearly sorted →Insertion Sort (O(n)) Reverse sorted → Any O(n log n) algorithm Random data → Quick Sort (fastest in practice) Many duplicates → Quick Sort 3-way Small data → Insertion Sort Large data → Merge Sort or Quick Sort Linked list → Merge Sort (O(1) space) Stability needed → Merge Sort or Insertion Sort Memory limited → Quick Sort or Heap Sort ``` ### 7.3 Hybrid Sorting Approaches **IntroSort (Introspective Sort):** ```c void introSort(int arr[], int low, int high, int depthLimit) { int n = high - low + 1; // Use Insertion Sort for small arrays if (n < 16) { insertionSort(arr + low, n); return; } // Switch to Heap Sort if recursion too deep if (depthLimit == 0) { heapSort(arr + low, n); return; } // Use Quick Sort int pi = partition(arr, low, high); introSort(arr, low, pi - 1, depthLimit - 1); introSort(arr, pi + 1, high, depthLimit - 1); } // Wrapper function void sort(int arr[], int n) { int depthLimit = 2 * log2(n); introSort(arr, 0, n - 1, depthLimit); } ``` **TimSort (Python's default sort):** - Combination of Merge Sort and Insertion Sort - Identifies natural runs in data - Uses Insertion Sort for small runs - Merges runs using Merge Sort # 8. Practical Applications ### 8.1 Search and Sort Combined ```c #include #include #include // Student structure typedef struct { int id; char name[50]; float gpa; } Student; // Compare functions for sorting int compareByID(const void *a, const void *b) { return ((Student*)a)->id - ((Student*)b)->id; } int compareByGPA(const void *a, const void *b) { float diff = ((Student*)b)->gpa - ((Student*)a)->gpa; return (diff > 0) ? 1 : (diff < 0) ? -1 : 0; } int compareByName(const void *a, const void *b) { return strcmp(((Student*)a)->name, ((Student*)b)->name); } // Binary search by ID int searchByID(Student students[], int n, int targetID) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (students[mid].id == targetID) { return mid; } else if (students[mid].id < targetID) { left = mid + 1; } else { right = mid - 1; } } return -1; } // Linear search by name int searchByName(Student students[], int n, const char *name) { for (int i = 0; i < n; i++) { if (strcmp(students[i].name, name) == 0) { return i; } } return -1; } // Print students void printStudents(Student students[], int n) { printf("\n%-10s %-20s %-8s\n", "ID", "Name", "GPA"); printf("----------------------------------------\n"); for (int i = 0; i < n; i++) { printf("%-10d %-20s %.2f\n", students[i].id, students[i].name, students[i].gpa); } } int main() { Student students[] = { {1003, "Alice Johnson", 3.8}, {1001, "Bob Smith", 3.5}, {1005, "Charlie Brown", 3.9}, {1002, "Diana Prince", 3.7}, {1004, "Eve Wilson", 3.6} }; int n = sizeof(students) / sizeof(students[0]); printf("=== Student Database ===\n"); printf("\nOriginal Data:"); printStudents(students, n); // Sort by ID qsort(students, n, sizeof(Student), compareByID); printf("\nSorted by ID:"); printStudents(students, n); // Search by ID int targetID = 1003; int index = searchByID(students, n, targetID); if (index != -1) { printf("\nStudent with ID %d: %s (GPA: %.2f)\n", targetID, students[index].name, students[index].gpa); } // Sort by GPA (descending) qsort(students, n, sizeof(Student), compareByGPA); printf("\nSorted by GPA (highest first):"); printStudents(students, n); // Sort by Name qsort(students, n, sizeof(Student), compareByName); printf("\nSorted by Name:"); printStudents(students, n); return 0; } ``` ### 8.2 Finding Kth Largest Element ```c // Partition function (same as Quick Sort) int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } // Quick Select algorithm - O(n) average time int findKthLargest(int arr[], int low, int high, int k) { if (low == high) { return arr[low]; } int pi = partition(arr, low, high); int length = high - pi + 1; if (length == k) { return arr[pi]; } else if (length > k) { return findKthLargest(arr, pi + 1, high, k); } else { return findKthLargest(arr, low, pi - 1, k - length); } } int main() { int arr[] = {3, 2, 1, 5, 6, 4}; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; int result = findKthLargest(arr, 0, n - 1, k); printf("%dth largest element: %d\n", k, result); // Output: 2nd largest element: 5 return 0; } ``` ### 8.3 Merge Two Sorted Arrays ```c #include #include int* mergeSortedArrays(int arr1[], int n1, int arr2[], int n2) { int *result = (int*)malloc((n1 + n2) * sizeof(int)); int i = 0, j = 0, k = 0; // Merge while both arrays have elements while (i < n1 && j < n2) { if (arr1[i] <= arr2[j]) { result[k++] = arr1[i++]; } else { result[k++] = arr2[j++]; } } // Copy remaining elements from arr1 while (i < n1) { result[k++] = arr1[i++]; } // Copy remaining elements from arr2 while (j < n2) { result[k++] = arr2[j++]; } return result; } int main() { int arr1[] = {1, 3, 5, 7}; int arr2[] = {2, 4, 6, 8}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int n2 = sizeof(arr2) / sizeof(arr2[0]); int *merged = mergeSortedArrays(arr1, n1, arr2, n2); printf("Merged array: "); for (int i = 0; i < n1 + n2; i++) { printf("%d ", merged[i]); } printf("\n"); free(merged); return 0; } ``` ### 8.4 Finding Median ```c // Find median of unsorted array double findMedian(int arr[], int n) { // Sort the array first quickSort(arr, 0, n - 1); // Find median if (n % 2 == 0) { // Even number of elements - average of two middle return (arr[n/2 - 1] + arr[n/2]) / 2.0; } else { // Odd number of elements - middle element return arr[n/2]; } } int main() { int arr1[] = {3, 1, 4, 1, 5, 9, 2}; int arr2[] = {6, 5, 3, 5, 8, 9}; printf("Median of arr1: %.1f\n", findMedian(arr1, 7)); printf("Median of arr2: %.1f\n", findMedian(arr2, 6)); return 0; } ``` ### 8.5 Removing Duplicates from Sorted Array ```c int removeDuplicates(int arr[], int n) { if (n == 0 || n == 1) { return n; } int j = 0; // Index for unique elements for (int i = 0; i < n - 1; i++) { if (arr[i] != arr[i + 1]) { arr[j++] = arr[i]; } } arr[j++] = arr[n - 1]; // Add last element return j; // New length } int main() { int arr[] = {1, 1, 2, 2, 2, 3, 4, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); int newLength = removeDuplicates(arr, n); printf("After removing duplicates: "); for (int i = 0; i < newLength; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } ``` ### 8.6 Finding Intersection of Two Arrays ```c void findIntersection(int arr1[], int n1, int arr2[], int n2) { // Sort both arrays first quickSort(arr1, 0, n1 - 1); quickSort(arr2, 0, n2 - 1); printf("Intersection: "); int i = 0, j = 0; while (i < n1 && j < n2) { if (arr1[i] < arr2[j]) { i++; } else if (arr1[i] > arr2[j]) { j++; } else { // Elements are equal printf("%d ", arr1[i]); i++; j++; } } printf("\n"); } int main() { int arr1[] = {1, 3, 4, 5, 7}; int arr2[] = {2, 3, 5, 6}; findIntersection(arr1, 5, arr2, 4); // Output: Intersection: 3 5 return 0; } ``` ### 8.7 Sorting Strings ```c #include #include void sortStrings(char *arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (strcmp(arr[j], arr[j + 1]) > 0) { // Swap pointers char *temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { char *fruits[] = {"Banana", "Apple", "Orange", "Mango", "Grape"}; int n = 5; printf("Original: "); for (int i = 0; i < n; i++) { printf("%s ", fruits[i]); } printf("\n"); sortStrings(fruits, n); printf("Sorted: "); for (int i = 0; i < n; i++) { printf("%s ", fruits[i]); } printf("\n"); return 0; } ```