Algoritmos de Ordenação em C - Bubble Sort, Shell Sort, Quick Sort e mais

Introdução

Algoritmos de ordenação são amplamente utilizados em ciência da computação e em diversos setores da indústria. Eles têm a capacidade de organizar dados de forma sistemática, permitindo que os desenvolvedores e analistas de dados possam acessar informações com mais facilidade e eficiência. Neste artigo, iremos explorar os algoritmos de ordenação em C mais populares, incluindo Bubble Sort, Shell Sort, Quick Sort, entre outros. Também discutiremos qual algoritmo é o mais rápido e por que.

Bubble Sort 🧼

O Bubble Sort é um dos algoritmos de ordenação mais simples e intuitivos. Ele opera comparando pares adjacentes de elementos na lista e trocando-os de posição se estiverem fora de ordem. O processo é repetido várias vezes até que a lista esteja ordenada.

A implementação do Bubble Sort em C pode ser feita da seguinte maneira:

void bubble_sort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (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;
            }
        }
    }
}

O Bubble Sort é fácil de entender e implementar, mas sua complexidade é de O(n²). Portanto, ele pode ser ineficiente para listas maiores.

Shell Sort 🐚

O Shell Sort é um algoritmo de ordenação que é uma extensão do Bubble Sort. Ele divide a lista em sub-listas menores e aplica o Bubble Sort a cada uma delas, ordenando assim os elementos da lista. A ideia é reduzir o número de elementos a serem comparados em cada iteração.

A implementação do Shell Sort em C pode ser feita da seguinte maneira:

void shell_sort(int arr[], int n) {
    int gap, i, j, temp;
    for (gap = n/2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

O Shell Sort tem uma complexidade de O(n log n) no melhor caso e O(n²) no pior caso, tornando-o mais eficiente do que o Bubble Sort para listas maiores.

Quick Sort ⚡

O Quick Sort é um algoritmo de ordenação que é amplamente utilizado devido à sua eficiência. Ele seleciona um elemento, o pivô, da lista e divide a lista em duas sub-listas, uma com elementos menores do que o pivô e outra com elementos maiores. O processo é repetido recursivamente até que a lista esteja ordenada.

A implementação do Quick Sort em C pode ser feita da seguinte maneira:

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pivot_index = partition(arr, low, high);
        quick_sort(arr, low, pivot_index - 1);
                quick_sort(arr, pivot_index + 1, high);
    }
}

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

O Quick Sort tem uma complexidade de O(n log n) no melhor caso e O(n²) no pior caso. Ele é frequentemente usado em aplicações que exigem alta velocidade de processamento, como processamento de imagens e análise de dados.

Merge Sort 🦀

O Merge Sort é um algoritmo de ordenação que divide a lista em duas partes iguais e as ordena separadamente. Em seguida, as duas listas ordenadas são mescladas para formar uma lista ordenada final.

A implementação do Merge Sort em C pode ser feita da seguinte maneira:

void merge_sort(int arr[], int low, int high) {
    if (low < high) {
        int middle = low + (high - low) / 2;
        merge_sort(arr, low, middle);
        merge_sort(arr, middle + 1, high);
        merge(arr, low, middle, high);
    }
}

void merge(int arr[], int low, int middle, int high) {
    int i, j, k;
    int n1 = middle - low + 1;
    int n2 = high - middle;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++) {
        L[i] = arr[low + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[middle + 1 + j];
    }
    i = 0;
    j = 0;
    k = low;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

O Merge Sort tem uma complexidade de O(n log n) no pior caso, tornando-o mais eficiente do que o Bubble Sort e o Shell Sort para listas maiores. No entanto, ele usa mais memória do que outros algoritmos de ordenação, pois requer uma lista temporária para a mesclagem.

Counting Sort 🔢

O Counting Sort é um algoritmo de ordenação que é eficiente para listas com um número limitado de valores possíveis. Ele conta o número de ocorrências de cada valor na lista e, em seguida, recria a lista em ordem crescente.

A implementação do Counting Sort em C pode ser feita da seguinte maneira:

void counting_sort(int arr[], int n, int k) {
    int i, j;
    int count[k+1];
    int output[n];
    for (i = 0; i <= k; i++) {
        count[i] = 0;
    }
    for (i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    for (i = 1; i <= k; i++) {
        count[i] += count[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

O Counting Sort tem uma complexidade de tempo de execução O(n + k), onde n é o número de elementos na lista e k é o maior valor na lista. Ele é um algoritmo de ordenação estável, o que significa que a ordem relativa dos elementos iguais é preservada. No entanto, ele só é eficiente quando k é relativamente pequeno em relação a n.

Conclusão 📚

Neste artigo, apresentamos vários algoritmos de ordenação em C, incluindo o Bubble Sort, o Shell Sort, o Quick Sort, o Merge Sort e o Counting Sort. Cada um desses algoritmos tem suas vantagens e desvantagens, dependendo do tamanho da lista e do número de elementos únicos na lista.

Em geral, o Quick Sort é frequentemente usado em aplicações que exigem alta velocidade de processamento, enquanto o Merge Sort é mais eficiente do que o Bubble Sort e o Shell Sort para listas maiores. O Counting Sort é eficiente para listas com um número limitado de valores possíveis, mas só é eficiente quando k é relativamente pequeno em relação a n.

Ao escolher um algoritmo de ordenação para um determinado problema, é importante levar em consideração a complexidade de tempo de execução, a eficiência de memória e a estabilidade da ordem relativa dos elementos iguais. Com as informações fornecidas neste artigo, esperamos que você tenha uma compreensão sólida dos diferentes algoritmos de ordenação disponíveis em C e possa escolher o melhor para seus próprios projetos.