(a) O que é ordem lexicográfica? (b) Na linguagem de programação C, como é determinada essa ordem? (c) Esboce um algoritmo que explica como é realizada a comparação lexicográfica entre duas strings.

Passo 1

Você me pediu três coisas claras:
(a) definição do que é ordem lexicográfica;
(b) como essa ordem é determinada na linguagem C;
(c) um esboço de algoritmo que explique como a comparação lexicográfica entre duas strings é feita.
Não há outros dados no enunciado — vou assumir que trabalhamos com strings típicas em C: sequências de bytes terminadas por um caractere nulo '\0'.

Passo 2

O que é, na prática, ordem lexicográfica — explicação intuitiva e relaxada.
Imagine o dicionário: palavras são ordenadas comparando letra por letra. A primeira letra diferente decide quem vem antes; se uma palavra é prefixo da outra (por exemplo, “casa” e “casal”), a mais curta vem primeiro. Isso é exatamente a ideia da ordem lexicográfica: comparar sequências elemento a elemento usando uma ordem já definida sobre os símbolos (por exemplo, a ordem das letras).

Passo 3

Definição formal (com notação simples).
Seja um alfabeto com ordem total (ou seja, para quaisquer dois símbolos x e y podemos dizer se x<y, x=y ou x>y). Seja cada string uma sequência de símbolos: s=(s_1,s_2,\dots,s_m) e t=(t_1,t_2,\dots,t_n). Dizemos que s<t lexicograficamente se, e somente se, existe um índice k tal que:
s_i = t_i \text{ para todo } i<k
e
s_k < t_k,
ou se s é prefixo de t e m<n.
Aqui: s_i é o i-ésimo símbolo de s; m e n são os comprimentos de s e t.

Passo 4

Exemplos concretos para ficar mais firme na ideia.
  • Comparando “abc” e “abd”: as primeiras duas letras são iguais, na terceira temos ‘c’ < ‘d’, portanto “abc” < “abd”.
  • Comparando “ab” e “abc”: todas as letras de “ab” coincidem com as iniciais de “abc”, e “ab” é mais curta, logo “ab” < “abc”.
  • Comparando “Apple” e “apple” em um ordenamento baseado em ASCII: ‘A’ tem código 65 e ‘a’ tem código 97, então “Apple” < “apple”.

Passo 5

Agora: como isso se traduz em C (parte b) — princípios gerais.
Em C, strings são arrays de bytes terminados por '\0'. A comparação lexicográfica padrão (como a feita por strcmp) ocorre olhando byte a byte, do início ao fim, até:
  • encontrar dois bytes diferentes, caso em que a ordem é decidida pelo valor numérico desses bytes na tabela de caracteres da execução (normalmente ASCII ou outra tabela de execução), ou
  • encontrar o caractere nulo '\0' em ambas as strings (significando igualdade), ou
  • encontrar '\0' numa das strings enquanto a outra continua (a mais curta — cujo '\0' apareceu primeiro — é considerada menor).
Importante notar alguns detalhes práticos:
  • O conjunto de códigos (ASCII, EBCDIC, etc.) é implementacional; na prática é quase sempre ASCII/UTF-8 na maioria dos sistemas modernos, mas o C usa a “tabela de execução” do ambiente.
  • Funções como strcmp tratam os bytes; não fazem comparação sensível a regras de locale (acentos, regras linguísticas) — para isso existem funções de collation específicas (ex.: em bibliotecas externas).
  • Problemas com char assinado: muitos implementadores convertem os bytes para unsigned char antes de compará-los para evitar efeitos de sinal em valores maiores que 127.

Passo 6

Exemplo numérico em C (detalhando os passos):
Comparar s = "A" e t = "a":
  1. Ler primeiro byte de s: caractere 'A' com código numérico geralmente 65.
  2. Ler primeiro byte de t: caractere 'a' com código numérico geralmente 97.
  3. Como 65<97, s é menor que t. A função strcmp(s,t) retornaria um valor negativo (por exemplo, -1) indicando s < t.

Passo 7

Esboço de algoritmo (passo a passo) — versão didática e fácil de entender (parte c).
Objetivo do algoritmo: dizer se duas strings s e t são “menor”, “iguais” ou “maior” lexicograficamente. Vou usar terminologia próxima de C, mas simples.
Algoritmo em palavras:
  1. Comece no índice i=0.
  2. Enquanto nem s[i] nem t[i] for '\0':
    a. Se s[i] \neq t[i], então comparar os códigos numéricos de s[i] e t[i]: se s[i] < t[i] então s < t; senão s > t. Interrompa.
    b. Se s[i] = t[i], incremente i e continue.
  3. Se saiu do laço porque ambos s[i] e t[i] são '\0', então s = t.
  4. Se saiu do laço porque um deles é '\0' e o outro não, a string cujo '\0' apareceu primeiro (ou seja, a mais curta) é a menor.

Passo 8

Esboço em pseudocódigo bem claro (estilo amigo que explica cada linha)
pseudocódigo:
  • i ← 0
  • enquanto true faça
    • c1 ← byte em s[i]
    • c2 ← byte em t[i]
    • se c1 = c2 então
      • se c1 = ‘\0’ então retorne “iguais” // ambos terminaram ao mesmo tempo
      • i ← i + 1 // continuar comparando próximo caractere
    • senão // c1 ≠ c2
      • se (unsigned char) c1 < (unsigned char) c2 então retorne “s < t”
      • senão retorne “s > t”
  • fim enquanto
Explicação das escolhas no pseudocódigo:
  • Casting para (unsigned char) evita problemas quando char é tratado como valor negativo pelo compilador. Assim a comparação baseia-se nos valores de 0 a 255 dos bytes.
  • A complexidade é linear: O(\min(m,n)) onde m e n são comprimentos das strings, porque paramos na primeira diferença ou no fim.

Passo 9

Traço um exemplo passo a passo com o algoritmo (para fixar):
Comparar s = "cas" e t = "casa":
  • i=0: s[0]='c', t[0]='c' iguais → i=1.
  • i=1: s[1]='a', t[1]='a' iguais → i=2.
  • i=2: s[2]='s', t[2]='s' iguais → i=3.
  • i=3: s[3]='\0', t[3]='a' → ‘\0’ < ‘a’, logo s < t. Isso confirma a regra do prefixo.

Passo 10

Notas práticas e armadilhas para a prova (dicas rápidas e úteis):
  • Lembre-se: strcmp e afins são byte-wise e não seguem regras de idioma. Para ordenação “linguística”, use bibliotecas de collation.
  • Sempre considere a representação dos caracteres (ASCII/UTF-8): em UTF-8, caracteres acentuados ocupam vários bytes — comparação byte a byte não corresponde necessariamente à ordenação por carácter ou por aparência.
  • Em código C real, a implementação clássica de strcmp costuma retornar um inteiro negativo, zero ou positivo; muitas implementações usam a expressão (unsigned char)c1 - (unsigned char)c2 ou simplesmente if (c1 < c2) return -1; if (c1 > c2) return 1;.

Resposta

(a) Ordem lexicográfica é a ordem de dicionário: comparar duas sequências símbolo a símbolo; a primeira posição em que differem decide a ordem, e se uma é prefixo da outra a mais curta vem primeiro.
(b) Em C a ordem é determinada comparando os bytes das strings um a um usando os valores numéricos dos caracteres na tabela de execução (normalmente ASCII); a comparação pára na primeira diferença ou no '\0'; a comparação é byte-wise (não sensível a locale) e normalmente os bytes são tratados como unsigned char para evitar problemas de sinal.
(c) Algoritmo (esboço): percorrer índices i comparando s[i] e t[i]; se s[i]\neq t[i] então decidir pela ordem conforme os valores numéricos (por exemplo, retornar -1 se s[i]<t[i], +1 se s[i]>t[i]); se ambos chegarem a '\0' simultaneamente retornar “iguais”; se um chegar a '\0' e o outro não, a string cujo '\0' aparece primeiro é menor.

Exercícios relacionados