LINEAR SEARCH

Linear search is a sequential searching algorithm where

we start from one end and check every element of the list
until the desired element is found. It is the simplest
searching algorithm.
Algorithm:

LinearSearch(array, key)
for each item in the array
if item == value
return its index
#include <stdio.h>

int search(int array[], int n, int x) {

// Going through array sequencially

for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}

int main() {
int array[] = {2, 4, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);

int result = search(array, n, x);

(result == -1) ? printf("Element not found") : printf("Element found at

index: %d", result);
}
 Binary Search
Binary Search is a searching algorithm for finding an element's position in a
sorted array.
In this approach, the element is always searched in the middle of a portion of
an array.
Binary search can be implemented only on a sorted list of items. If the
elements are not sorted already, we need to sort them first.

do until the pointers low and high meet each other.

mid = (low + high)/2
if (x == arr[mid]) return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
// Binary Search in C
#include <stdio.h>
int binarySearch(int array[], int x, int low,
int high) int main(void) {
{ int array[] = {3, 4, 5, 6, 7, 8, 9};
// Repeat until the pointers low and high int n = sizeof(array) /
meet each other. sizeof(array[0]);
while (low <= high) int x = 4;
{ int result = binarySearch(array, x, 0,
int mid = low + (high - low) / 2; n - 1);
if (array[mid] == x) if (result == -1)
return mid; printf("Not found");
if (array[mid] < x) else
low = mid + 1; printf("Element is found at index
else %d", result);
high = mid - 1; return 0;
} }
return -1;
}
 BUBBLE SORT
Bubble sort is a simple and intuitive sorting algorithm. It
repeatedly swaps adjacent elements if they are in the wrong order
until the array is sorted. In this algorithm, the largest element
"bubbles up" to the end of the array in each iteration. Bubble sort is
inefficient for large data sets, but it is useful for educational purposes
and small data sets. In this article, we will implement the bubble sort
algorithm in C programming language.
The function has two loops. The outer loop runs from the first
element to the second-last element of the array. The inner loop runs
from the first element to the second-last element of the unsorted
part of the array. The condition of the inner loop is n - i - 1 because
the last i elements of the array are already sorted.
In each iteration of the inner loop, we compare adjacent
elements. If the left element is greater than the right element, we
swap them. After the inner loop completes, the largest element is
guaranteed to be at the end of the unsorted part of the array.
#include <stdio.h>

void bubble_sort(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]) {
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]);
bubble_sort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
 INSERTION SORT
Insertion sort is a simple sorting algorithm that iteratively
constructs a sorted section of an array one element at a time. It is an
in-place comparison-based method with an average time complexity
of O(n2).
The array is divided into two halves by the method: sorted
and unsorted. The first element of the array is first considered the
sorted component, whereas the remaining items are originally
considered the unsorted component.
The algorithm subsequently compares each unsorted element
to the elements in the sorted segment, beginning at the end, and
adjusts the bigger elements one position to the right until the
unsorted element is found in the correct location.
After determining the proper location, the unsorted element is
placed into the sorted component at that location.
#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;

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);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
 SELECTION SORT
In selection sort, the smallest value among the unsorted elements of the
array is selected in every pass and inserted to its appropriate position into the
array. It is also the simplest algorithm. It is an in-place comparison sorting
algorithm. In this algorithm, the array is divided into two parts, first is sorted part,
and another one is the unsorted part. Initially, the sorted part of the array is
empty, and unsorted part is the given array. Sorted part is placed at the left, while
the unsorted part is placed at the right.
In selection sort, the first smallest element is selected from the unsorted
array and placed at the first position. After that second smallest element is
selected and placed in the second position. The process continues until the array is
entirely sorted.
The average and worst-case complexity of selection sort is O(n2),
where n is the number of items. Due to this, it is not suitable for large data sets.

Selection sort is generally used when -

A small array is to be sorted
Swapping cost doesn't matter
It is compulsory to check all elements
// Selection sort in C
// put min at the correct position
#include <stdio.h> swap(&array[min_idx], &array[step]);
}
// function to swap the the position of two }
elements
void swap(int *a, int *b) { // function to print an array
int temp = *a; void printArray(int array[], int size) {
*a = *b; for (int i = 0; i < size; ++i) {
*b = temp; printf("%d ", array[i]);
} }
printf("\n");
void selectionSort(int array[], int size) { }
for (int step = 0; step < size - 1; step++) {
int min_idx = step; // driver code
for (int i = step + 1; i < size; i++) { int main() {
int data[] = {20, 12, 10, 15, 2};
// To sort in descending order, change > to < int size = sizeof(data) / sizeof(data[0]);
in this line. selectionSort(data, size);
// Select the minimum element in each loop. printf("Sorted array in Acsending
if (array[i] < array[min_idx]) Order:\n");
min_idx = i; printArray(data, size);
} }
 RADIX SORT
Radix sort is the linear sorting algorithm that is used for integers. In Radix
sort, there is digit by digit sorting is performed that is started from the least
significant digit to the most significant digit.
The process of radix sort works similar to the sorting of students names,
according to the alphabetical order. In this case, there are 26 radix formed due to
the 26 alphabets in English. In the first pass, the names of students are grouped
according to the ascending order of the first letter of their names. After that, in the
second pass, their names are grouped according to the ascending order of the
second letter of their name. And the process continues until we find the sorted list.

The steps used in the sorting of radix sort are listed as follows –

First, we have to find the largest element (suppose max) from the given array.
Suppose 'x' be the number of digits in max. The 'x' is calculated because we need to
go through the significant places of all elements.
After that, go through one by one each significant place. Here, we have to use any
stable sorting algorithm to sort the digits of each significant place.
#include <stdio.h>
int getMax(int a[], int n) { // Place the elements in sorted order
int max = a[0]; for (int i = n - 1; i >= 0; i--) {
for(int i = 1; i<n; i++) { output[count[(a[i] / place) % 10] -
if(a[i] > max) 1] = a[i];
max = a[i]; count[(a[i] / place) % 10]--;
} }
return max; //maximum element from the arr
ay for (int i = 0; i < n; i++)
} a[i] = output[i];
void countingSort(int a[], int n, int place) // fu }
nction to implement counting sort
{ // function to implement radix sort
int output[n + 1]; void radixsort(int a[], int n) {
int count[10] = {0};
// Calculate count of elements // get maximum element from array
for (int i = 0; i < n; i++) int max = getMax(a, n);
count[(a[i] / place) % 10]++;
// Apply counting sort to sort elements
// Calculate cumulative frequency based on place value
for (int i = 1; i < 10; i++) for (int place = 1; max / place > 0; place
count[i] += count[i - 1]; *= 10)
countingSort(a, n, place);
}
// function to print array elements
void printArray(int a[], int n) {
for (int i = 0; i < n; ++i) {
printf("%d ", a[i]);
}
printf("\n");
}

int main() {
int a[] = {181, 289, 390, 121, 145, 736, 514, 888, 122};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a,n);
radixsort(a, n);
printf("After applying Radix sort, the array elements are -
\n");
printArray(a, n);
}
 MERGE SORT
Merge sort is the sorting technique that follows the divide and conquer
approach. This article will be very helpful and interesting to students as they might
face merge sort as a question in their examinations. In coding or technical
interviews for software engineers, sorting algorithms are widely asked. So, it is
important to discuss the topic.
Merge sort is similar to the quick sort algorithm as it uses the divide and
conquer approach to sort the elements. It is one of the most popular and efficient
sorting algorithm. It divides the given list into two equal halves, calls itself for the
two halves and then merges the two sorted halves. We have to define
the merge() function to perform the merging.
The sub-lists are divided again and again into halves until the list cannot
be divided further. Then we combine the pair of one element lists into two-
element lists, sorting them in the process. The sorted two-element pairs is merged
into the four-element lists, and so on until we get the sorted list.
#include <stdio.h>
while (i < n1 && j < n2)
{
/* Function to merge the subarrays of a[] */
if(LeftArray[i] <= RightArray[j])
void merge(int a[], int beg, int mid, int end)
{
{
a[k] = LeftArray[i];
int i, j, k;
i++;
int n1 = mid - beg + 1;
}
int n2 = end - mid;
else
{
int LeftArray[n1], RightArray[n2]; //tempor
a[k] = RightArray[j];
ary arrays
j++;
}
/* copy data to temp arrays */
k++;
for (int i = 0; i < n1; i++)
}
LeftArray[i] = a[beg + i];
while (i<n1)
for (int j = 0; j < n2; j++)
{
RightArray[j] = a[mid + 1 + j];
a[k] = LeftArray[i];
i++;
i = 0; /* initial index of first sub-array */
k++;
j = 0; /* initial index of second sub-
}
array */
k = beg; /* initial index of merged sub-
array */
 while (j<n2) /* Function to print the array */
{ void printArray(int a[], int n)
a[k] = RightArray[j]; {
j++; int i;
k++; for (i = 0; i < n; i++)
} printf("%d ", a[i]);
} printf("\n");
}
void mergeSort(int a[], int beg, int end
) int main()
{ {
if (beg < end) int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
{ int n = sizeof(a) / sizeof(a[0]);
int mid = (beg + end) / 2; printf("Before sorting array elements are -
mergeSort(a, beg, mid); \n");
mergeSort(a, mid + 1, end); printArray(a, n);
merge(a, beg, mid, end); mergeSort(a, 0, n - 1);
} printf("After sorting array elements are - \n");
} printArray(a, n);
return 0;
}
 QUICK SORT
Quick sort is a commonly used sorting algorithm that is often preferred over
other sorting algorithms due to its efficiency and effectiveness. It proceeds by
splitting an array into two parts, one with elements smaller than a selected pivot
element and the other with elements bigger than the pivot. The algorithm then
applies this procedure recursively to each partition until the complete array is
sorted.
Quick sort can be used in any scenario where sorting is required, such as in
database applications, scientific computing, and web applications. It is frequently
utilized when a large dataset must be rapidly and effectively sorted. Some specific
use cases where quick sort is commonly used include:
• Sorting arrays in programming languages such as C, Java, and Python.
• Sorting database records in database management systems.
• Sorting large datasets in scientific computing, such as in numerical simulations
and data analysis.
• Sorting search results in web applications and e-commerce platforms.
Overall, quick sort is a versatile and widely used algorithm that can be applied in a
variety of domains where sorting is required. Its low average-case time
complexity and simplicity of execution make it an appealing choice for efficiently
sorting large datasets.
#include <stdio.h> void quickSort(int arr[], int low, int high) {
if (low < high) {
// Function to swap two elements int pi = partition(arr, low, high);
void swap(int* a, int* b) { quickSort(arr, low, pi - 1);
int t = *a; quickSort(arr, pi + 1, high);
*a = *b; }
*b = t; }
} // Function to print the array
int partition(int arr[], int low, int high) { void printArray(int arr[], int size) {
int pivot = arr[high]; int i;
int i = (low - 1); for (i = 0; i < size; i++)
printf("%d ", arr[i]);
for (int j = low; j <= high - 1; j++) { printf("\n");
if (arr[j] < pivot) { }
i++;
swap(&arr[i], &arr[j]); int main() {
} int arr[] = { 12, 17, 6, 25, 1, 5 };
} int n = sizeof(arr) / sizeof(arr[0]);
swap(&arr[i + 1], &arr[high]); quickSort(arr, 0, n - 1);
return (i + 1); printf("Sorted array: \n");
} printArray(arr, n);
return 0;
}