[Duda] Inserción en una tabla ordenada

[Denok]

Hola, mirar estoy intentando hacer el ejercicio siguiente:

Hacer un procedimiento
    void insereix(vector <double>& v);

que, suponiendo que todas las posiciones de v, excepto quizas la ultima,estan ordenadas de pequeño a grande, deje v totalmente ordenado de pequeño a grande.
Un ejemplo seria, si v fuera (2,4,7,7,8,9,5), deberia quedar(2,4,5,7,7,8,9).

El codigo que yo he hecho es el siguiente:

Código (cpp) [Seleccionar] Expandir



#include <iostream>
#include <vector>
using namespace std;

void insereix(vector <double>& v){
    int n = v.size();
    int k = v[n-1];
    vector <double> vi(n);
    bool inserit = false;
    int j;

    for(int i = 0; i < n and not(inserit); ++i){
        if(v[i] <= k){
            vi[i] = v[i];
        } else {
            vi[i] = k;
            inserit = true;
            j = i + 1;
        }
    }

    for(int i = j; i < n;++i){
        vi[i] = v[i];
    }
}

int main(){
    int n;
    cin >> n;
    vector <double> v1(n);
    for(int i = 0; i < n; ++i)
        cin >> v1[i];

    insereix(v1);

    for(int i = 0; i < n; ++i)
        cout << v1[i];

}


Pero cuando imprimo me sale el vector exactamente igual que lo he introducido.
Para explicar un poco el código de la función, lo que hago es crear un nuevo vector donde guardare el antiguo vector ordenado.
Declaro una variable(k) donde guardo el valor de la ultima posición, y con un for voy comprobando si cada posición es menor o igual a la ultima. Si no es así, introduzco en esa posición el valor de k, y con una variable booleana puesta en false, hago que no se ejecute el código.

Luego solo hago otro for para rellenar el vector desde la siguiente posición de k.

No entiendo porque no funciona.

Muchas gracias y adiós!.

[El_Java]

Hombre, puestos a usar métodos predefinidos puedes usar la función sort (sí, es standar):

Código (cpp) [Seleccionar] Expandir

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main(){
    vector<double> v(7);
    v[0] = 2; v[1] = 4; v[2] = 7; v[3] = 7; v[4] = 8; v[5] = 9; v[6] = 5;
    // v == {2,4,7,7,8,9,5}
    for(int y=0; y<(int)v.size(); y++) cout << v[y];
    cout << endl;
    sort(v.begin(), v.end());
    // v == {2,4,5,7,7,8,9}
    for(int x=0; x<(int)v.size(); x++) cout << v[x];
    cout << endl;

    return 0;
}

Si no quieres usar la funcion sort, hazlo con las funciones que te da la clase vector, esta es tu función pero echa por mi:

Código (cpp) [Seleccionar] Expandir


void insereix(vector <double>& v){
    int x;
    for(x=0; x<(int)v.size(); x++) if(v[x] >= v[v.size()-1]) break; //para cuando encuentra un valor mas grande que v[v.size()-1]
    v.insert(v.begin()+x, v[v.size()-1]); //lo inserta en x
    v.erase(v.end()-1); //borra el ultimo valor
}

PD: En tu función v nunca cambia porque usas un vector auxiliar y la funcion es de tipo void, añade swap(v, vi); al final de tu función y #include <algorithm> al principio del archivo y verás que de todas formas no haces bien el ordenamiento.

[Denok]

Gracias por responder!!.

Lo que pasa es que no puedo usar ninguna de las dos opciones que me explicas(no me dejan). Cual seria la manera para que me quedara bien ordenado, no entiendo porque no se ordena bien.
Que tendría que modificar de mi código para que quedase bien?
Tampoco entiendo tu pd, que tiene que ver que sea una función void ? Si me lo explicaras me harías un favor.

Muchas gracias!!

Adiós.

[El_Java]

Claro que te lo explico, no hay problema:
en tu función lo que haces es ir añadiendo elementos del vector v al vector NUEVO vi, pero sin embargo, al terminar la función no retornas nada, por lo que el vector v va a seguir igual porque no lo has modificado, y el modificado vi no lo usas para nada, por lo que al terminar la función 'desaparece'.

tu función "arreglada":

Código (cpp) [Seleccionar] Expandir

#include <algorithm> //mete esto en los includes
void insereix(vector <double>& v){
    int n = v.size();
    int k = v[n-1];
    vector <double> vi(n);
    bool inserit = false;
    int j;

    for(int i = 0; i < n && !inserit; ++i){ //he cambiado and not por && !
        if(v[i] <= k){
            vi[i] = v[i];
        } else {
            vi[i] = k;
            inserit = true;
            j = i + 1;
        }
    }

    for(int i = j; i < n;++i){
        vi[i] = v[i-1]; //tambien te he metido el -1 en el v
    }

    swap(vi, v); //intercambia vi y v
}

saludos.

[Denok]

La web que evalúa el programa me dice que no funciona, pero el código funciona muy bien en mi ordenador.

Muchas gracias !

Pero una cosa, las funciones de tipo void, son procedimientos por lo que no pueden retornar nada no? Siempre tengo que usar swap si uso un vector auxiliar ?

Gracias por todo.
Adios!

[ghastlyX]

Por lo que veo estás haciendo un problema del Jutge en la versión catalana por el nombre de la función, así que asumiré que estás haciendo o un Grado en Matemáticas en la FME o un Grado en Informática en la FIB, que son las dos carreras que lo utilizan. Esto lo digo porque al ser la primera asignatura de programación, suelen ser estrictos con el estilo al programar, así que voy a intentar hacer todo según el estilo que marcan en ambas asignaturas.

Vayamos por partes. El último código que se ha puesto cuando lo envíes si lo envías verás que no funciona, puesto que hay un fallo que tenías que sigue ahí y es que haces casting a int con la variable k y el vector es de double, de manera que las comparaciones van a hacerse raras y el número si tenía decimales quedará modificado. Aparte de eso, en tu código utilizas un vector auxiliar que no se necesita para nada, de forma que gastas memoria tontamente haciendo el código además bastante más largo, cosa que en un examen te valorarían (o almenos deberían, con el grado no se cómo puntúan sobretodo en la FIB) bastante mal en la corrección manual, por mucho que el Jutge de un verde.

La idea de la solución es simple y es comenzar por el final e ir intercambiando los elementos mientras sea necesario.

Un pequeño código que he hecho y que debería funcionar es el siguiente:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

void insereix(vector<double>& v){
    int n = v.size();
    for (int i = n - 1; i > 0 and v[i] < v[i - 1]; --i) swap(v[i], v[i - 1]);
}

Como ves, sin usar vectores auxiliares queda todo mucho más simple, natural y corto. La función swap no recuerdo si la podéis usar, si no podéis es muy sencilla de implementar (de hecho es uno de los problemas de la lista si no recuerdo mal).

[Denok]

La clavas en todo, estoy haciendo primero en la FIB, programando los algoritmos fundamentales.

Tu código funciona muy bien, y tu manera es mucho mas sencilla, lastima que no se me ocurriera xD

Creo que no nos dejan usar la función swap, la tenemos que programar pero eso es sencillo.

Muchas gracias por todo.
Algún consejo que me puedas dar a la hora de programar, para que puntúen bien en los exámenes? Es que se acerca el final y así voy mejor preparado.

Muchísimas gracias por todo.
Adiós.

[ghastlyX]

No hay mucho misterio, si quieres programar bien y saber hacer ejercicios de programación, se aprende a base de programar. No es simple cuestión de conocer el lenguaje, sino de saber resolver problemas de tipo a veces más algorítmico que de implementación. Para todo esto, la única opción es practicar y para eso está el Jutge. A programar se aprende programando y si alguna cosa no te sale, pregunta.

Aparte de eso, intenta adaptarte al estilo que marcan en la asignatura para que no te bajen puntos por estilo (en la FIB con el grado no sé si lo siguen haciendo, pero me imagino que sí).

[Denok]

Si, siguen haciendo lo de las notas de estilo.

Muchas gracias !