**Course Title:** Mastering C: From Fundamentals to Advanced Programming **Section Title:** Sorting and Searching Algorithms **Topic:** Write C programs to implement and test various sorting and searching algorithms. (Lab topic) **Overview:** In this lab topic, you'll learn how to implement and test various sorting and searching algorithms using the C programming language. You'll write programs to sort and search arrays of integers and strings using different algorithms, such as Bubble Sort, Selection Sort, Quick Sort, Linear Search, and Binary Search. **Learning Objectives:** * Implement and test Bubble Sort, Selection Sort, and Quick Sort algorithms for sorting arrays of integers and strings. * Understand the time complexities of different sorting algorithms. * Implement and test Linear Search and Binary Search algorithms for searching arrays of integers and strings. * Analyze the efficiency of different searching algorithms. * Learn how to use C programming to solve real-world problems related to sorting and searching. **Lab Exercises:** ### Exercise 1: Bubble Sort Implement the Bubble Sort algorithm to sort an array of integers in ascending order. ```c #include <stdio.h> void bubbleSort(int arr[], int n) { int i, j, temp; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } void printArray(int arr[], int n) { int i; for (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; } ``` ### Exercise 2: Selection Sort Implement the Selection Sort algorithm to sort an array of integers in ascending order. ```c #include <stdio.h> void selectionSort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n - 1; i++) { min_idx = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[min_idx]) { min_idx = j; } } int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } void printArray(int arr[], int n) { int i; for (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); selectionSort(arr, n); printf("Sorted array: "); printArray(arr, n); return 0; } ``` ### Exercise 3: Quick Sort Implement the Quick Sort algorithm to sort an array of integers in ascending order. ```c #include <stdio.h> int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); int j; for (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; } void quickSort(int arr[], int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void printArray(int arr[], int n) { int i; for (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); quickSort(arr, 0, n - 1); printf("Sorted array: "); printArray(arr, n); return 0; } ``` ### Exercise 4: Linear Search Implement the Linear Search algorithm to search for an element in an array. ```c #include <stdio.h> int linearSearch(int arr[], int n, int target) { int i; for (i = 0; i < n; i++) { if (arr[i] == target) { return i; } } return -1; } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); int i; for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); int target; printf("Enter the target element: "); scanf("%d", &target); int result = linearSearch(arr, n, target); if (result == -1) { printf("Element not found in the array\n"); } else { printf("Element found at index %d\n", result); } return 0; } ``` ### Exercise 5: Binary Search Implement the Binary Search algorithm to search for an element in a sorted array. ```c #include <stdio.h> int binarySearch(int arr[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; } int main() { int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); int i; for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); int target; printf("Enter the target element: "); scanf("%d", &target); int result = binarySearch(arr, n, target); if (result == -1) { printf("Element not found in the array\n"); } else { printf("Element found at index %d\n", result); } return 0; } ``` **Lab Report:** After completing the lab exercises, you should be able to: 1. Implement and test the Bubble Sort, Selection Sort, and Quick Sort algorithms for sorting arrays of integers. 2. Implement and test the Linear Search and Binary Search algorithms for searching arrays of integers. 3. Analyze the time complexities of different sorting and searching algorithms. 4. Use C programming to solve real-world problems related to sorting and searching. **Additional Resources:** * [GeeksforGeeks: Sorting Algorithms](https://www.geeksforgeeks.org/sorting-algorithms/) * [GeeksforGeeks: Searching Algorithms](https://www.geeksforgeeks.org/searching-algorithms/) * [Wikipedia: Sorting Algorithms](https://en.wikipedia.org/wiki/Sorting_algorithm) * [Wikipedia: Searching Algorithms](https://en.wikipedia.org/wiki/Search_algorithm) **Conclusion:** In this lab topic, you have learned how to implement and test various sorting and searching algorithms using the C programming language. You have also analyzed the time complexities of different algorithms and used C programming to solve real-world problems related to sorting and searching. If you have any questions or need help with any of the exercises, please leave a comment below. **Next Topic:** In the next topic, we will cover the importance of debugging and testing in software development. We will explore different debugging techniques and learn how to use testing frameworks to ensure that our code is reliable and efficient. Please proceed to the next topic: [Importance of Debugging and Testing in Software Development](#).