Algoritmos de Ordenação

Ordenação é o processo de reorganizar elementos de uma estrutura de dados em uma determinada ordem, geralmente crescente ou decrescente. É fundamental para otimizar buscas, análises e visualização de dados.

Bubble Sort

Algoritmo simples que compara pares de elementos adjacentes e os troca de posição se estiverem fora de ordem.

• Complexidade:
  • Melhor caso: \( \mathcal{O}(n) \) (lista já ordenada)
  • Médio e pior caso: \( \mathcal{O}(n^2) \)
• Vantagem: fácil de implementar
• Desvantagem: ineficiente para grandes volumes de dados

Exemplo

void bubble_sort(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;
            }
}

Selection Sort

Percorre a lista para encontrar o menor (ou maior) elemento e o coloca na posição correta, repetindo o processo para o restante.

• Complexidade:
  • Melhor, médio e pior caso: \( \mathcal{O}(n^2) \)
• Vantagem: número fixo de trocas
• Desvantagem: número elevado de comparações, mesmo com lista parcialmente ordenada

Exemplo

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

Insertion Sort

Constrói a lista ordenada inserindo cada novo elemento na posição correta, comparando com os anteriores.

• Complexidade:
  • Melhor caso: \( \mathcal{O}(n) \) (lista quase ordenada)
  • Médio e pior caso: \( \mathcal{O}(n^2) \)
• Vantagem: eficiente para listas pequenas ou quase ordenadas
• Desvantagem: desempenho ruim com listas grandes desordenadas

Exemplo

void insertion_sort(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--];
        arr[j + 1] = key;
    }
}

Merge Sort

Divide a lista em sublistas, ordena cada uma recursivamente e as combina (merge) de forma ordenada.

• Complexidade:
  • Todos os casos: \( \mathcal{O}(n \cdot \log n) \)
• Vantagem: desempenho estável e previsível
• Desvantagem: exige memória adicional para as sublistas

Exemplo

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

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

Quick Sort

Escolhe um pivô, separa os elementos menores à esquerda e maiores à direita, e aplica o mesmo processo recursivamente.

• Complexidade:
  • Melhor e médio caso: \( \mathcal{O}(n \cdot \log n) \)
  • Pior caso: \( \mathcal{O}(n^2) \) (quando a partição é desequilibrada)
• Vantagem: muito rápido na prática
• Desvantagem: sensível à escolha do pivô e não estável

Exemplo

int partition(int arr[], int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            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 quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

Resumo Comparativo

Aplicações na Engenharia

Algoritmos de ordenação são essenciais para:

• Pré-processamento de sinais e dados sensoriais;
• Organização de logs, eventos e registros;
• Otimização de algoritmos de busca e decisão em sistemas embarcados.

A escolha do algoritmo depende do tamanho da entrada, recursos do sistema e necessidade de desempenho determinístico.