República Bolivariana de Venezuela
Ministerio del Poder Popular para la Defensa
Universidad Experimental Politécnica de la
Fuerza Armada Nacional Bolivariana
Núcleo La Guaira
Profesor. Alumno.
Cumare, Nolis. Sánchez, Joerfre
Archivo Objeto y Archivo Ejecutable
Archivo Objeto
En primer lugar, el programa C es un conjunto de instrucciones escritas en lenguaje de
programación C para realizar una tarea específica. Este programa se llama el código
fuente. El programador puede leer y entender el código fuente, pero la CPU no lo
entiende. Por lo tanto, es necesario convertir el código fuente en un formato
comprensible para la máquina. Un código de objeto se genera después de compilar el
código fuente
El archivo de objeto es otro nombre para el código de objeto. El archivo objeto tiene la
extensión .obj en el entorno de Windows. Además, el archivo objeto tiene el. o
extensión de archivo en entorno Linux. Sin embargo, la CPU no puede ejecutar
directamente el archivo objeto.
Archivo Ejecutable ORDEN
Después de escribir el programa C, si hay errores
de sintaxis, el
editarlos. Sin embargo, si
AMIEN programador debe
no hay errores de sintaxis,
TO Y
el compilador convierte el código fuente en un
archivo objeto. Luego el enlazador realiza el
proceso de vinculación. Toma uno o más archivos
de objetos generados por
combina en un solo BÚSQU el compilador y los
archivo ejecutable.
Además, enlaza los otros archivos de programa y las
funciones que el programa
programa tiene la función
EDA requiere. Por ejemplo, si el
"exp ()", el enlazador
vincula el programa con la biblioteca matemática del
sistema.
El programador no entiende las instrucciones
en el archivo ejecutable, pero la CPU puede leer y entender esas instrucciones. Por lo
tanto, la CPU ejecuta directamente el archivo ejecutable para realizar las tareas
definidas en el programa.
Métodos de Ordenamiento
Ordenamiento Burbuja
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de
ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada
con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es
necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios,
lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la
forma con la que suben por la lista los elementos durante los intercambios, como si
fueran pequeñas "burbujas". También es conocido como el método del intercambio
directo. Dado que solo usa comparaciones para operar elementos, se lo considera un
algoritmo de comparación, siendo uno de los más sencillos de implementar.
Ejemplo en C++
Este es un ejemplo de un programa que captura números y los ordena de menor a
mayor en lenguaje C++, compilado con g++ 5.4.0:
Ordenamiento por selección
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de
ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
Descripción del algoritmo
Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lista
Intercambiarlo con el primero
Buscar el siguiente mínimo en el resto de la lista
Intercambiarlo con el segundo
Y en general:
Buscar el mínimo elemento entre una posición i y el final de la lista
Intercambiar el mínimo con el elemento de la posición i
De esta manera se puede escribir el siguiente pseudocódigo para ordenar una
lista de n elementos indexados desde el 0:
Ejemplo del algoritmo en C++
Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que
ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que
ordenar un vector de estructuras más complejas, la operación intercambiar() sería más
costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar()
que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se
sustituyera por intercambiar(lista[i], lista[j]) tendríamos una versión del algoritmo de la
burbuja (naturalmente eliminando el orden intercambiar del final).
Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción
directa es que no mejora su rendimiento cuando los datos ya están ordenados o
parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de
burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y
finalizar, en la ordenación por selección se realizarían el mismo número de pasadas
independientemente de si los datos están ordenados o no.
Ordenamiento por inserción
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de
ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de
cartas numeradas en forma arbitraria. Requiere O(n2) operaciones para ordenar una
lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado.
Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento
k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se
encuentra un elemento menor (todos los elementos mayores han sido desplazados
una posición a la derecha) o cuando ya no se encuentran elementos (todos los
elementos fueron desplazados y este es el más pequeño). En este punto se inserta el
elemento k+1 debiendo desplazarse los demás elementos.
Ordenamiento por intercambio
El algoritmo del intercambio aunque es el más sencillo de implementar es uno de los
más pobres en rendimiento, se basa en la idea de buscar cada vez el menor elemento
del conjunto y ubicarlo al principio del mismo, repitiendo este proceso cada vez con el
conjunto sin su primer elemento (el menor del conjunto anterior), hasta llegar a un
conjunto de un solo elemento que por definición ya está ordenado.
En cada paso del algoritmo se compara el primer elemento del conjunto x[i], con los
demás elementos del mismo x[j] (j=i+1 .. n) y cuando x[i] es mayor que x[j], se
intercambian sus valores. Cuando se termina de recorrer el arreglo el proceso nos
garantiza que en x[i] está el menor elemento del conjunto.
Teniendo en cuenta que el algoritmo de ordenamiento por intercambio se realiza
siempre de la misma manera independiente de los datos que estén almacenados, no
existe un mejor, peor o caso promedio y su complejidad siempre será O(n 2).
Ordenamiento rápido
El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenacion creado por
el científico británico en computación C. A. R. Hoare.
Descripción del algoritmo
El algoritmo trabaja de la siguiente forma:
Elegir un elemento del conjunto de elementos a ordenar, al que llamaremos
pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que
a un lado queden todos los menores que él, y al otro los mayores. Los
elementos iguales al pivote pueden ser colocados tanto a su derecha como a su
izquierda, dependiendo de la implementación deseada. En este momento, el
pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la
izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas
contengan más de un elemento. Una vez terminado este proceso todos los
elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que
termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos
sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo
es \Omega(n·log n).
En el peor caso, el pivote termina en un extremo de la lista. El orden de
complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la
implementación del algoritmo, aunque habitualmente ocurre en listas que se
encuentran ordenadas, o casi ordenadas. Pero principalmente depende del
pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el
primer elemento del array, y el array que le pasamos está ordenado, siempre
va a generar a su izquierda un array vacío, lo que es ineficiente.
En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se
centren en la elección del pivote.
Ordenamiento por mezcla
El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de
ordenamiento externo estable basado en la técnica divide y vencerás. Es de
complejidad O(n log n).
Descripción
Fue desarrollado en 1945 por John Von Neumann.
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
1. Si la longitud de la lista es 0 o 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del
tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de
ejecución:
1. Una lista pequeña necesitará menos pasos para ordenarse que una lista
grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos
listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo,
sólo será necesario entrelazar cada lista una vez que están ordenadas.
A continuación se describe el algoritmo en pseudocódigo (se advierte de que no se
incluyen casos especiales para vectores vacíos, etc.; una implementación en un
lenguaje de programación real debería tener en cuenta estos detalles):
Hashing
Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersión o tabla
fragmentada es una estructura de datos que asocia llaves o claves con valores. La
operación principal que soporta de manera eficiente es la búsqueda: permite el acceso
a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave
generada (usando el nombre o número de cuenta, por ejemplo). Funciona
transformando la clave con una función hash en un hash, un número que identifica la
posición (casilla o cubeta) donde la tabla hash localiza el valor deseado.
Las tablas hash se suelen implementar sobre vectores de una dimensión, aunque se
pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como
en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda
promedio O(1), sin importar el número de elementos en la tabla. Sin embargo, en
casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en
función del número de elementos.
Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles
cuando se almacenan grandes cantidades de información.
Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el
acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles
binarios auto-balanceables tienen un tiempo promedio de búsqueda mayor (tiempo de
búsqueda O(log n)), pero la información está ordenada en todo momento.
Ejemplo:
Un ejemplo práctico para ilustrar que es una tabla hash es el siguiente: Se necesita
organizar los periódicos que llegan diariamente de tal forma que se puedan ubicar de
forma rápida, entonces se hace lo siguiente: se hace una gran caja para guardar todos
los periódicos (una tabla), y se divide en 31 contenedores (ahora es una hash table o
tabla fragmentada), y la clave para guardar los periódicos es el día de publicación
(índice). Cuando se requiere buscar un periódico se busca por el día que fue publicado
y así se sabe en que zócalo (bucket) está. Varios periódicos quedarán guardados en el
mismo zócalo (es decir, colisionan al ser almacenados), lo que implica buscar en la sub-
lista que se guarda en cada zócalo. De esta forma se reduce el tamaño de las
búsquedas de O(n) a O(log(n)).
