Searching and Sorting Algorithms in C
Searching is the process of finding a particular record within a huge amount of data. Data can be in the form of arrays, linked lists, trees, etc.
There are mainly two categories of searching:
- Sequential Searching (e.g., Linear Search)
- Interval Searching (e.g., Binary Search)
1. Linear Search
It is a type of sequential searching algorithm. Every element within the input array is traversed and compared with the item to be found. If the item matches, the search is successful.
- Best Case Complexity: O(1)
- Worst Case Complexity: O(n)
#include<stdio.h>
int main() {
int item, i, n = 6;
int a[6] = {1, 4, 2, 8, 6, 9};
printf("Enter the element to be found: ");
scanf("%d", &item);
for(i = 0; i < n; i++) {
if(a[i] == item) {
printf("Item found at %d position", i + 1);
return 0;
}
}
printf("Item not found");
return 0;
}2. Binary Search
Binary Search is an efficient algorithm used on sorted arrays. It works by repeatedly dividing the search interval in half.
Note: The definition of mid is (first + last) / 2.
If the target value is less than the middle element, we narrow the interval to the lower half. Otherwise, we narrow it to the upper half. We repeat this until the value is found or the interval is empty.
#include <stdio.h>
int binarySearch(int a[], int beg, int end, int item) {
int mid;
if(end >= beg) {
mid = (beg + end)/2;
if(a[mid] == item) {
return mid+1;
}
else if(a[mid] < item) {
return binarySearch(a, mid+1, end, item);
}
else {
return binarySearch(a, beg, mid-1, item);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 31, 40, 42, 52, 56, 80};
int item = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]);
int res = binarySearch(a, 0, n-1, item);
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", item);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}Sorting Algorithms
A. Selection Sort
In selection sort, the smallest value among the unsorted elements is selected in every pass and inserted into its appropriate position. The array is divided into two parts: sorted (left) and unsorted (right).
#include <stdio.h>
void selection(int a[], int n) {
int i, j, min;
for (i = 0; i < n-1; i++) {
min = i; // minimum element index
for (j = i+1; j < n; j++)
if (a[j] < a[min])
min = j;
// Swap
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
void printArr(int a[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main() {
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}B. Bubble Sort
Also known as exchange sort. It is the simplest sorting method. In each pass, two adjacent numbers are compared; if they are out of order, they are swapped. The large values "bubble" to the end of the array.
#include<stdio.h>
void print(int a[], int n) {
int i;
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
}
void bubble(int a[], int n) {
int i, j, temp;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(a[j] < a[i]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
int main () {
int a[5] = { 10, 35, 31, 5, 40};
int n = sizeof(a)/sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
bubble(a, n);
printf("\nAfter sorting array elements are - \n");
print(a, n);
}C. Insertion Sort
Similar to sorting playing cards. We assume the first element is sorted, then take the next unsorted element and place it in its correct position relative to the sorted part.
#include <stdio.h>
void insert(int a[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j >= 0 && temp <= a[j]) {
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
void printArr(int a[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main() {
int a[] = { 12, 30, 21, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}D. Quick Sort
A "Divide and Conquer" algorithm. It selects a pivot element and partitions the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
#include <stdio.h>
int partition (int a[], int start, int end) {
int pivot = a[end];
int i = (start - 1);
for (int j = start; j <= end - 1; j++) {
if (a[j] < pivot) {
i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}
void quick(int a[], int start, int end) {
if (start < end) {
int p = partition(a, start, end);
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}
void printArr(int a[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main() {
int a[] = { 20, 9, 39, 44, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}E. Merge Sort
Another "Divide and Conquer" algorithm. It recursively divides the array into halves until they cannot be divided further, then merges them back together in sorted order.
#include <stdio.h>
void merge(int a[], int beg, int mid, int end) {
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
int LeftArray[n1], RightArray[n2];
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0; j = 0; k = beg;
while (i < n1 && j < n2) {
if(LeftArray[i] <= RightArray[j]) {
a[k] = LeftArray[i];
i++;
} else {
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1) {
a[k] = LeftArray[i];
i++; k++;
}
while (j<n2) {
a[k] = RightArray[j];
j++; k++;
}
}
void mergeSort(int a[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
void printArray(int a[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main() {
int a[] = { 12, 22, 26, 9, 32, 18, 40, 45 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}Quick Reference: Big-O Complexity Comparison
Use this table to quickly compare the time and space complexity of all algorithms covered in this post:
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
Bonus: Structures vs Unions
Structures
- Each member has its own memory location.
- Size = Sum of sizes of members + padding.
- Used to represent a collection of different data types.
Unions
- All members share the same memory location.
- Size = Size of the largest member.
- Used when only one value needs to be accessed at a time.