Category: Data Structure Using 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 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 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 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 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, 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.