Public App

# Category: Searching, Sorting, and File Structures

## Selection Sort in C Language

Selection sort is a simple in-place comparison-based sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted part of the array and moving it to the beginning of the array. Here’s an implementation of the selection sort algorithm in C language:

``````#include <stdio.h>

void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n) {
int i, j, min_idx;

// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);

selectionSort(arr, n);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

In the `selectionSort` function, we first find the minimum element from the unsorted part of the array and swap it with the first element. We then repeat this process for the remaining subarray until the entire array is sorted.

The `swap` function is a helper function that exchanges the values of two integer variables using pointers.

In the `main` function, we create an integer array and call the `selectionSort` function to sort it. Finally, we print the sorted array to the console.

The time complexity of selection sort is O(n^2), which makes it inefficient for large arrays. However, it has the advantage of being simple to implement and requiring only a small amount of additional memory space.

## Merge Sort in C Language

Merge sort is a popular divide-and-conquer sorting algorithm that recursively divides the input array into two halves, sorts each half, and then merges the sorted halves back together. In C language, an implementation of the Merge Sort algorithm can be as follows:

``````#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[n1], R[n2];

/* copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}

/* merge the temp arrays back into arr[l..r] */
i = 0; /* initial index of first subarray */
j = 0; /* initial index of second subarray */
k = l; /* initial index of merged subarray */
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

/* copy the remaining elements of L[], if there are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* copy the remaining elements of R[], if there are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // middle index

/* sort first and second halves */
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

/* merge the sorted halves */
merge(arr, l, m, r);
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `merge` function takes an integer array `arr` and three integer values `l`, `m`, and `r`. It merges two sorted sub-arrays `arr[l..m]` and `arr[m+1..r]` into a single sorted sub-array `arr[l..r]`.

The `mergeSort` function recursively sorts the array by dividing it into two halves, sorting each half, and then merging them back together using the `merge` function.

The `main` function creates an integer array and calls the `mergeSort` function to sort it. Finally, it prints the sorted array to the console.

Note that the worst-case time complexity of merge sort is O(n log n), which makes it very efficient for sorting large arrays. However, it has a higher overhead than other algorithms like insertion sort or selection sort for small arrays.

## Quick Sort in C Language

Quick Sort is a popular divide-and-conquer sorting algorithm that uses recursion to sort an array by partitioning it into smaller sub-arrays. In C language, an implementation of the Quick Sort algorithm can be as follows:

``````#include <stdio.h>

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now at right place
int pi = partition(arr, low, high);

// Separately sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `swap` function swaps two integer values passed as pointers.

The `partition` function takes an integer array `arr`, and two integer values `low` and `high`, which are the indexes of the subarray to be sorted. It selects the last element in the subarray as the pivot and partitions the array into two parts such that elements smaller than or equal to the pivot come before it, and elements larger than the pivot come after it. It returns the index of the pivot element after partitioning.

The `quickSort` function recursively sorts the array by calling `partition` and then calling itself on the two resulting subarrays until the whole array is sorted.

The `main` function creates an integer array and calls the `quick Sort` function to sort it. Finally, it prints the sorted array to the console.

Note that the worst-case time complexity of quick sort is O(n^2), but its average and best-case complexity is O(n log n), making it a very efficient algorithm for sorting large arrays.

## Bubble Sort in C Language

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. In C language, an implementation of the bubble sort algorithm can be as follows:

``````#include <stdio.h>

void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

int main() {
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int n = sizeof(arr) / sizeof(arr[0]);

bubbleSort(arr, n);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `bubbleSort` function takes an integer array `arr` and its length `n` as arguments. It iterates over the array multiple times, comparing each adjacent element and swapping them if they are in the wrong order. The largest element will “bubble” up to the end of the array after each iteration. The loop runs `n-1` times since the last element will be sorted automatically after `n-1` iterations.

The `main` function creates an integer array and calls the `bubbleSort` function to sort it. Finally, it prints the sorted array to the console.

Note that the worst-case time complexity of bubble sort is O(n^2), and it is not very efficient for large arrays. However, it has a small overhead and can be very efficient for small or partially sorted arrays.

## Insertion Sort in C Language

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it is very efficient for small lists or partially sorted lists. In C language, an implementation of the insertion sort algorithm can be as follows:

``````#include <stdio.h>

void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that are greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `insertionSort` function takes an integer array `arr` and its length `n` as arguments. It iterates over the array from the second element to the last element. For each element, it compares it with the previous elements and moves the larger elements from one position to the right until it finds the correct position for the current element. Finally, it inserts the current element into its correct position.

The `main` function creates an integer array and calls the `insertionSort` function to sort it. Finally, it prints the sorted array to the console.

Note that the worst-case time complexity of insertion sort is O(n^2), and it is not very efficient for large arrays. However, it has a small overhead and can be very efficient for small or partially sorted arrays.

## Binary Search in C Language

Binary search is a searching algorithm that efficiently searches a sorted array or list by repeatedly dividing the search interval in half. The algorithm compares the target element with the middle element of the array or list. If the target element is equal to the middle element, the search is complete. If the target element is less than the middle element, the search continues on the lower half of the array. If the target element is greater than the middle element, the search continues on the upper half of the array.

In C language, the binary search algorithm can be implemented using a loop that iteratively halves the search interval until the target element is found or the search interval is empty.

Here is an example implementation of binary search in C language:

``````int binarySearch(int arr[], int n, int x) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
}
else if (arr[mid] < x) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
``````

In this implementation, `arr` is the sorted array of elements to be searched, `n` is the size of the array, and `x` is the element to be searched. The `binarySearch` function uses `low` and `high` variables to represent the search interval. The search interval is repeatedly halved until the target element is found or the search interval is empty. The `mid` variable is the index of the middle element in the search interval. If the target element is equal to the middle element, the search is complete. If the target element is less than the middle element, the search continues on the lower half of the search interval. If the target element is greater than the middle element, the search continues on the upper half of the search interval. If the target element is not found, the function returns `-1`.

## Sequential Search in C Language

Sequential search, also known as linear search, is a simple searching algorithm that searches an array or a list of elements sequentially from start to end until the desired element is found.

In C language, the sequential search algorithm can be implemented using a loop that iterates through the elements of the array or list, comparing each element with the desired element. If the element is found, the loop is terminated, and the position of the element is returned. If the element is not found, the function returns a special value to indicate that the element is not present in the array or list.

Here is an example implementation of sequential search in C language:

``````int sequentialSearch(int arr[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
``````

In this implementation, `arr` is the array of elements to be searched, `n` is the size of the array, and `x` is the element to be searched. The `sequentialSearch` function iterates through the array using a `for` loop and compares each element with `x`. If the element is found, the function returns its index in the array. If the element is not found, the function returns `-1` to indicate that the element is not present in the array.