Algorithm in c

Introduction to searching and sorting algorithm

Searching and sorting are fundamental operations in computer science and programming. These algorithms play a crucial role in organizing and retrieving information efficiently from data sets. In this introduction, we’ll briefly explain searching and sorting algorithms and provide an overview of their significance in the context of programming using the C language.

Searching Algorithms:

Searching algorithms are used to find a specific value within a collection of data. Whether it’s locating a particular element in an array or searching for a specific record in a database, efficient searching is essential for fast data retrieval.

One common searching algorithm is the Linear Search. In C, this algorithm involves iterating through an array sequentially and comparing each element with the target value until a match is found or the entire array is traversed. Another widely used searching algorithm is the Binary Search, which is applicable only to sorted arrays. Binary Search repeatedly divides the array into halves and narrows down the search range by comparing the middle element with the target value. This results in significantly faster searching compared to Linear Search, especially for large datasets.

Sorting Algorithms:

Sorting algorithms arrange elements in a specific order, such as ascending or descending. Organizing data is crucial for efficient retrieval, data presentation, and various other operations.

One of the simplest sorting algorithms is the Bubble Sort. It involves iterating through the array multiple times, comparing adjacent elements, and swapping them if they are in the wrong order. Bubble Sort continues these passes until the entire array is sorted. Selection Sort is another basic sorting algorithm. It works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and placing it in the correct position in the sorted portion.

More advanced sorting algorithms include Insertion Sort, which builds the sorted array one element at a time by inserting elements in their correct positions, and Merge Sort, which divides the array into smaller sub-arrays, sorts them, and then merges them back together to obtain the final sorted array.

Quick Sort is a highly efficient sorting algorithm that works by selecting a ‘pivot’ element, partitioning the array into elements smaller and larger than the pivot, and recursively sorting these partitions. Each sorting algorithm has its own advantages and disadvantages in terms of time complexity, space complexity, and performance characteristics. The choice of algorithm depends on factors such as the size of the dataset, the existing order of the data, and the desired efficiency.

In the C programming language, you can implement these searching and sorting algorithms by utilizing loops, conditional statements, and appropriate data structures like arrays. Understanding these algorithms is essential for any programmer, as they provide the foundation for solving various data-related problems efficiently.

Implementation of Bubble Sort and Insertion Sort

Bubble Sort

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 no swaps are needed, which means the list is now sorted. Bubble Sort gets its name because smaller elements “bubble” to the top of the list while larger elements “sink” to the bottom.

Algorithm Explanation:

1. Start with an unsorted array of elements.
2. Compare the first element with the second element. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements (second and third) and compare them. Again, swap if necessary.
4. Continue this process for every adjacent pair of elements in the array. After the first pass, the largest element will have “bubbled up” to the end of the array.
5. Repeat the process for the remaining unsorted elements (excluding the last one, which is already sorted after the previous pass). This will push the next largest element to its correct position.
6. Continue these passes until no more swaps are needed. This indicates that the entire array is now sorted.

Here’s a simple implementation of the Bubble Sort algorithm in C:

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap the elements
                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]);

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

    bubbleSort(arr, n);

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

    return 0;
}
Output: -
Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 
[program terminated]

Bubble Sort is easy to understand and implement, but it is not very efficient, especially for large lists. Its average and worst-case time complexity is O(n^2), where ‘n’ is the number of elements in the list. This makes it less suitable for sorting large datasets compared to more advanced sorting algorithms like Quick Sort or Merge Sort, which have better time complexities.

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is particularly efficient for small datasets or nearly sorted arrays. The idea behind Insertion Sort is to iterate through the input array, repeatedly moving elements that are out of order to their correct positions within the sorted portion of the array.

Algorithm Explanation:

1. Start with the second element (index 1) of the array.
2. Compare the second element with the first element (sorted portion). If it’s smaller, swap them.
3. Move to the third element and compare it with the elements in the sorted portion. Insert it in the correct position by shifting larger elements to the right.
4. Continue this process for each element in the array, moving through the unsorted portion and placing them in their correct positions within the sorted portion.
5. Repeat until the entire array is sorted.

Here’s a simple implementation of the Insertion Sort algorithm in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j, key;
    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]);
    
        printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }


    insertionSort(arr, n);
    

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

    return 0;
}
Output: -
Original array: 12 11 13 5 6 
Sorted array: 5 6 11 12 13 
[program terminated]

Insertion Sort has an average and worst-case time complexity of O(n^2), where n is the number of elements in the array. However, it can perform very efficiently on small datasets or partially sorted arrays due to its adaptive nature.

Read more about programming in c: –
Data type and Operator in C: – https://xcoode.co.in/c_programming/data-type-and-operators-in-c/
if else statement in c: – https://xcoode.co.in/c_programming/if-else-statement-in-c/
Loop’s in c: – https://xcoode.co.in/c_programming/loop-in-c/

Follow us on: –
Facebook page: – https://www.facebook.com/groups/294849166389180
Quora : – https://xcoode404.quora.com/