Escreva uma função que verifica se um vetor de números inteiros está ou não ordenado crescentemente. Além do vetor de inteiros, sua função deve receber, como parâmetro, um número inteiro indicando o tamanho do vetor.
Passo 1
O que o enunciado pede e o que ele nos dá:
- Foi pedido para escrever uma função que verifica se um vetor de números inteiros está ordenado crescentemente.
- A função deve receber:
- um vetor de inteiros (vou chamar de
); - um inteiro indicando o tamanho do vetor (vou chamar de
).
- um vetor de inteiros (vou chamar de
- Resultado esperado: a função deve indicar “sim” ou “não” (ou equivalentemente devolver um valor lógico) dizendo se
está ordenado crescentemente. - Observação importante que não está no enunciado: a expressão “ordenado crescentemente” pode significar duas coisas ligeiramente diferentes:
- ordenação não-decrescente (permitindo elementos iguais): para todo
vale ; - ordenação estritamente crescente (sem repetições): para todo
vale .
- ordenação não-decrescente (permitindo elementos iguais): para todo
- Neste problema a função deve receber apenas
e ; a implementação deve lidar corretamente com casos triviais (por exemplo, ou ).
Passo 2
Escolha do comportamento e do método:
- Vou explicar e fornecer as duas versões (não-decrescente e estrita). Assim você poderá usar a que o professor espera.
- Método escolhido: percorrer o vetor uma única vez comparando elementos adjacentes. Essa é a forma mais direta e eficiente para verificar ordenação quando só se tem o vetor e seu tamanho.
- Intuição do método (sem programar ainda): se existir algum índice
com tal que a comparação entre e viole a condição de ordenação, então o vetor não está ordenado; caso contrário, está ordenado. - Esse método é simples de implementar, rápido (varre o vetor uma vez) e fácil de justificar.
Passo 3
Explicação detalhada do algoritmo (passo a passo lógico):
- Se
então o vetor tem zero ou um elemento; por definição isso é ordenado. Então a função deve retornar “verdadeiro”. - Caso
, faça um laço com índice que percorre . - Em cada iteração compare
e : - Para verificar ordenação não-decrescente: se
então existe uma violação e o vetor não está ordenado — retorna “falso” imediatamente (early exit). - Para verificar ordenação estrita: se
então existe violação e retorna “falso”.
- Para verificar ordenação não-decrescente: se
- Se o laço terminar sem encontrar violação, retorna “verdadeiro”.
- Justificativa de corretude (breve): ao retornar “falso” detecta-se a primeira violação
(ou no caso estrito). Se nenhuma violação aparece, então por construção todos os pares adjacentes satisfazem a propriedade, logo a sequência inteira satisfaz a ordenação desejada.
Passo 4
Complexidade e propriedades importantes (o que levar para a prova)
- Tempo: percorre no máximo
comparações, logo a complexidade temporal é . - Espaço: usa apenas algumas variáveis de índice, logo a complexidade espacial é
. - Propriedade “early exit”: se há uma violação cedo no vetor, o algoritmo para imediatamente; isso pode ser vantajoso em muitos casos práticos.
- Casos de borda:
-
ou : sempre retorna verdadeiro. - Vetor já ordenado: percorre todo o vetor e retorna verdadeiro.
- Vetor com primeira violação em posição
: faz comparações e retorna falso.
-
Passo 5
Exemplos concretos e passo a passo manual (para treinar)
- Exemplo 1:
, . Usando não-decrescente: - comparar
com : OK. - comparar
com : OK. - comparar
com : OK. - sem violações → vetor ordenado (retorna verdadeiro).
- comparar
- Exemplo 2:
, . - comparar
com : OK. - comparar
com : é falso → violação → retorna falso.
- comparar
- Exemplo 3 (estrito):
não é estritamente crescente porque existe e com → violação para a versão estrita.
Passo 6
Como implementar na prova (dicas de escrita e o que retornar)
- Se a linguagem da prova for C, é comum escrever a função com assinatura:
- para não-decrescente:
int is_sorted(const int v[], int n) - para estrita:
int is_strictly_sorted(const int v[], int n) - retornar
1para verdadeiro e0para falso (outrue/falsese a linguagem suportarbool).
- para não-decrescente:
- Comentários importantes que você pode escrever ao lado do código na prova:
- indicar que
tem índices válidos de a ; - mostrar que o laço vai de
até ; - explicar que a função retorna imediatamente quando encontra uma violação.
- indicar que
Passo 7
Código de exemplo (duas versões) — leia com calma e copie no enunciado da prova se pedir função:
- Abaixo estão duas funções em C: uma verifica ordenação não-decrescente (permite repetições) e outra verifica ordenação estrita (sem repetições). Ambas recebem o vetor
e o inteiro como pedido.
Resposta
/* Verifica se o vetor v (tamanho n) está ordenado NÃO-DECRESCENTE:
retorna 1 se estiver ordenado (v[i] <= v[i+1] para todo i), caso contrário retorna 0. */
int is_sorted(const int v[], int n) {
if (n <= 1) return 1; /* vetores vazios ou de um elemento são ordenados */
for (int i = 0; i <= n - 2; ++i) {
if (v[i] > v[i + 1]) return 0; /* violação encontrada: não está ordenado */
}
return 1; /* nenhuma violação: está ordenado */
}
/* Verifica se o vetor v (tamanho n) está ordenado ESTRITAMENTE CRESCENTE:
retorna 1 se estiver estritamente crescente (v[i] < v[i+1] para todo i), caso contrário retorna 0. */
int is_strictly_sorted(const int v[], int n) {
if (n <= 1) return 1;
for (int i = 0; i <= n - 2; ++i) {
if (v[i] >= v[i + 1]) return 0; /* violação para estrito: elementos iguais também invalidam */
}
return 1;
}