Arreglos de caracteres (cadenas).

   Todo lo que hasta este momento se ha comentado para los arreglos respecto a su declaración, inicialización, recorrido, y uso con funciones, es aplicable a arreglos de cualquiera de los tipos de datos de C incluyendo char; sin embargo, este tipo de arreglos poseen características particulares, empezando porque es común denominar a un arreglo de caracteres (char) como cadena, de ahí que su tratamiento y discusión se hayan separado en una entrada especial.

   Si se han revisado las entradas anteriores, en este momento el lector cuenta con algo de experiencia en la declaración, inicialización, recorrido, y uso de arreglos con funciones, por lo que en el Ejemplo 6.6 se presentan estos conceptos en el contexto de cadenas, es decir: arreglos de caracteres.

   Las líneas 12, 13 y 14 muestran la declaración de tres cadenas: cadena1, cadena2 y cadena3. Note que las dos primeras no tienen un tamaño explícito y que han sido inicializadas de forma distinta.

   La cadena1 se ha inicializado con una frase contenida entre comillas dobles. En el lenguaje de programación C, cualquier sucesión de elementos contenida entre comillas dobles es una cadena, y dicha cadena está compuesta por todos los caracteres entre comillas (incluyendo los espacios en blanco), más un carácter no visible, pero que delimita el fin de la cadena. Este carácter recibe el nombre de fin de cadena y es '\0', que aunque es un carácter compuesto por dos símbolos (\ y 0), se considera como uno solo y se denota entre comillas simples: '\0'. Por lo tanto la cadena1 tiene un tamaño implícito o longitud no de 18 caracteres como podría pensarse en un principio, sino de 19.

   Por otro lado, la cadena2 (línea 13) tiene una inicialización más parecida a lo que se vio en su momento para arreglos de tipo int y float. Note que cada unos de los elementos de la cadena, incluyendo el fin de cadena, se encuentran entre comillas simples. Para este tipo de inicialización el terminador de cadena '\0' debe proporcionarse de manera explícita, ya que de otra forma, la cadena estaría mal formada, es decir, sin terminar, y esto podría llevar a efectos o resultados desde inesperados (impresión de caracteres extraños más allá de lo que en principio conforma la cadena) hasta catastróficos (intentos de acceso a memoria no reservada y la consecuente anulación del programa). Esta cadena tiene una longitud implícita de seis caracteres.

   La cadena3 no ha sido inicializada y se utilizará para leer una cadena desde la entrada estándar a través de la función gets (la cual recibe una cadena almacena en ella lo que se procesa de la entrada estándar, hasta que se introduzca un ENTER, (\n) (línea 18).

   El ciclo for de la línea 21 muestra el recorrido clásico de una cadena. Observe que la expresión condicional depende del carácter de fin de cadena ('\0'), y que el cuerpo del ciclo (línea 22) imprime la cadena cadena1 carácter por carácter con un espacio entre ellos.

   La línea 23 muestra el uso de la función putchar para imprimir el carácter de avance de línea y un retorno de carro. Dicha función es equivalente a la sentencia:

printf("\n");

   Note que la secuencia de escape '\n' ha sido escrita entre comillas simples en la línea 23 debido a que la función putchar escribe en la salida estándar el carácter que recibe como argumento.

   El Ejemplo 6.6 también dos funciones que se describen a continuación:

• longitud (línea 38): recibe una cadena, la cual se identifica como c dentro de la función, y realiza un recorrido sobre c para llegar al final de la misma, de tal forma que la variable de control i contiene la longitud de c cuando la expresión condicional del for se evalúa como 0; el cuerpo del ciclo está vacío porque no hay nada más que hacer y esto se enfatiza con el ";" de la línea 42. Finalmente la función regresa la longitud de la cadena: i (línea 43).
• imprimeAlReves (línea 30):  recibe una cadena, la cual se identifica como c dentro de la función y realiza un recorrido inverso sobre c, es decir, del último carácter de la cadena (longitud - 1) al primero (0). Dentro del recorrido, la cadena se imprime en la salida estándar carácter por carácter.

   Note que la cadena original (como argumento la cadena original es cadena2 (línea 25), como parámetro es c (línea 30)) no se invierte, sino que únicamente se imprime al revés, por lo tanto la cadena original permanece inalterada; asegúrese de comprender esto antes de continuar.

   Una posible salida del Ejemplo 6.6 se  muestra en la siguiente figura:

Una posible salida del Ejemplo 6.6.

 

    En la entrada correspondiente a los apuntadores se retomará el tema de cadenas.

Búsqueda lineal y búsqueda binaria.

Búsqueda lineal.

   La búsqueda lineal es muy sencilla y natural, dado que es la forma en que los seres humanos realizamos búsquedas.

   La idea es bastante simple: se va recorriendo uno a uno la secuencia de elementos sobre los que se desea realizar la búsqueda (conjunto de datos), y se va comparando cada uno de ellos con el elemento a buscar (clave o llave); si existe coincidencia, entonces la búsqueda ha tenido éxito y se reporta el índice (posición) del elemento dentro del conjunto de datos.

   También puede ocurrir que se haya recorrido todo el conjunto de datos y no se haya encontrado coincidencia con la clave, en cuyo caso se reporta dicha situación con una posición (índice) no válida (-1) respecto al conjunto de datos.

   La función busquedaLineal de las líneas 8-15 del Ejemplo 6.5, recibe un arreglo de enteros constantes (el modificador const le indica al compilador que el arreglo es de elementos constantes, y previene al programador de alguna modificación accidental o incidental sobre los elementos del arreglo afectado por el modificador, es decir, vuelve al arreglo afectado de sólo lectura: no es posible modificar sus elementos dentro de la función) a (conjunto de datos), un entero x (clave o llave), y un número n que representa la cantidad de datos del conjunto sobre el que se realizará la búsqueda (podría ser todo el conjunto de datos o sólo una parte de él).

   El ciclo for de la línea 11 realiza el recorrido sobre el conjunto de datos, mientras que el if de la línea 12 verifica la coincidencia con el elemento clave; en caso de existir, se reporta en la línea 13, pero si el elemento clave no existe, se reporta dicha situación en la línea 14.

Búsqueda binaria.

   La búsqueda binaria se fundamenta en un pre requisito sumamente importante: que el conjunto de datos esté ordenado.

   La importancia de tal pre requisito es tal que, si no se cumple, no se garantiza el buen funcionamiento de la búsqueda binaria.

   La búsqueda binaria capitaliza el hecho de que los datos estén ordenados para ir eliminando en cada iteración a la mitad de los datos, lo cual la hace muy eficiente; sin embargo, el costo a pagar es el previo ordenamiento de los datos.

   Para entender mejor el funcionamiento de la búsqueda binaria utilizaré una analogía con la forma de realizar la búsqueda de una persona en un directorio telefónico (si desconoce por completo lo que estoy diciendo, pregúntele a una persona mayor que no sea de la generación de smartphones lo que era un directorio telefónico antigüo).

   Suponga que se desea buscar en un directorio telefónico el siguiente nombre: Ricardo Ruiz Rodríguez. En México los nombres aparecen registrados en el directorio en base al primer apellido, segundo apellido y nombre(s) de las personas registradas. Supongamos también que se decide abrir el directorio por la mitad (aproximadamente), y que la lista de apellidos que vemos empieza con Murrieta.

   ¿Hacia qué parte del directorio deberíamos dirigir la búsqueda? Debería ser obvio que hacia la segunda mitad, ya que Ruiz se encuentra alfabéticamente después que Murrieta. Pues bien, ésta es en esencia la idea de la búsqueda binaria.

   El Ejemplo 6.5 muestra en las líneas 17-31 la función que implementa el mecanismo de búsqueda binaria.

   La función recibe (línea 17) un arreglo de elementos constantes a (conjunto de búsqueda), el elemento a buscar x (clave o llave), y dos números que representan las posiciones de los límites inferior (lim_inf)  y superior (lim_sup) del conjunto de búsqueda respectivamente. Estos límites en general coinciden con el índice inferior y superior del arreglo pero no necesariamente tiene que ser así, ya que el conjunto de búsqueda podría ser un subconjunto de todos los elementos.

   La expresión condicional de la estructura de repetición while de la línea 20, controla la continuidad o no de la búsqueda del elemento x sobre el arreglo a. En cuanto ya no se cumpla dicha expresión, se sabrá que el elemento clave no existe en el conjunto de búsqueda (¿por qué?), y dicha situación se reporta en la línea 30.

   La línea 20 es la fórmula del punto medio y calcula el elemento central del conjunto de búsqueda. En analogía al ejemplo del directorio telefónico, esta sería la simulación de abrirlo aproximadamente a la mitad.

   La estructura if/else anidada de las líneas 22-27 determina lo siguiente:

• Si la clave se encontró (línea 22), se regresa su posición dentro del conjunto (línea 23).
• Si no se encontró y hay que buscarla en la parte izquierda del conjunto (línea 24), se ajusta el límite superior (línea 25) para re definir un nuevo subconjunto de búsqueda.
• Si la clave no es igual ni menor respecto al elemento actual (a[medio]), por tricotomía de números, no le queda otra (línea 26) más que estar (si existe) en la parte derecha del conjunto de búsqueda, por lo que se ajusta el límite inferior (línea 27) para re definir el nuevo subconjunto de búsqueda.

   Finalmente, si no se ha encontrado la clave y los límites del subconjunto de búsqueda son válidos, se repite nuevamente todo el proceso descrito pero sobre un conjunto de búsqueda con menos datos, de hecho la mitad (aproximadamente) de los datos en cada iteración.

   Probablemente el lector haya tenido una sensación parecida a un deja vu y haya venido a su mente el concepto de recursividad (si revisó las entradas correspondientes a recursividad). La búsqueda binaria puede ser abordada utilizando un enfoque recursivo y se deja como ejercicio explorar dicha situación.

Ordenamiento por burbuja.

   El ordenamiento de elementos es uno de los problemas clásicos de la computación. En esta entrada se presentará un algoritmo clave y sencillo, aunque no eficiente, para el ordenamiento de elementos: el ordenamiento por burbuja.

   Considere la siguiente secuencia de elementos:

15, -4, 0, -9, 7, 10

   Con toda seguridad, si consigue una hoja de papel y un lápiz, incluso quizá mentalmente, podrá ordenarlos ascendentemente obteniendo como resultado:

-9, -4, 0, 7, 10, 15

   Ahora bien, ¿cuál fue el procedimiento que siguió para ordenarlos?, ¿lo podría especificar y detallar para convertirlo en un algoritmo?

   No hay una única forma de ordenar una secuencia de elementos, aunque quizá la más común sea la búsqueda del elemento menor de la lista, colocarlo es su lugar, y buscar el siguiente elemento menor de la lista, colocarlo en su lugar, y continuar así sucesivamente hasta terminar con toda la secuencia de elementos a ordenar.

   El algoritmo de la burbuja se basa en ir comparando elementos contigüos, es decir, tomar el elemento i-ésimo y compararlo con el elemento i-ésimo + 1, si ese par de elementos no está ordenado, entonces se intercambian, si lo están, se dejan tal y como se encontraron.

   Para la secuencia anterior, el algoritmo de la burbuja generaría los siguientes intercambios para el primer recorrido:

15, -4, 0, -9, 7, 10

-4, 15, 0, -9, 7, 10

-4, 0, 15, -9, 7, 10

-4, 0, -9, 15, 7, 10

-4, 0, -9, 7, 15, 10

-4, 0, -9, 7, 10, 15

   Observe que aunque los elementos aún no están ordenados todavía, el mayor de ellos (15) fue intercambiándose y ascendiendo a su posición final; de hecho ésta es la razón por la cual el algoritmo recibe el nombre de burbuja, en analogía al efecto ascendente de las burbujas de aire en el agua.

   La secuencia anterior de intercambios, constituye de hecho el primer recorrido para la lista de elementos, y en principio, se necesitan n - 1 recorridos para una lista de n elementos y n - 1 comparaciones dentro de cada recorrido para saber si realiza o no el intercambio.

   Siguiendo la idea planteada hasta ahora termine de hacer los recorridos restantes, es decir: los cuatro recorridos que faltan con sus cinco iteraciones de comparación en cada uno.

   El Ejemplo 6.4 muestra un archivo de biblioteca personalizada (.h) que contiene dos versiones para el ordenamiento por burbuja. La versión que nos compete por el momento es la función definida en las líneas 23-34, la cual implementa la versión tradicional del ordenamiento por burbuja, también conocido como burbuja clásico o ingenuo.

   La estructura de repetición for de la línea 26 controla el número de veces que se recorre el arreglo, que como ya se mencionó es de n - 1 veces, donde n es el número de elementos a ordenar. Ahora bien, para una n muy grande se tiene:

   Por lo que se puede decir que un arreglo de n elementos se recorre n veces.

   Por otro lado, el ciclo for de la línea 27 realiza en general n - 1 iteraciones para comparar parejas de números candidatas a intercambio para los n elementos del arreglo, pero por la misma razón que antes establecida por el límite, es posible decir que se repite n veces. Esto quiere decir que por cada recorrido se realizan n comparaciones.

   En base a lo anterior, el ordenamiento por burbuja tiene el siguiente comportamiento general:

donde n es el número de elementos a ordenar.

   La notación de la expresión anterior se lee como ''o grande de n cuadrada", y su explicación queda fuera de los alcances de este blog; por ahora, basta con saber que el ordenamiento por burbuja tiene un comportamiento cuadrático.

Burbuja mejorado.

   Si terminó de realizar las iteraciones propuestas en párrafos anteriores para ordenar la secuencia de números que se presentó, probablemente se haya dado cuenta de que la secuencia está ordenada después de la primera iteración de comparación del tercer recorrido.

   Se deriva entonces una pregunta más que pertitente: ¿Tiene sentido realizar los recorridos e iteraciones de comparación restantes? Con toda seguridad su respuesta será negativa.

   El ordenamiento por burbuja clásico no hace ningún tipo de verificación en éste sentido, por lo que realizaría siempre todos los recorridos e iteraciones de comparación basándose única y exclusivamente en el número de elementos a ordenar aún cuando los datos estuvieran ordenados desde el principio, de ahí que al ordenamiento por burbuja clásico también se le denomine ingenuo.

   Para subsanar esta deficiencia, se pueden hacer esencialmente dos cosas basadas en las siguientes consideraciones:

1. Después de cada recorrido, el elemento mayor de serie de elementos se encontrará ya en su posición final; en el segundo recorrido el segundo elemento mayor y así sucesivamente, ¿tiene sentido seguir comparando estos elementos que sabemos ya ordenados? La respuesta es no, por lo que si después de cada recorrido reducimos también el número de iteraciones de comparación, se mejorará la eficiencia. Ésta es precisamente la mejora que se implementa en el ciclo for de la línea 13 del Ejemplo 6.4, en donde la expresión condicional se ha modificado para que dependa también del número de veces que se ha realizado el recorrido.
2. Ahora bien, si la serie de elementos se encuentra ya ordenada en alguna parte del proceso de ordenamiento antes de las n x n iteraciones, tampoco tendría sentido continuar. Para dicho caso se ha utilizado una bandera (línea 9), la cual asumirá que después de cada recorrido la serie de elementos estará probablemente ordenada, por lo que la bandera se apaga  (línea 12) para que la expresión condicional del ciclo for de la línea 11 sea falsa y los recorridos sobre la serie de elementos terminen; sin embargo, si la expresión condicional del if de la línea 14 se cumple para al menos una de las iteraciones de comparación, entonces la serie de elementos no está ordenada todavía y se enciende nuevamente la bandera (línea 18) para procesar al menos un nuevo recorrido.

   En el argot computacional una bandera es un indicador (centinela), y es una variable que sirve para indicar una determinada situación.

   Las banderas más comunes son las banderas binarias o booleanas, las cuales toman únicamente dos valores: 1 (verdadero) o 0 (falso).

   El lenguaje de programación C no tiene tipos de datos booleanos, por lo que tienen que ser simulados o implementados con variables de tipo entero. Cuando a una bandera booleana se le asigna verdadero, se dice que se enciende la bandera, y cuando se le asigna falso, se dice que se apaga la bandera en analogía a un interruptor (switch) de encendido/apagado.