Sorting Algorithms

Introduction

Sorting algorithms arrange elements in a specific order (ascending or descending) within a data structure. They are fundamental to computer science and are used in many applications including database operations, search optimization, and data analysis. Understanding different sorting techniques helps in choosing the most efficient approach for specific scenarios.

Key Concepts

Sorting: Arranging elements in a specific order Time Complexity: Computational time required relative to input size Space Complexity: Additional memory required by the algorithm Stability: Maintaining relative order of equal elements In-place Sorting: Sorting without requiring additional storage space

Bubble Sort

Algorithm and Implementation

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Characteristics:

• Time Complexity: O(n²)
• Space Complexity: O(1)
• Stable: Yes
• In-place: Yes

Selection Sort

Algorithm and Implementation

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        // Find minimum element in remaining array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap minimum element with first element
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Before sorting: ");
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    printf("After sorting: ");
    printArray(arr, n);
    
    return 0;
}

Characteristics:

• Time Complexity: O(n²)
• Space Complexity: O(1)
• Stable: No
• In-place: Yes

Insertion Sort

Algorithm and Implementation

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // Move elements greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original: ");
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    printf("Sorted: ");
    printArray(arr, n);
    
    return 0;
}

Characteristics:

• Time Complexity: O(n²) worst case, O(n) best case
• Space Complexity: O(1)
• Stable: Yes
• In-place: Yes

Quick Sort

Algorithm and Implementation

#include <stdio.h>

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // Swap arr[i+1] and arr[high] (pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        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]);
    
    printf("Original array: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Characteristics:

• Time Complexity: O(n log n) average, O(n²) worst case
• Space Complexity: O(log n)
• Stable: No
• In-place: Yes

Merge Sort

Algorithm and Implementation

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

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int *leftArr = (int*)malloc(n1 * sizeof(int));
    int *rightArr = (int*)malloc(n2 * sizeof(int));
    
    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];
    
    // Merge the temporary arrays back
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    
    // Copy remaining elements
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
    
    free(leftArr);
    free(rightArr);
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Given array: ");
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

Characteristics:

• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Stable: Yes
• In-place: No

Algorithm Comparison

Performance Analysis

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

void testSortingAlgorithm(void (*sortFunc)(int[], int), 
                         const char* name, 
                         int arr[], 
                         int size) {
    int *testArr = (int*)malloc(size * sizeof(int));
    memcpy(testArr, arr, size * sizeof(int));
    
    clock_t start = clock();
    sortFunc(testArr, size);
    clock_t end = clock();
    
    double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
    
    printf("%s: %.6f seconds\n", name, time_taken);
    
    free(testArr);
}

void generateRandomArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 1000;
    }
}

int main() {
    const int SIZE = 1000;
    int *arr = (int*)malloc(SIZE * sizeof(int));
    
    srand(time(NULL));
    generateRandomArray(arr, SIZE);
    
    printf("Comparing sorting algorithms with %d elements:\n", SIZE);
    
    testSortingAlgorithm(bubbleSort, "Bubble Sort", arr, SIZE);
    testSortingAlgorithm(selectionSort, "Selection Sort", arr, SIZE);
    testSortingAlgorithm(insertionSort, "Insertion Sort", arr, SIZE);
    
    free(arr);
    return 0;
}

Specialized Sorting Applications

Sorting Structures

#include <stdio.h>
#include <string.h>

struct Student {
    int rollNo;
    char name[30];
    float marks;
};

void sortStudentsByMarks(struct Student students[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (students[j].marks < students[j + 1].marks) {
                struct Student temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
            }
        }
    }
}

void displayStudents(struct Student students[], int n) {
    printf("Roll No\tName\t\tMarks\n");
    printf("-------\t----\t\t-----\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%-15s\t%.2f\n", 
               students[i].rollNo, 
               students[i].name, 
               students[i].marks);
    }
}

int main() {
    struct Student students[] = {
        {101, "Alice", 85.5},
        {102, "Bob", 92.0},
        {103, "Charlie", 78.5},
        {104, "Diana", 96.5},
        {105, "Eve", 88.0}
    };
    
    int n = sizeof(students) / sizeof(students[0]);
    
    printf("Before sorting:\n");
    displayStudents(students, n);
    
    sortStudentsByMarks(students, n);
    
    printf("\nAfter sorting by marks (descending):\n");
    displayStudents(students, n);
    
    return 0;
}

Algorithm Selection Guidelines

When to Use Each Algorithm:

Bubble Sort:

• Educational purposes
• Very small datasets
• Nearly sorted data

Selection Sort:

• Small datasets
• Memory is limited
• Simple implementation needed

Insertion Sort:

• Small to medium datasets
• Nearly sorted data
• Online sorting (data arrives continuously)

Quick Sort:

• Large datasets
• Average case performance important
• Memory efficiency required

Merge Sort:

• Large datasets
• Stable sorting required
• Worst-case performance guarantee needed

Best Practices

1. Choose appropriate algorithm based on data size and requirements
2. Consider stability if equal elements’ order matters
3. Analyze space constraints for memory-limited environments
4. Test with different data patterns (sorted, reverse sorted, random)
5. Use built-in library functions for production code when available

Summary

Sorting algorithms are essential tools in programming with different characteristics and use cases. Simple algorithms like bubble, selection, and insertion sort are easy to understand but inefficient for large datasets. Advanced algorithms like quick sort and merge sort offer better performance for larger data. The choice of sorting algorithm depends on factors including data size, memory constraints, stability requirements, and performance needs.

Part of BCA Programming with C Course (UGCOA22J201)