Considerando os trechos de código abaixo, qual seriam esses algoritmos de ordenação? Por quê?
procedure XXXXXX( A : list of sortable items )
 n = length(A)
 for each i in 1 to n-1 inclusive {
 for each j in n-1 to i inclusive{
 if A[j-1] > A[j] {
 swap(A[j-1], A[j])
 }
 }
 }
end procedure
XXXXXXXXXX-SORT(A)
 n = length(A)
 for i }\leftarrow\textrm{n}\mathrm{ downto 2 {
 max}\leftarrow\textrm{i
 for j }\leftarrow1 to i{x
 if A[j] > A[max] {
 max }\leftarrow\textrm{j
 }
 }
 swap (A[i], A[max])
 }
}

Passo 1

O enunciado apresenta dois trechos de pseudocódigo que implementam algoritmos de ordenação. No primeiro, há um duplo laço aninhado que compara e troca elementos adjacentes; no segundo, o laço externo decresce e, dentro dele, escolhe-se o maior elemento restante para trocá-lo com a posição final. Para identificar qual é qual, vamos reconhecer os padrões clássicos de bubble sort e selection sort.

Passo 2

No primeiro trecho, o laço externo varia i de 1 até n-1 e o laço interno faz j descer de n-1 até i, sempre comparando
A[j-1]
com
A[j]
e trocando-os se o anterior for maior. Esse processo faz com que, a cada passagem completa do laço interno, o maior elemento da parte não ordenada “borbulhe” até o fim do vetor. Esse comportamento é justamente a característica do bubble sort (ordenação por bolha).

Passo 3

No segundo trecho, o laço externo varia i de n até 2 e, para cada i, percorre-se o subvetor de 1 até i procurando o índice \mathrm{max} do maior elemento. Ao fim dessa busca, troca-se
A[i]
com
A[\mathrm{max}]
colocando o maior elemento da parte não ordenada na sua posição final com apenas uma troca. Esse padrão de selecionar o maior e posicioná-lo é exatamente o selection sort (ordenação por seleção).

Resposta

  1. O primeiro algoritmo é bubble sort.
  2. O segundo algoritmo é selection sort.

Exercícios relacionados