Executando verificação de segurança...
6

Alguns adendos que acho importante serem ditos, até porque quem não tem contato com cursos acadêmicos acaba perdendo.

Para que servem algoritmos de ordenamento?

Para facilitar a resolução de alguns problemas. Por exemplo, como determinar o maior elemento de uma array? E o menor elemento? Se for um array qualquer, você precisará percorrer todo o arranjo para então determinar qual é o elemento, tendo uma complexidade O(n), ou seja, o problema terá um custo cada vez maior ao passo que o tamanho do arranjo aumenta. Contudo, quando falamos de arranjos ordenados, a complexidade se torna O(1), pois sabemos exatamente onde estão os valores, na primeira e última posição.

Outra aplicação é também para algoritmos de busca. Temos dois tipos principais de buscas em um array: busca linear e busca binária. Na busca linear, percorremos todo o arranjo para encontrar ou determinar se um elemento não está no arranjo, trazendo uma complexidade O(n), contudo, em arranjos ordenados, podemos utilizar a busca binária, que resolve o problema com complexidade O(log(n)), que é muito melhor.

Outras formas de implementar o quicksort

O quicksort é um algoritmo recursivo de ordenamento por partição. Isso significa que ele determina duas partições de acordo com o elemento pivô e ordena elas, fazendo isso, recursivamente, até que todo o arranjo esteja ordenado. Segue uma implementação feita em C:

void quicksort(float *A, int size) {
  if (size == 2 && A[0] > A[1]) {
    int aux = A[0];
    A[0] = A[1];
    A[1] = aux;
  } else if (size > 2) {
    int x = A[size / 2];
    int i = 0, j = size - 1;

    do {
      while (A[i] < x)
        ++i;
      while (A[j] > x)
        --j;

      if (i <= j) {
        int aux = A[i];
        A[i] = A[j];
        A[j] = aux;
        ++i;
        --j;
      }
    } while (i <= j);
    if (j > 0)
      quicksort(A, j + 1);
    if (i < size)
      quicksort(&A[i], size - i);
  }
}

Perceba que, ao determinar o elemento pivô (nesse caso é sempre o elemento do meio do arranjo), o algoritmo verifica se existem elementos fora de ordem e, quando os encontra, troca eles de lugar, até que não existam mais nenhum elemento fora de lugar.

Resumindo, ao encontrar um elemento fora de ordem na partição 1 e outro na partição 2, o algoritmo os troca entre si, fazendo assim com que todos os elementos na esquerda do pivô sejam menores que ele e que todos os elementos na sua direita sejam maiores.

Mas há um porém que torna o algoritmo implementado no post ser menos eficiente, que é o fato de que sempre terão duas instâncias recursivas, além de se ter uma maior cópia de memória em cada uma das instâncias (são sempre criados dois arranjos, que somados tem tamanho n-1, o que faz com que seja gasta muita memória desnecessariamente.

O Quicksort tem complexidade O(nlog(n)) em geral, contudo no pior caso, onde todos os elementos se encontram em ordem inversa, tem complexidade O(n²), o que faz com que ele não seja exatamente o melhor algoritmo de ordenamento, mas mesmo assim se tornou o padrão em muitas linguagens.

Carregando publicação patrocinada...
2