Sorting

Sorting is the process of arranging data in a specific order, typically in ascending or descending order. Sorting is crucial in computer science as it enhances the efficiency of search operations and helps in data organization.

Types of Sorting Techniques

Sorting techniques can be broadly categorized into two types:

1. Comparison-Based Sorting
   • Bubble Sort
   • Selection Sort
   • Insertion Sort
   • Merge Sort
   • Quick Sort
   • Heap Sort
2. Non-Comparison-Based Sorting
   • Counting Sort
   • Radix Sort
   • Bucket Sort

---

Common Sorting Algorithms in C

1. Bubble Sort

• A simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.
• Time Complexity:
  • Best Case: O(n)O(n)O(n) (already sorted array)
  • Worst Case: O(n2)O(n^2)O(n2)

C Code Example:

cCopy code#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 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;
}

---

2. Selection Sort

• Divides the array into a sorted and unsorted part, repeatedly finding the minimum element from the unsorted part.
• Time Complexity: O(n2)O(n^2)O(n2) for all cases.

C Code Example:

cCopy codevoid selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum with the first element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

---

3. Insertion Sort

• Builds the sorted array one element at a time by inserting each element into its correct position.
• Time Complexity:
  • Best Case: O(n)O(n)O(n) (already sorted array)
  • Worst Case: O(n2)O(n^2)O(n2)

C Code Example:

cCopy codevoid 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--;
        }
        arr[j + 1] = key;
    }
}

---

4. Merge Sort

• A divide-and-conquer algorithm that divides the array into halves, sorts each half, and merges them.
• Time Complexity: O(nlog⁡n)O(n \log n)O(nlogn) for all cases.

C Code Example:

cCopy codevoid merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

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);
    }
}

---

5. Quick Sort

• A divide-and-conquer algorithm that selects a pivot and partitions the array around it.
• Time Complexity:
  • Best/Average Case: O(nlog⁡n)O(n \log n)O(nlogn)
  • Worst Case: O(n2)O(n^2)O(n2) (for a poorly chosen pivot)

C Code Example:

cCopy codeint 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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    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);
    }
}

---

Comparison of Sorting Algorithms

Algorithm	Time Complexity (Best)	Time Complexity (Worst)	Space Complexity	Stability
Bubble Sort	O(n)O(n)O(n)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	Stable
Selection Sort	O(n2)O(n^2)O(n2)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	Unstable
Insertion Sort	O(n)O(n)O(n)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	Stable
Merge Sort	O(nlog⁡n)O(n \log n)O(nlogn)	O(nlog⁡n)O(n \log n)O(nlogn)	O(n)O(n)O(n)	Stable
Quick Sort	O(nlog⁡n)O(n \log n)O(nlogn)	O(n2)O(n^2)O(n2)	O(log⁡n)O(\log n)O(logn)	Unstable

---

Applications

• Bubble/Selection/Insertion Sort: Suitable for small datasets.
• Merge Sort: Used in external sorting and linked lists.
• Quick Sort: Widely used in systems with in-memory sorting requirements.
• Counting/Radix/Bucket Sort: Suitable for numeric data.

Sorting is a foundational concept in computer science that plays a significant role in improving algorithmic efficiency and data management.