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])
}
}
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
de
até
e o laço interno faz
descer de
até
, sempre comparando
com
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
de
até
e, para cada
, percorre-se o subvetor de
até
procurando o índice
do maior elemento. Ao fim dessa busca, troca-se
com
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
- O primeiro algoritmo é bubble sort.
- O segundo algoritmo é selection sort.