Public App

Menu

Category: Data Structure Using C Language

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.

What is Stack in Data Structure?

In C language, a stack is an abstract data type that represents a collection of elements with two main operations: push and pop. It follows the Last In First Out (LIFO) principle, which means that the element added last to the stack will be the first one to be removed.

The stack can be implemented in C language using various data structures such as arrays, linked lists, and dynamic arrays. The most common implementation is using an array because it is simple and efficient.

In a stack implemented using an array, the top of the stack is represented by an index variable that points to the last element inserted in the stack. When an element is pushed into the stack, the top index is incremented, and when an element is popped, the top index is decremented.

Here is an example of defining a stack using an array in C language:

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

In this example, we defined a stack of a maximum size of 100, which is represented by the stack array. The top variable is initially set to -1, indicating that the stack is empty.

To perform stack operations, such as push and pop, we can use functions that manipulate the stack elements and the top index.

Operations on Stack

Here are the common operations that can be performed on a stack in C language:

Push

The push operation adds a new element to the top of the stack. The prototype of the push function is as follows

void push(int item);

Where item is the data item to be added to the stack.

Pop

The pop operation removes the top element from the stack. The prototype of the pop function is as follows

int pop();

The pop function returns the data item that was removed from the stack.

Peek

The peek operation returns the top element of the stack without removing it. The prototype of the peek function is as follows

int peek();

The peek function returns the data item at the top of the stack.

isEmpty

The isEmpty operation checks if the stack is empty. The prototype of the isEmpty function is as follows

int isEmpty();

The isEmpty function returns 1 if the stack is empty and 0 otherwise.

isFull

The isFull operation checks if the stack is full. This operation is only applicable when the stack is implemented using an array. The prototype of the isFull function is as follows

int isFull();

The isFull function returns 1 if the stack is full and 0 otherwise.

Here is an example implementation of these operations

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

void push(int item) {
    if (top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        top++;
        stack[top] = item;
    }
}

int pop() {
    int item;
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        item = stack[top];
        top--;
        return item;
    }
}

int peek() {
    if (top < 0) {
        printf("Stack is Empty\n");
        return -1;
    } else {
        return stack[top];
    }
}

int isEmpty() {
    if (top < 0) {
        return 1;
    } else {
        return 0;
    }
}

int isFull() {
    if (top >= MAX_SIZE - 1) {
        return 1;
    } else {
        return 0;
    }
}

Representation and Implementation of Stack

In C language, a stack can be implemented using an array or a linked list. Here is an example implementation of a stack using an array:

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

// Push operation
void push(int item) {
    if (top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        top++;
        stack[top] = item;
    }
}

// Pop operation
int pop() {
    int item;
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        item = stack[top];
        top--;
        return item;
    }
}

// Display operation
void display() {
    int i;
    if (top < 0) {
        printf("Stack is Empty\n");
    } else {
        printf("Stack elements are:\n");
        for (i = top; i >= 0; i--)
            printf("%d\n", stack[i]);
    }
}

In this implementation, the push operation adds an element to the top of the stack, the pop operation removes the top element from the stack, and the display operation displays all the elements of the stack.

Here is an example implementation of a stack using a linked list:

struct Node {
    int data;
    struct Node* next;
};

struct Node* top = NULL;

// Push operation
void push(int item) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = item;
    newNode->next = top;
    top = newNode;
}

// Pop operation
int pop() {
    int item;
    struct Node* temp;
    if (top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        temp = top;
        item = temp->data;
        top = top->next;
        free(temp);
        return item;
    }
}

// Display operation
void display() {
    struct Node* temp;
    if (top == NULL) {
        printf("Stack is Empty\n");
    } else {
        temp = top;
        printf("Stack elements are:\n");
        while (temp != NULL) {
            printf("%d\n", temp->data);
            temp = temp->next;
        }
    }
}

In this implementation, the push operation creates a new node with the given data and adds it to the top of the stack, the pop operation removes the top node from the stack and returns its data, and the display operation displays all the elements of the stack.