1

Tengo 2 listas (una simple y una doble), en la doble implemente el método de insertsort sin ningún problema y me gustaría implementar el mismo método de ordenamiento pero en la lista simple, el código es el siguiente.

Insertar al inicio:

void Listaven::insertaInicio(Vendedor dato) {
Nodo * tmp = new Nodo;
tmp->guardaObjeto(dato);
tmp->guardaNodoSig(NULL);
bool nada = vacia();

if (nada) {
    inicio = final = tmp;
}
else {
    tmp->sig = inicio;
    inicio->ant = tmp;
    tmp->ant = NULL;
    inicio = tmp;
}
ordenar();
int codigoVendedor = dato.damecodigoVendedor();
cout << "Has agregado un vendedor con el codigo: '" << codigoVendedor << "'" << endl;
}

Metodo de ordenamiento:

void Listaven::ordenar() {
Nodo *tmp = inicio;
Nodo *aux;
Vendedor recuperar;
while (tmp)
{
    recuperar = tmp->dato;
    aux = tmp;
    while (aux->ant != NULL && recuperar.damecodigoVendedor()<aux->ant->dato.damecodigoVendedor())
    {
        aux->dato = aux->ant->dato;
        aux = aux->ant;
    }
    aux->dato = recuperar;
    tmp = tmp->sig;
}
}

Así es como lo tengo para poder ordenarlo en la lista doblemente enlazada. Cual seria la forma para implementarlo en la lista simplemente enlazada, ya que por ende en la lista simple no hay parte ANT solo parte SIG.

1
  • 1
    Vaya, parece que ya respondí anteriormente cómo insertar ordenadamente en una lista simplemente enlazada (escoge la respuesta que más te guste, no tiene por qué ser la mía). Commented el 5 may. 2016 a las 7:31

2 respuestas 2

1

Depende del tipo de ordenación que quieras el algoritmo puede variar; podrías probar con un burbuja de toda la vida, que es más conocido por su sencillez que por su eficiencia.

Por ejemplo:

void ordenar()
{
    for (Nodo *head = inicio; head; head = head->sig)
    {
        for (Nodo *tail = head->sig; tail; tail = tail->sig)
        {
            if (head->dato.damecodigoVendedor() > tail->dato.damecodigoVendedor())
            {
                std::swap(head->dato, tail->dato);
            }
        }
    }
}

Puedes ver el código funcionando [aquí].

Evidentemente me he inventado el Vendedor y el Listaven, no se cuál es tu implementación.

2
  • No uso cualquier otro método porque asi es como me pidieron el proyecto, puedo usar selectSort o InsertSort, y prácticamente es así. Yo hago el método por separado y prácticamente lo hago llamar cuando inserto un nuevo dato. Es decir lo llamo como ordenacion(); para que haga su función y lo ordene al mismo tiempo de que lo inserta y listo ya los muestra de manera ordenada, pero solo logre hacer funcionar el insert en la doble, mas no en la simple. Por eso mi pregunta así tal cual. Commented el 5 may. 2016 a las 16:33
  • He hecho una implementación falsa de Listaven que ordena datos, puedes verlo aquí ¿te sirve? Commented el 6 may. 2016 a las 7:05
1

La mejor forma de ordenar, desde mi punto de vista, una lista simple es volcar todos los elementos a un vector, ordenar dicho vector y después reconstruir la lista simple.

¿Por qué? Primero porque es mucho menos engorroso y segundo porque en una lista enlazada simple no tienes punteros que te permitan retroceder, lo que te obliga a recorrer la lista desde el principio para cada iteración. Además, trabajar sobre un vector te permite evitar el trasiego de punteros ya que en el vector no se va a perder ningún elemento. Una vez ordenada la lista se actualiza el miembro sig y listo.

// Copiamos los nodos en el vector
std::vector<Nodo*> elementos;
for( auto nodo = inicio; nodo != nullptr; nodo=nodo->sig )
  elementos.push_back(nodo);

// Si la lista tiene 0 o 1 elementos no tiene sentido ordenar
if( elementos.size() > 1 )
{
  // Se ordena el vector
  // ...

  // Este elemento se añade para simplificar la costura de la lista
  elementos.push_back(nullptr);

  // Se recomponen la lista
  inicio = elementos[0];
  for(int i=elementos.size()-2; i>=0; i--)
    elementos[i]->sig = elementos[i+1];
}

No obstante, para aplicar el principio que comentas deberías guardar de forma manual el puntero al nodo anterior al que pretendes mover, de tal forma que te sea posible recomponer la lista correctamente. Un ejemplo lo tienes en el enlace del comentario de @PaperBirdMaster, por lo que no creo conveniente duplicar un código similar en esta respuesta.

Un saludo.

6
  • Me acabo de dar cuenta que es el mismo usuario el de esta pregunta y el que preguntó en el enlace que he puesto... o Eduardo Javier Maldonado no está entendiendo algo, o no lo estoy entendiendo yo, o ambas cosas, o el mundo es muy confuso :'( Commented el 5 may. 2016 a las 7:52
  • Lo mismo no le gustó o no entendió tu respuesta y volvió a preguntar... si vuelve a pasarse por este hilo que nos saque de dudas :)
    – eferion
    Commented el 5 may. 2016 a las 8:08
  • Lo quiero ordenar con un método de ordenamiento porque así lo necesito para un proyecto universitario, y la respuesta de PaperBirdMaster no la comprendí en la pregunta que anteriormente realice ya que lo que yo quiero es únicamente hacer lo que estoy haciendo aquí en la doble enlazada pero en la simple es decir en el método de INSERTAR ya solo llamo a la función Ordernar(); para que me ordene todo. Por eso únicamente necesito acomodar este método para que haga su función en una lista simple. Commented el 5 may. 2016 a las 8:38
  • No es lo mismo decir "lo quiero ordenar con un método de ordenamiento" que "lo tengo que ordenar con ese método de ordenamiento". Si simplemente necesitas ordenarlo puedes usar el algoritmo que más cómodo te resulte. Si es un requisito usar un en concreto las opciones obviamente se reducen, pero en ese caso es necesario explicar las cosas de forma concisa y clara.
    – eferion
    Commented el 5 may. 2016 a las 8:40
  • 1
    No eras el único confundido jejejeje, por eso comenté que es importante explicar las cosas correctamente
    – eferion
    Commented el 5 may. 2016 a las 9:02

Tu Respuesta

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

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