**Course Title:** Mastering C: From Fundamentals to Advanced Programming **Section Title:** Sorting and Searching Algorithms **Topic:** Implementing sorting and searching in C **Introduction** In the previous topic, we explored the common sorting algorithms: bubble sort, selection sort, and quicksort, as well as searching algorithms: linear search and binary search. In this topic, we will delve deeper into implementing these algorithms in C programming language. We will discuss the coding aspect, best practices, and time complexity of each algorithm. **Implementing Sorting Algorithms** Let's start with implementing bubble sort, selection sort, and quicksort algorithms in C. ### Bubble Sort Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. ```c #include <stdio.h> // Function to swap two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // Function to perform bubble sort void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(&arr[j], &arr[j + 1]); } } } } // Function to print an array void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // Driver program to test bubble sort int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printArray(arr, n); return 0; } ``` ### Selection Sort Selection sort is an in-place comparison-based algorithm that divides the list into two sublists, the sorted list and the unsorted list. Initially, the sorted list is empty and the unsorted list contains all the elements. Each iteration, the algorithm selects the smallest (or largest, depending on the sorting order) element from the unsorted sublist and swaps it with the leftmost element of the unsorted sublist. ```c #include <stdio.h> // Function to perform selection sort void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int min_index = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[min_index]) { min_index = j; } } // Swap the found minimum element with the first element of unsorted portion int temp = arr[min_index]; arr[min_index] = arr[i]; arr[i] = temp; } } // Function to print an array void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // Driver program to test selection sort int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); selectionSort(arr, n); printArray(arr, n); return 0; } ``` ### Quicksort Quicksort is a divide-and-conquer algorithm that selects a 'pivot' element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. ```c #include <stdio.h> // Function to swap two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Function to partition the array and returns the pivot index int partition(int arr[], int low, int high) { int pivot = arr[high]; // choosing the last element as pivot int i = (low - 1); // index of smaller element for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; // swap arr[i] and arr[j] swap(&arr[i], &arr[j]); } } // swap arr[i+1] and arr[high] (or pivot) swap(&arr[i + 1], &arr[high]); return (i + 1); } // Function to perform quicksort void quickSort(int arr[], int low, int high) { if (low < high) { int pivot_index = partition(arr, low, high); // Recursively sort the sub-arrays quickSort(arr, low, pivot_index - 1); quickSort(arr, pivot_index + 1, high); } } // Function to print an array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } // Driver program to test quicksort int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printArray(arr, n); return 0; } ``` **Implementing Searching Algorithms** Now let's implement linear search and binary search algorithms in C. ### Linear Search Linear search is a simple searching algorithm that works by iterating through each element in the list until it finds the desired element. ```c #include <stdio.h> // Function to perform linear search int linearSearch(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return i; } } return -1; } // Driver program to test linear search int main() { int arr[] = {2, 3, 4, 10, 40}; int key = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = linearSearch(arr, n, key); if (result == -1) printf("Element is not present in array"); else printf("Element is present at index %d", result); return 0; } ``` ### Binary Search Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed the possible locations to just one. ```c #include <stdio.h> // Function to perform binary search int binarySearch(int arr[], int l, int r, int key) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == key) return mid; if (arr[mid] > key) return binarySearch(arr, l, mid - 1, key); return binarySearch(arr, mid + 1, r, key); } return -1; } // Driver program to test binary search int main() { int arr[] = {2, 3, 4, 10, 40}; int key = 10; int n = sizeof(arr) / sizeof(arr[0]); // Perform binary search int result = binarySearch(arr, 0, n - 1, key); if (result == -1) printf("Element is not present in array"); else printf("Element is present at index %d", result); return 0; } ``` **Time Complexity** Here's a summary of the time complexity of the implemented sorting and searching algorithms: | Algorithm | Best-Case Time Complexity | Average-Case Time Complexity | Worst-Case Time Complexity | | --- | --- | --- | --- | | Bubble Sort | O(n) | O(n^2) | O(n^2) | | Selection Sort | O(n^2) | O(n^2) | O(n^2) | | Quicksort | O(n log n) | O(n log n) | O(n^2) | | Linear Search | O(1) | O(n/2) | O(n) | | Binary Search | O(1) | O(log n) | O(log n) | **Conclusion** In this topic, we've implemented common sorting algorithms (bubble sort, selection sort, and quicksort) and searching algorithms (linear search and binary search) in C. We've discussed the coding aspect, best practices, and time complexity of each algorithm. **External 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) **Ask For Help:** If you have any questions or need further clarification on any of the concepts discussed in this topic, please leave a comment below. **Next Topic:** In the next topic, we'll discuss the importance of debugging and testing in software development.