Considere um vetor A com 11 elementos onde A 1A 7>A 8> cdots>A 11, 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.

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]:
  1. Inicialize i =7, j =11.
  2. Enquanto i faça:
    • troque A[i] e A[j]
    • i i+1, j j-1
  3. Crie vetor auxiliar D[1…11], e inicialize:
    i1, j7, p1.
  4. Enquanto i<=6 e j<=11 faça:
    • se A[i]<= A[j] então
      D[p] A[i]; i i+1
      senão
      D[p] A[j]; j j+1
    • p p+1
  5. Enquanto i<=6 faça:
    D[p] A[i]; i i+1; p p+1
  6. Enquanto j<=11 faça:
    D[p] A[j]; j j+1; p p+1
  7. Para k=1 até 11 faça:
    A[k] D[k]
Após esses passos, o vetor A estará completamente ordenado em ordem crescente.

Exercícios relacionados