Sorting is a fundamental concept in computer science that involves arranging elements in a specific order. In C programming, there are various techniques to sort elements in an array. Each sorting technique has its own logic and approach to organizing data. Understanding these sorting techniques can help us choose the most efficient method for different scenarios.

Let us start with various sorting technique using c programming.

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 the list is sorted.

Algorithm

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]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Full Code:

You can work with online GDB complier to execute any c programming code

#include <stdio.h>

void bubbleSort(int arr[], int n);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

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]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Explanation of the above code:

1. #include <stdio.h>: This line includes the standard input/output library, which provides functions like printf and scanf for input and output operations.
2. void bubbleSort(int arr[], int n);: This line is a function prototype for the bubbleSort function, which indicates that the function takes an integer array arr and its size n as arguments and returns nothing (void).
3. int main() {: This is the starting point of the program. The main function is the entry point for C programs.
4. int arr[] = {64, 34, 25, 12, 22, 11, 90};: This line declares an integer array arr and initializes it with the values {64, 34, 25, 12, 22, 11, 90}.
5. int n = sizeof(arr) / sizeof(arr[0]);: This line calculates the number of elements in the array arr by dividing the total size of the array by the size of a single element (arr[0]).
6. bubbleSort(arr, n);: This line calls the bubbleSort function to sort the array arr in ascending order.
7. printf("Sorted array: \n");: This line prints a message to the console indicating that the array is sorted.
8. for (int i = 0; i < n; i++) {: This line starts a for loop that iterates over each element of the sorted array.
9. printf("%d ", arr[i]);: Inside the loop, this line prints each element of the sorted array followed by a space.
10. printf("\n");: After printing all elements, this line prints a newline character to move to the next line in the console.
11. return 0;: This line indicates that the main function has successfully executed and returns 0 to the operating system, indicating successful termination of the program.
12. }: This closing brace marks the end of the main function.
13. void bubbleSort(int arr[], int n) {: This line defines the bubbleSort function, which takes an integer array arr and its size n as arguments and returns nothing (void).
14. for (int i = 0; i < n-1; i++) {: This line starts a for loop that iterates over each element of the array arr, except the last element.
15. for (int j = 0; j < n-i-1; j++) {: Inside the outer loop, this line starts another for loop that compares adjacent elements and swaps them if they are in the wrong order.
16. if (arr[j] > arr[j+1]) {: This line checks if the current element is greater than the next element in the array.
17. int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;: If the condition is true, this line swaps the current element with the next element using a temporary variable temp.
18. }: This closing brace marks the end of the inner for loop.
19. }: This closing brace marks the end of the outer for loop.
20. }: This closing brace marks the end of the bubbleSort function.

This code implements the bubble sort algorithm to sort an array of integers in ascending order. The algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order, bubbling the largest unsorted element to its correct position in each iteration.

Real Life Use of Bubble Sort-

Bubble Sort is rarely used in real-life applications due to its O(n^2) time complexity, which makes it inefficient for large datasets. It can be used for educational purposes or for sorting small datasets where simplicity is more important than efficiency.

Selection Sort:

Selection Sort is an in-place comparison sorting algorithm. It divides the input list into two parts: the sorted sublist and the unsorted sublist. Initially, the sorted sublist is empty, and the unsorted sublist contains all the elements.

Algorithm:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

How Does the above algorithm work?

1. The outer loop (with variable i) iterates through each element of the array from the first element to the second-to-last element (n-1). This loop selects the current position for the minimum element in the unsorted part of the array.
2. Inside the outer loop, the variable min_idx is initialized to the current value of i, indicating the index of the minimum element found so far in the unsorted part.
3. The inner loop (with variable j) starts from the element after the current position (i+1) and iterates through the remaining unsorted part of the array (i+1 to n-1). This loop finds the index of the minimum element in the unsorted part.
4. If the element at index j is less than the element at index min_idx, min_idx is updated to j, indicating that a smaller element has been found.
5. After finding the index of the minimum element in the unsorted part (min_idx), the algorithm swaps the element at index i with the minimum element. This ensures that the minimum element is placed at the correct position in the sorted part of the array.
6. The outer loop continues to iterate, with each iteration adding the next smallest element to the sorted part of the array by swapping it with the element at the beginning of the unsorted part.
7. Once the outer loop has completed all iterations, the array is sorted in ascending order.

Full Code:

#include <stdio.h>

void selectionSort(int arr[], int n);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

Real-life Use: Selection Sort is also not commonly used in real-life applications due to its O(n^2) time complexity, which makes it inefficient for large datasets. It can be used for educational purposes or for sorting small datasets.

Insertion Sort:

Imagine you have a deck of cards that are all mixed up, and you want to sort them from smallest to largest. You start with an empty hand and then pick up one card at a time from the deck.

1. Pick the first card from the deck and hold it in your hand. This represents the sorted part of the list (which starts with just one element).
2. Pick the next card from the deck and compare it to the cards in your hand from right to left.
3. If the new card is smaller than the card in your hand, move the card in your hand to the right to make space for the new card.
4. Repeat step 3 until you find the correct position for the new card in your hand.
5. Insert the new card into the correct position in your hand.
6. Repeat steps 2-5 until all cards from the deck are in your hand and the deck is empty.

Algorithm:

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

Full Code:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int 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);

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

    return 0;
}

Real Life Use of Insertion Sort:

Insertion Sort is efficient for small datasets or nearly sorted datasets. It is often used in scenarios where the dataset is expected to be small or nearly sorted, such as sorting a small list of names alphabetically.

Merge Sort:

Merge sort is a sorting algorithm that divides the unsorted list into n sublists, each containing one element, and then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining. This final sublist is the sorted list. It’s like sorting a deck of cards by dividing it into smaller piles, sorting each pile, and then merging the piles back together in order.

Algorithm:

void merge(int arr[], int l, int m, int r) {
    // Merge two subarrays of arr[]
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    // Merge the two subarrays
}

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

in the above code

The merge function takes three parameters: the array arr[] and the indices l, m, and r such that l <= m < r. It merges two subarrays of arr[]: one from l to m and another from m+1 to r. The function first creates temporary arrays to store the two subarrays, then merges the two subarrays into the original array in sorted order.

The mergeSort function recursively sorts the array. It takes three parameters: the array arr[] and the indices l and r such that l is the starting index and r is the ending index of the array. If l < r, the function calculates the middle index m and recursively calls mergeSort on the left and right halves of the array (l to m and m+1 to r). Finally, it merges the two sorted halves using the merge function.

#include <stdio.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 temporary arrays
    int L[n1], R[n2];

    // Copy data to temporary 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 temporary 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) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l + (r - l) / 2;

        // 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 arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Explanation of the whole code above in detail:

1. #include <stdio.h>: This line includes the standard input/output library, which is needed for functions like printf.
2. void merge(int arr[], int l, int m, int r) {: This defines a function merge that takes four arguments: an array arr[] and three integers l, m, and r.
3. int i, j, k;: These lines declare three integer variables i, j, and k.
4. int n1 = m - l + 1;: This calculates the size of the left subarray.
5. int n2 = r - m;: This calculates the size of the right subarray.
6. int L[n1], R[n2];: This declares two temporary arrays L and R to store the left and right subarrays.
7. for (i = 0; i < n1; i++): This loop copies the elements from the original array arr[] to the temporary array L[].
8. for (j = 0; j < n2; j++): This loop copies the elements from the original array arr[] to the temporary array R[].
9. i = 0; j = 0; k = l;: These lines initialize the indices for merging the left and right subarrays.
10. while (i < n1 && j < n2) {: This loop compares the elements of the left and right subarrays and merges them into the original array arr[].
11. if (L[i] <= R[j]) {: This condition checks if the element in the left subarray is less than or equal to the element in the right subarray.
12. arr[k] = L[i];: If the condition is true, it copies the element from the left subarray to the original array arr[].
13. i++;: It then increments the index i of the left subarray.
14. else {: If the condition is false (i.e., the element in the right subarray is smaller), it copies the element from the right subarray to the original array arr[].
15. arr[k] = R[j];: It then increments the index j of the right subarray.
16. k++;: Finally, it increments the index k of the original array arr[].
17. while (i < n1) {: This loop copies the remaining elements of the left subarray to the original array arr[].
18. while (j < n2) {: This loop copies the remaining elements of the right subarray to the original array arr[].
19. void mergeSort(int arr[], int l, int r) {: This defines a function mergeSort that takes three arguments: an array arr[] and two integers l and r.
20. if (l < r) {: This condition checks if the array has more than one element.
21. int m = l + (r - l) / 2;: This calculates the middle index of the array.
22. mergeSort(arr, l, m);: This recursively calls mergeSort for the left subarray.
23. mergeSort(arr, m + 1, r);: This recursively calls mergeSort for the right subarray.
24. merge(arr, l, m, r);: This calls the merge function to merge the left and right subarrays.
25. int main() {: This is the main function where the program starts execution.
26. int arr[] = {12, 11, 13, 5, 6, 7};: This initializes an array arr[] with some values.
27. int arr_size = sizeof(arr) / sizeof(arr[0]);: This calculates the size of the array arr[].
28. printf("Given array is \n");: This prints a message to indicate the given array.
29. mergeSort(arr, 0, arr_size - 1);: This calls the mergeSort function to sort the array.
30. printf("Sorted array is \n");: This prints a message to indicate the sorted array.
31. return 0;: This indicates that the program executed successfully.

Counting Sort:

Imagine you have a bunch of numbered balls, and you want to arrange them in order from smallest to largest. The counting sort algorithm works like this:

1. First, you find the largest number among all the balls. This helps you know the range of numbers you’re dealing with.
2. Then, you create a counting array, which is like having separate boxes for each number in the range. For example, if the largest number is 8, you’d have boxes numbered from 0 to 8.
3. Next, you go through all your balls and put each ball into its corresponding box. For example, if you have two balls with the number 2, you’d put them in box number 2.
4. After that, you modify your counting array so that each box now contains the number of balls less than or equal to its number. For example, if box number 5 contains 3 balls, it means there are 3 balls with numbers less than or equal to 5.
5. Now, you create a new array to hold your sorted balls. Starting from the end of your original array, you take each ball, find its box in the counting array, and place it in the new array at the position indicated by the count in that box. You also reduce the count in that box by 1.
6. Finally, you copy the sorted array back into your original array, and you’re done! All your balls are now in sorted order.

Algorithm:

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    int* count = (int*)calloc(max + 1, sizeof(int));
    int* output = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

1. Initialization: Create an auxiliary array count[] to store the count of each unique element and initialize all elements of count[] to 0. Also, find the maximum element in the input array arr[].
2. Counting: Traverse the input array arr[] and increment the count of the element at arr[i] in count[].
3. Cumulative Sum: Modify count[] to store the cumulative sum of counts. This step determines the position of each element in the output array.
4. Placement: Traverse the input array arr[] from the end. For each element arr[i], place it at index count[arr[i]] - 1 in the output array. Decrease count[arr[i]] by 1.
5. Result: The output array is the sorted array.

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

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    int* count = (int*)calloc(max + 1, sizeof(int));
    int* output = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    countingSort(arr, n);

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

    return 0;
}

In conclusion, understanding the logic behind different sorting techniques in C programming is crucial for writing efficient and effective code. Each sorting algorithm has its strengths and weaknesses, making them suitable for different scenarios. By grasping the underlying principles, programmers can choose the right sorting technique for a given problem, leading to faster and more optimized solutions.