Sorting Algorithms in C

This repository contains implementations of several sorting algorithms in C. These algorithms demonstrate various approaches to sorting arrays of structures, specifically focusing on sorting people by their ages. This work was developed as part of an assignment for the Data Structures course at the Federal University of Alagoas.

Table of Contents

• Insertion Sort
• Quick Sort
• Radix Sort
• Bin Sort
• Merge Sort

---

Insertion Sort

Description:
Insertion Sort is a simple sorting algorithm that builds the sorted array one element at a time. It's efficient for small datasets and is adaptive, meaning it performs better on nearly sorted data.

void insertSort(Pessoa pessoas[], int n) {
    for (int i = 1; i < n; i++) {
        Pessoa chave = pessoas[i];
        int j = i - 1;
        while (j >= 0 && pessoas[j].idade > chave.idade) {
            pessoas[j + 1] = pessoas[j];
            j--;
        }
        pessoas[j + 1] = chave;
    }
}

Quick Sort

Description:
Quick Sort is a highly efficient sorting algorithm based on the divide-and-conquer principle. It works by selecting a 'pivot' element and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

void quickSort(Pessoa arr[], int low, int high) {
    if (low < high) {
        int pi = particionar(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Radix Sort

Description:
Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. It utilizes counting sort as a subroutine to sort the digits efficiently.

void radixSort(Pessoa arr[], int n) {
    int max = arr[0].idade;
    for (int i = 1; i < n; i++)
        if (arr[i].idade > max)
            max = arr[i].idade;

    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

Bin Sort

Description:
Bin Sort, also known as Bucket Sort, is an algorithm that distributes elements into different bins (or buckets) and then sorts these bins individually. It is particularly useful when the input is uniformly distributed.

void binSort(Pessoa arr[], int n) {
    int i, j;
    int idadeMax = IDADE_MAX;
    Pessoa bins[idadeMax + 1][n];
    int count[idadeMax + 1];

    for (i = 0; i <= idadeMax; i++) {
        count[i] = 0;
    }

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

    int indice = 0;
    for (i = 0; i <= idadeMax; i++) {
        for (j = 0; j < count[i]; j++) {
            arr[indice++] = bins[i][j];
        }
    }
}

Merge Sort

Description:
Merge Sort is a divide-and-conquer sorting algorithm. It recursively splits the array into halves, sorts each half, and merges them back together in sorted order.

void mergeSort(Pessoa 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);
    }
}