I have 2 lists (a simple one and a double one), in the double one I implement the method of insertsort
without any problem and I would like to implement the same ordering method but in the simple list, the code is the following.
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;
}
Ordering 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 so I can sort it in the doubly linked list. What would be the way to implement it in the simply linked list, since therefore in the simple list there is no part, ANT
only part SIG
.
The best way to sort, from my point of view, a simple list is to dump all the elements to a vector, sort this vector and then reconstruct the simple list.
Why? Firstly because it's much less cumbersome and secondly because in a simple linked list you don't have pointers to go back, forcing you to iterate through the list from the beginning for each iteration. Also, working on a vector allows you to avoid moving pointers since no element is going to be lost in the vector. Once the list is ordered, the member is updated
sig
and that's it.However, to apply the principle you mention, you should manually save the pointer to the node before the one you intend to move, so that you can recompose the list correctly. You have an example in the @PaperBirdMaster comment link, so I don't think it's convenient to duplicate a similar code in this answer.
All the best.
Depending on the type of sorting you want, the algorithm may vary; you could try a bubble of all life, which is known more for its simplicity than its efficiency.
For example:
You can see the code working [here] .
Obviously I have invented the
Vendedor
and theListaven
, I don't know what your implementation is.