Defina formalmente o problema de ordenação.

Passo 1

O exercício pede para definirmos formalmente o problema de ordenação, que faz parte de algoritmos e estruturas de dados, e envolve tanto conceitos de sequência quanto de relações de ordem entre elementos.

Passo 2

Primeiro definimos os elementos básicos: uma sequência é uma lista ordenada de itens, e permutação é um rearranjo dessa lista. Além disso, precisamos de uma relação de ordem total, que nos permite comparar quaisquer dois elementos.

Passo 3

Agora especificamos a instância e o que esperamos como saída: a instância do problema é uma sequência de comprimento n, digamos (a1,a2,dots,an). A saída deve ser outra sequência (b1,b2,dots,bn) que seja uma permutação de (a1,dots,an).

Passo 4

Por fim, formalizamos o requisito de ordenação: a permutação (b1,dots,bn) deve satisfazer a condição de não decrescimento. Ou seja, para todo índice i tal que 1 <= i < n, vale bi <= bi+1.

Resposta

Dado um inteiro positivo n e uma sequência de elementos (a1,a2,dots,an) extraídos de um conjunto com relação de ordem total, encontrar uma permutação (b1,b2,dots,bn) de (a1,dots,an) que satisfaça
b1 <= b2 <= cdots <= bn
Em outras palavras, produzir uma reordenação da sequência original de forma que os elementos fiquem em ordem não decrescente.

Exercícios relacionados