C Implementation of Selection Sort and Search Algorithms
Selection Sort Algorithm in C
Selection Sort is a simple sorting algorithm that repeatedly finds the minimum element from the unsorted part of the array and swaps it with the element at the current position.
C Implementation of Selection Sort Function
#include <stdio.h>
The function void selectionSort(int arr[], int n) performs the sorting:
void selectionSort(int arr[], int n)
{
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
// Find the index of the minimum element in the unsorted part
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { minIndex = j;}
}
// Swap the found minimum element with the first element of the unsorted subarray
if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
Utility Function: Printing the Array
void printArray(int arr[], int n) {
printf("Sorted array: ");
for (int i = 0; i < n; i++) { printf("%d ", arr[i]); }
printf("\n");
}
Main Function Example (Selection Sort)
This example demonstrates how to input elements, sort them using selectionSort, and print the result.
int main() {
int arr[100], n;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); }
selectionSort(arr, n);
printArray(arr, n);
return 0;
}
Searching Algorithms in C
Linear Search Implementation
Linear search checks every element sequentially until the target value is found. It is suitable for unsorted arrays.
#include <stdio.h>
Main Function Example (Linear Search)
int main() {
int array[100], n, target, found = 0;
// Input number of elements
printf("Enter the number of elements: ");
scanf("%d", &n);
// Input elements
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) { scanf("%d", &array[i]); }
// Input the value to search
printf("Enter the value to search: ");
scanf("%d", &target);
// Linear Search Logic
for (int i = 0; i < n; i++) {
if (array[i] == target) {
printf("Element %d found at position %d (index %d).\n", target, i + 1, i);
found = 1;
break;
}
}
if (!found) {
printf("Element %d not found in the array.\n", target);
}
return 0;
}
Binary Search Implementation
Binary search is highly efficient but requires the input array to be sorted. It works by repeatedly halving the search interval.
#include <stdio.h>
Binary Search Function Definition
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = low + (high - low) / 2; // Safer midpoint calculation
if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}
return -1; // Target not found
}
Auxiliary Sorting Function (Required for Binary Search)
This implementation redefines Selection Sort to ensure the array is sorted before the binary search begins.
void selectionSort(int arr[], int n)
{
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { minIndex = j; }
}
// Swap logic
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
Auxiliary Print Function
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) { printf("%d ", arr[i]); }
printf("\n");
}
Main Function Example (Binary Search)
int main() {
int arr[100], n, target, result;
printf("Enter number of elements: ");
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("Invalid number of elements. Must be between 1 and 100.\n");
return 1;
}
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); }
// Sort the array before binary search
selectionSort(arr, n);
// Print the sorted array
printf("Sorted array:\n");
printArray(arr, n);
printf("Enter element to search: ");
scanf("%d", &target);
result = binarySearch(arr, n, target);
if (result != -1) {
printf("Element %d found at index %d (after sorting)\n", target, result);
} else {
printf("Element %d not found in the array\n", target);
}
return 0;
}