Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » C/Visual C » TORNEO

C/Visual C - TORNEO

Volver
Nuevo Tema
<<>>
 
Vista:

TORNEO

Publicado por hector (1 intervención) el 23/10/2002 07:41:35
URGENTE. Necesito el programa en C de ordenamiento por seleccion de arboles(TOURNAMENT).
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Implementación de ordenamiento por selección usando árboles de torneo (tournament sort)

Publicado por Alejandro (980 intervenciones) el 27/03/2025 19:58:12
Héctor, aquí tienes un programa en C que implementa el algoritmo de ordenamiento por selección utilizando árboles de torneo (tournament sort). Este algoritmo utiliza una estructura de árbol para seleccionar el elemento mínimo de un conjunto de datos y es eficiente para ordenar grandes volúmenes de datos.

Código en C para ordenamiento por selección usando árboles de torneo



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int value;
    int index;
} Node;
 
void buildTournamentTree(Node *tournamentTree, int *array, int n) {
    for (int i = 0; i < n; i++) {
        tournamentTree[i].value = array[i];
        tournamentTree[i].index = i;
    }
 
    for (int i = n; i < 2 * n - 1; i++) {
        tournamentTree[i].value = INT_MAX; // Inicializar con un valor grande
        tournamentTree[i].index = -1;
    }
 
    for (int i = n - 1; i > 0; i--) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (tournamentTree[left].value < tournamentTree[right].value) {
            tournamentTree[i] = tournamentTree[left];
        } else {
            tournamentTree[i] = tournamentTree[right];
        }
    }
}
 
int extractMin(Node *tournamentTree, int n) {
    Node minNode = tournamentTree[0];
    tournamentTree[0].value = INT_MAX; // Marcar como eliminado
 
    for (int i = 0; i < n; i++) {
        if (tournamentTree[i].value != INT_MAX) {
            int parent = (i - 1) / 2;
            if (parent >= 0) {
                if (tournamentTree[i].value < tournamentTree[parent].value) {
                    tournamentTree[parent] = tournamentTree[i];
                }
            }
        }
    }
 
    return minNode.value;
}
 
void tournamentSort(int *array, int n) {
    Node *tournamentTree = (Node *)malloc(sizeof(Node) * (2 * n - 1));
    buildTournamentTree(tournamentTree, array, n);
 
    for (int i = 0; i < n; i++) {
        array[i] = extractMin(tournamentTree, n);
    }
 
    free(tournamentTree);
}
 
int main() {
    int array[] = {5, 3, 8, 6, 2, 7, 4, 1};
    int n = sizeof(array) / sizeof(array[0]);
 
    tournamentSort(array, n);
 
    printf("Array ordenado: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
 
    return 0;
}

Explicación del código


1. Estructura `Node`: Se define una estructura para almacenar el valor y el índice de cada elemento en el árbol de torneo.
2. Construcción del árbol de torneo: La función `buildTournamentTree` construye el árbol de torneo a partir del arreglo de entrada.
3. Extracción del mínimo: La función `extractMin` extrae el valor mínimo del árbol de torneo y actualiza la estructura para mantener la propiedad del árbol.
4. Ordenamiento: La función `tournamentSort` utiliza las funciones anteriores para ordenar el arreglo.
5. Función principal: En `main`, se define un arreglo de ejemplo, se llama a `tournamentSort`, y se imprime el arreglo ordenado.

Compilación y ejecución


Para compilar y ejecutar el programa, puedes usar un compilador de C como `gcc`:

1
2
gcc -o tournament_sort tournament_sort.c
./tournament_sort

Este código debería proporcionarte una buena base para implementar el ordenamiento por selección utilizando árboles de torneo.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar