2

Hola a todos tengo que ordenar n pares de coordenadas x,y en base a x sin utilizar matrices solo arreglos, lo intente hacer con el método de la burbuja, y funciona pero cuando son demasiadas coordenadas se vuelve demasiado lento, alguna sugerencia de como lo podría hacer?

Este es mi código

#include <stdio.h>
int main()
{
    int n,temp1=0,temp2=0;
    printf("Ingresa el numero de coordenadas: ");
    scanf("%d",&n);

    int cordenadax[n],cordenaday[n];
    for(int i=0; i<n; i++){
        printf("Coordenada %d\n",i+1);

        printf("Ingresa x: ");
        scanf("%d",&cordenadax[i]);
        printf("Ingresa y: ");
        scanf("%d",&cordenaday[i]);

        printf("\n");
    }
    for(int i=1; i<n; i++){
        for(int j=0; j<n-1; j++){
            if(cordenadax[j]>cordenadax[j+1]){
                temp1 = cordenadax[j];
                temp2 = cordenaday[j];

                cordenadax[j] = cordenadax[j+1];
                cordenaday[j] = cordenaday[j+1];

                cordenadax[j+1] = temp1;
                cordenaday[j+1] = temp2;
             }
        }
    }
    printf("\nCoordenadas ordenadas en base a x\n");
    for(int i=0; i<n; i++){
        printf("X:%d Y:%d\n",cordenadax[i],cordenaday[i]);
    }
    return 0;
}

Ejemplo de entrada y salida introducir la descripción de la imagen aquí

5
  • Me parece interesante, pero me cuesta un poquito de trabajo seguir todo tu código. ¿Podrías poner al final de tu post, un ejemplo de entrada de datos y un ejemplo de salida?
    – Cuauhtli
    el 29 sep. 2022 a las 1:15
  • 2
    listo ya lo edite
    – Richyms
    el 29 sep. 2022 a las 1:22
  • el algoritmo de ordenamiento burbuja es bastante ineficiente, aunque es el mas facil implementar, mientras mas grande y desordenado sea el conjunto mas lento es. Te recomiendo inversigar el ordenamiento por insercion. el 29 sep. 2022 a las 2:00
  • Si hay dos pares con la misma x, tomarías en cuenta la y también? O simplemente no importa?
    – Mateo
    el 29 sep. 2022 a las 2:13
  • @Mateo no importa que sean iguales
    – Richyms
    el 29 sep. 2022 a las 2:22

1 respuesta 1

1

Mi lenguaje C está oxidado, sin embargo, lo que hice fue reescribir el algoritmo quick sort de este sitio, y lo adecué para tu caso.

La única diferencia significativa es que en la función swap también realicé la reasignación para las coordenadas de Y.

Además que reescribí el código encapsulándolo para que sea más entendible:

#include <stdio.h>
#include <stdlib.h>

void get_data(int num_cord, int* coordenadas_x, int* coordenadas_y) {
    for (int i=0; i < num_cord; i++) {
        printf("Tupla %d\n", (i + 1));

        printf("Ingresa X: ");
        scanf("%d", &coordenadas_x[i]);
        
        printf("Ingresa Y: ");
        scanf("%d", &coordenadas_y[i]);
    }
}

void swap(int *primero, int *segundo) {
    int temp = *primero;
    *primero = *segundo;
    *segundo = temp;
}

int partition(int* coordenadas_x, int* coordenadas_y, int low, int high) {
    int pivot = coordenadas_x[high];
    int i = (low - 1);
    
    for (int j = low; j < high; j++) {
        if (coordenadas_x[j] <= pivot) {
            i++;
            swap(&coordenadas_x[i], &coordenadas_x[j]);
            swap(&coordenadas_y[i], &coordenadas_y[j]);
        }
    }

    swap(&coordenadas_x[i + 1], &coordenadas_x[high]);
    swap(&coordenadas_y[i + 1], &coordenadas_y[high]);
  
    return (i + 1);
}

void sort_coords(int* coordenadas_x, int* coordenadas_y, int low, int high) {
  if (low < high) {
    int pivot = partition(coordenadas_x, coordenadas_y, low, high);
    
    sort_coords(coordenadas_x, coordenadas_y, low, pivot - 1);
    sort_coords(coordenadas_x, coordenadas_y, pivot + 1, high);
  }
}

void print_xy_coords(int* coordenadas_x, int* coordenadas_y, int num_cord) {
    int i=0;
    while (i++ < num_cord)
        printf("%d -> X:%d,Y:%d\n", i, coordenadas_x[i], coordenadas_y[i]);
}

int* initialice_array(int size) {
    return (int *) malloc(sizeof(int) * size);
}

int main() {
    int num_cord;

    printf("Ingresa el numero de coordenadas: ");
    scanf("%d", &num_cord);
    
    int* coordenadas_x = initialice_array(num_cord);
    int* coordenadas_y = initialice_array(num_cord);

    get_data(num_cord, coordenadas_x, coordenadas_y);
    sort_coords(coordenadas_x, coordenadas_y, 0, num_cord);

    print_xy_coords(coordenadas_x, coordenadas_y, num_cord);

    free(coordenadas_x);
    free(coordenadas_y);

    return 0;
}

Y al ejecutarlo obtienes esto:

$ gcc ordenar.c -o ordenar && ./ordenar
Ingresa el numero de coordenadas: 5
Tupla 1
Ingresa X: 5
Ingresa Y: 50
Tupla 2
Ingresa X: 7
Ingresa Y: 70
Tupla 3
Ingresa X: 2
Ingresa Y: 20
Tupla 4
Ingresa X: 8
Ingresa Y: 80
Tupla 5
Ingresa X: 1
Ingresa Y: 10
1 -> X:1,Y:10
2 -> X:2,Y:20
3 -> X:5,Y:50
4 -> X:7,Y:70
5 -> X:8,Y:80

Yo utilicé gcc en WSL, pero debería ser similar para tu caso.

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.