Scribd
Cargar
19 vistas6 páginas

Practica1 1

El documento presenta una práctica sobre estructuras de datos, enfocándose en un algoritmo de ordenamiento por conteo con complejidad O(n). Se describe un conjunto de datos aleatorios y se propone un algoritmo que permite ordenar estos datos y realizar búsquedas en O(1). Incluye código de implementación y resultados esperados.

Cargado por

francisco orozco
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
19 vistas6 páginas

Practica1 1

El documento presenta una práctica sobre estructuras de datos, enfocándose en un algoritmo de ordenamiento por conteo con complejidad O(n). Se describe un conjunto de datos aleatorios y se propone un algoritmo que permite ordenar estos datos y realizar búsquedas en O(1). Incluye código de implementación y resultados esperados.

Cargado por

francisco orozco
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Unidad Profesional Interdisciplinaria

en Ingeniería y Tecnologías
Avanzadas

Alumno
Orozco Rojas Francisco

Unidad de Aprendizaje
Estructura de Datos

Profesor
M. en C. Niels Henrik Navarrete Manzanilla

Práctica 1.1
ÍNDICE
CONTENIDO
INTRODUCCIÓN 3
DESARROLLO 3
DESCRIPCIÓN 3
ANÁLISIS 3
REQUERIMIENTOS FUNCIONALES 3
REQUERIMIENTOS NO FUNCIONALES 3
DIAGRAMAS 3
CÓDIGO 3
RESULTADOS 3
CONCLUSIONES 3
REFERENCIAS BIBLIOGRÁFICAS 4
INTRODUCCIÓN

Las estructuras de datos, junto con el estudio de algoritmo, hacen


parte de los fundamentos de la programación y se escucha mucho
sobre la importancia de estudiar este tema. En este documento
vamos a hablar acerca de un problema sobre algoritmo de
ordenamiento.

DESARROLLO

Descripción
Se tiene un conjunto de n datos generados de manera aleatoria, del cual se sabe el número
más grande y el más pequeño. Proponga un algoritmo con una complejidad temporal O(n) -
por conteo, que permita ordenar dicho arreglo, de tal forma que sea posible realizar una
búsqueda de un valor en el arreglo ordenado en O(1).
Código // Crear el arreglo auxiliar para almacenar el
conjunto de datos ordenado
int sorted_arr[n];
#include <stdio.h>
#include <stdlib.h> // Colocar cada valor en su posición
int i; correspondiente en el arreglo auxiliar
for ( i = n - 1; i >= 0; i--) {
void counting_sort(int arr[], int n) { sorted_arr[count[arr[i] - min_num] - 1] =
// Obtener el número más grande y el más arr[i];
pequeño del conjunto de datos count[arr[i] - min_num]--;
int max_num = arr[0]; }
int min_num = arr[0]; // El arreglo
for ( i = 1; i < n; i++) { printf("Arreglo original: ");
if (arr[i] > max_num) { for(i= 0; i< n; i++){
max_num = arr[i]; printf("%d ", arr[i]);
} }
if (arr[i] < min_num) { printf("\n");
min_num = arr[i];
} // Mostrar el arreglo ordenado
} printf("Arreglo ordenado: ");
// Crear el arreglo de conteo y inicializarlo en for ( i = 0; i < n; i++) {
cero printf("%d ", sorted_arr[i]);
int count[max_num - min_num + 1]; }
for ( i = 0; i < max_num - min_num + 1; i++) { printf("\n");
count[i] = 0; }
}
int main() {
// Contar la frecuencia de cada valor en el // Ejemplo de uso del algoritmo de Counting
conjunto de datos Sort
for ( i = 0; i < n; i++) { int arr[] = {9, 6, 3, 7, 1, 8, 5, 2, 4};
count[arr[i] - min_num]++;
} int n = sizeof(arr) / sizeof(arr[0]);
// Calcular la posición final de cada valor en el counting_sort(arr, n);
arreglo ordenado
for ( i = 1; i < max_num - min_num + 1; i++) { return 0;
count[i] += count[i - 1]; }
}

Resultado
CONCLUSIONES
REFERENCIAS BIBLIOGRÁFICAS

También podría gustarte