Algoritmos sobre secuencias ya ordenadas

Merge - Apareo de secuencias ordenadas

• Problema:

  Dadas dos secuencias ordenadas, unir ambas secuencias en una única secuencia ordenada.

• Especificación:

  proc merge(in a, b seq(Z), out result : seq(Z)) {
  	Pre{ordenado(a) && ordenado(b)}
  	Post{ordenado(result) && mismos(result, a ++ b)}
  }
  

• Invariante:

  I = 
  	0 <= i <= |a| && 0 <= j <=  |b| &L
  	 (mismos(a[0..i) ++ b[0..j), c[0..k)) && ordenado(c[0..k)) &&
  	 j < |b| -->L (p. t. k : Z) (0 <= k < i -->L a[k] <= b[j]) &&
  	 i < |a| -->L (p. t. k : Z) (0 <= k < j -->L b[k] <= a[i])
  

• Implementación en SmallLang:

  i := 0; j := 0; k := 0;
  
  while (i < |a| && j < |b|) {
  	if (a[i] < b[j]) {
  		c[k] := a[i];
  		i++;
  		k++;
  	} else {
  		c[k] := b[j];
  		j++;
  		k++;
  	}
  }
  
  while (j < |b|) {
  	c[k] := b[j];
  	j++;
  	k++;
  }
  
  while (i < |a|) {
  	c[k] := a{i};
  	i++;
  	k++;
  }
  

• Función variante:

  $$ ⁍ $$

• Complejidad: $O(n)$

The Welfare Crook

• Problema:

  Dadas tres secuencias ordenadas sabemos que hay al menos un elemento en conmún entre ellas. Encontrar los índices donde está al menos uno de estos elementos repetidos.

• Especificación:

  proc crook(in a, b, c : seq(Z), out i, j, k : Z) {
  	Pre{
  			ordenado(a) && ordenado(b) && ordenado(c) &&
  			(E iv, jv, kv : Z)
  				((0 <= iv < |a| && 0 <= jv < |b| && 0 <= kv < |c|) &L
  				a[iv] = b[jv] = c[kv])
  		}
  	Post{
  				(0 <= i < |a| && 0 <= j < |b| && 0 <= k < |c|) &L
  				a[i] = b[j] = c[k]
  		}
  }
  

• Invariante:

  I = (E iv, jv, kv : Z)
  				(
  				(0 <= iv < |a| && 0 <= jv < |b| && 0 <= kv < |c|) &L
  				a[iv] = b[iv] = c[iv] &&
  				**0 <= i <= iv && 0 <= j <= jv && 0 <= k <= kv**
  			)
  

• Implementación en SmallLang:

  i := 0; j := 0; k := 0;
  
  while (a[i] != b[j] || b[j] != c[k]) {
  	if (a[i] < b[j]) {
  		i++;
  	} else (b[j] < c[k]) {
  		j++;
  	} else {
  		k++;
  	}
  }