Algorithms are fundamental to problem-solving in computer science. Sorting and searching are two essential operations that are often used in programming to organize and retrieve data efficiently. In this article, we will explore basic sorting and searching algorithms implemented in C language.
Sorting algorithms are used to arrange data in a specific order (ascending or descending). Below, we will look at two commonly used sorting algorithms: Bubble Sort and Selection Sort.
Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap the elements
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, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
In this example, the function bubbleSort sorts the array in ascending order by repeatedly comparing and swapping adjacent elements. The function printArray displays the array before and after sorting.
Selection Sort is another comparison-based sorting algorithm. It works by dividing the array into two parts: the sorted part and the unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first unsorted element.
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first unsorted element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = 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: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
In this example, the selectionSort function sorts the array by selecting the minimum element from the unsorted part and swapping it with the first unsorted element.
Searching algorithms are used to find a specific element within a data structure. Below, we will discuss two basic searching algorithms: Linear Search and Binary Search.
Linear Search is a simple searching algorithm that checks each element in a list sequentially until the desired element is found or the end of the list is reached. It is best used with unsorted data.
#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // Element found, return index
}
}
return -1; // Element not found
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 22;
int result = linearSearch(arr, n, key);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
In this example, the function linearSearch searches for the value key in the array. If the element is found, it returns the index of the element; otherwise, it returns -1.
Binary Search is an efficient searching algorithm that works on sorted data. It repeatedly divides the search interval in half, comparing the target value to the middle element of the list. If the target value is smaller, it searches the left half; otherwise, it searches the right half. The process continues until the element is found or the interval is empty.
#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid; // Element found, return index
} else if (arr[mid] > key) {
right = mid - 1; // Search left half
} else {
left = mid + 1; // Search right half
}
}
return -1; // Element not found
}
int main() {
int arr[] = {11, 12, 22, 25, 64};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 22;
int result = binarySearch(arr, n, key);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
In this example, the function binarySearch searches for the value key in a sorted array. It divides the array into halves and narrows down the search space until the element is found or the search space is empty.
Sorting and searching are fundamental operations that play a crucial role in many algorithms. In this article, we have covered basic sorting algorithms (Bubble Sort and Selection Sort) and searching algorithms (Linear Search and Binary Search). These algorithms provide a foundation for understanding more advanced techniques and can be optimized further for large datasets and specific use cases.