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
, digamos
. A saída deve ser outra sequência
que seja uma permutação de
.
Passo 4
Por fim, formalizamos o requisito de ordenação: a permutação
deve satisfazer a condição de não decrescimento. Ou seja, para todo índice
tal que
, vale
.
Resposta
Dado um inteiro positivo
e uma sequência de elementos
extraídos de um conjunto com relação de ordem total, encontrar uma permutação
de
que satisfaça
Em outras palavras, produzir uma reordenação da sequência original de forma que os elementos fiquem em ordem não decrescente.