Sorting an array in C involves arranging the elements of the array in a specific order (either ascending or descending). There are several sorting algorithms available, each with its own approach and efficiency. Some common sorting algorithms include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. Below, we'll discuss a few of these methods, particularly focusing on Selection Sort and Quick Sort, and provide example implementations for both.

Selection Sort

Selection Sort is a simple sorting algorithm that works by repeatedly selecting the smallest (or largest, depending on the order) element from the unsorted part of the array and moving it to the sorted part.

Steps of Selection Sort:

1. Start with the first element as the minimum.
2. Compare it with the rest of the array to find the actual minimum.
3. Swap the minimum found with the first element.
4. Move to the next position and repeat until the entire array is sorted.

C Program to Sort an Array Using Selection Sort

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    // One by one move the boundary of the unsorted subarray
    for (i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements in the array

    printf("Unsorted array: \n");
    printArray(arr, n);

    selectionSort(arr, n); // Sort the array using Selection Sort

    printf("Sorted array: \n");
    printArray(arr, n); // Print the sorted array

    return 0;
}

Explanation of the Selection Sort Program:

1. Function Definitions:

   • void selectionSort(int arr[], int n): This function implements the Selection Sort algorithm, taking an array and its size as arguments.
   • void printArray(int arr[], int size): This function prints the elements of the array.

2. Selection Sort Logic:

   • The outer loop iterates through each element of the array.
   • The inner loop finds the index of the minimum element in the remaining unsorted part.
   • After finding the minimum, it swaps it with the first element of the unsorted part.

3. Main Function:

   • An integer array is defined and initialized.
   • The size of the array is calculated.
   • The unsorted array is printed before sorting.
   • The selectionSort function is called to sort the array.
   • The sorted array is printed after sorting.

Sample Output:

Unsorted array:
64 25 12 22 11 
Sorted array:
11 12 22 25 64 

Quick Sort

Quick Sort is a more efficient, divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

Steps of Quick Sort:

1. Choose a pivot element from the array.
2. Partition the array into two halves:
   • Elements less than the pivot.
   • Elements greater than the pivot.
3. Recursively apply the above steps to the sub-arrays.

C Program to Sort an Array Using Quick Sort

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function for Quick Sort
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing the rightmost element as pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j < high; 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
        }
    }
    swap(&arr[i + 1], &arr[high]); // Swap the pivot element with the element at i + 1
    return (i + 1); // Return the partitioning index
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at the right place
        int pi = partition(arr, low, high);

        // Recursively sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements in the array

    printf("Unsorted array: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1); // Sort the array using Quick Sort

    printf("Sorted array: \n");
    printArray(arr, n); // Print the sorted array

    return 0;
}

Explanation of the Quick Sort Program:

1. Function Definitions:

   • void swap(int *a, int *b): This function swaps two integers.
   • int partition(int arr[], int low, int high): This function partitions the array based on the pivot.
   • void quickSort(int arr[], int low, int high): This function implements the Quick Sort algorithm.

2. Quick Sort Logic:

   • The partition function selects a pivot and rearranges the array so that elements less than the pivot come before it and those greater come after it.
   • The quickSort function recursively sorts the sub-arrays.

3. Main Function:

   • An integer array is defined and initialized.
   • The size of the array is calculated.
   • The unsorted array is printed before sorting.
   • The quickSort function is called to sort the array.
   • The sorted array is printed after sorting.

Sample Output:

Unsorted array:
10 7 8 9 1 5 
Sorted array:
1 5 7 8 9 10 

Key Points:

• Time Complexity: The average time complexity of Quick Sort is $O(n \log n)$, but its worst-case complexity is $O(n^2)$ (which can happen when the smallest or largest element is always chosen as the pivot).
• Space Complexity: Quick Sort has a space complexity of $O(\log n)$ due to recursive calls.
• In-Place Sorting: Quick Sort is an in-place sorting algorithm, meaning it requires only a small, constant amount of additional storage space.

Conclusion

Sorting an array in C can be accomplished using various algorithms, each with its strengths and weaknesses. Understanding these sorting algorithms can greatly enhance your problem-solving skills in programming. You can implement additional sorting algorithms based on your specific requirements and data sets.