InsertSort of double list linked to simple list

Navigation
1

I have 2 lists (one simple and one double), in the double implement the method of insertsort without any problem and I would like to implement the same sorting method but in the simple list, the code is as follows.

Insert at start: 

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;
}

Sorting method: 

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;
}
}

This is how I have it to be able to sort it in the double linked list. What would be the way to implement it in the list simply linked, since therefore in the simple list there is no part ANT only part SIG .

    
asked by Eduardo Javier Maldonado 05.05.2016 в 09:21
source

2 answers

1

Depends on the type of order you want the algorithm may vary; You could try a lifelong bubble , which is more known for its simplicity than for its efficiency.

For example: 

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);
            }
        }
    }
}

You can see the code working [here] .

Evidently I have invented the Vendedor and the Listaven , I do not know what your implementation is.

    
answered by 05.05.2016 / 17:09
source
1

The best way to sort, from my point of view, a simple list is to dump all the elements to a vector, sort that vector and then reconstruct the simple list.

Why? First because it is much less cumbersome and secondly because in a simple linked list you do not have pointers that allow you to go back, which forces you to go through the list from the beginning for each iteration. In addition, working on a vector allows you to avoid the transfer of pointers since no elements will be lost in the vector. Once the list is sorted the member sig is updated and ready. 

// 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];
}

However, to apply the principle that you comment you should manually save the pointer to the previous node that you intend to move to, in such a way that it is possible to recompose the list correctly. You can find an example in the comment link of @PaperBirdMaster, so I do not think it's convenient to duplicate a similar code in this answer.

Greetings.

    
answered by 05.05.2016 в 09:42
Two variables onclick event How to save a two-dimensional arrangement in a one-dimensional