Considere um vetor
com 11 elementos onde
, ou seja, está ordenado em ordem crescente até o sexto elemento, e a partir desse elemento está ordenado em ordem decrescente. Dado o vetor da questão anterior, proponha um algoritmo para ordenar os elementos.
Passo 1
O enunciado apresenta um vetor bitônico de 11 elementos, ou seja, ele cresce de A₁ até A₆ e depois decresce de A₇ até A₁₁. A matéria envolvida é ordenação de vetores e, em particular, a técnica de mesclagem (merge) de duas subsequências já ordenadas.
Passo 2
Como o vetor está dividido em duas partes ordenadas (A₁…A₆ em ordem crescente e A₆…A₁₁ em ordem decrescente), podemos transformá-lo em duas subsequências ordenadas crescente–crescente e depois aplicar a operação de merge para obter um vetor totalmente ordenado.
Passo 3
Primeiro, invertemos a subsequência decrescente A₇…A₁₁ para torná-la crescente. Isso é feito trocando A[i] com A[j] enquanto i<j, onde inicialmente i=7 e j=11.
Em seguida, fazemos a mesclagem de duas subsequências ordenadas de A: A₁…A₆ e o que antes era A₇…A₁₁ (agora crescente). Usamos dois ponteiros (i na primeira parte e j na segunda) para comparar elementos e construir um vetor auxiliar D em ordem crescente.
Em seguida, fazemos a mesclagem de duas subsequências ordenadas de A: A₁…A₆ e o que antes era A₇…A₁₁ (agora crescente). Usamos dois ponteiros (i na primeira parte e j na segunda) para comparar elementos e construir um vetor auxiliar D em ordem crescente.
Passo 4
Por fim, copiamos o vetor auxiliar D de volta para A, garantindo que todo o vetor A fique ordenado.
Passo 5
A complexidade desse algoritmo é O(n), pois cada uma das fases (inversão e merge) percorre o vetor um número de vezes proporcional a n = 11.
Resposta
Pseudo-código do algoritmo OrdenaBitonico para A[1…11]:
-
Inicialize i
, j . -
Enquanto
faça: - troque
e -
,
- troque
-
Crie vetor auxiliar D[1…11], e inicialize:
, , . -
Enquanto
e faça: - se
então
;
senão
; -
- se
-
Enquanto
faça:
; ; -
Enquanto
faça:
; ; -
Para
até faça:
Após esses passos, o vetor A estará completamente ordenado em ordem crescente.