An algorithme to sort a liste

sort_list.cpp

#include <iostream>

using namespace std;

struct elemento
{
	int valor;
	elemento *proximo;
};

void imprime_lista(elemento *begin)
{
	cout << "Imprimindo lista!" << endl;
	while(begin != NULL)
	{
		cout << begin->valor << endl;
		begin = begin->proximo;
	}
	cout << "Fim de imprimir lista!" << endl;
}

elemento *lista_add(elemento *begin, int novo_valor)
{
	// Essa funcao cria um novo elemento da lista, e adiciona o novo_valor no inicio da lista.
	elemento *novo_elemento;
	novo_elemento = new elemento();

	novo_elemento->valor = novo_valor; // O valor dentro do elemento criado eh o mesmo que o recebido pelo argumento
	novo_elemento->proximo = begin; // Como adicionamos o novo elemento no inicio da lista
									// Entao o antigo inicio vai ser o segundo elemento.
	return novo_elemento;
}

int tamanho_lista(elemento *begin)
{
	int tamanho = 0;
	while(begin != NULL)
	{
		begin = begin->proximo;
		tamanho += 1;
	}
	return tamanho;

}

elemento *ordena_lista(elemento *inicio)
{
	// Essa funcao de ordenar utiliza o algoritmo do BubbleSort
	// A ordem desse algoritmo é O(n2), mas usaremos pois eh mais simples de entender.
	int i, tamanho;
	int temp;
	elemento *begin, *next;

	tamanho = tamanho_lista(inicio);
	cout << "Organizando uma lista de tamanho " << tamanho << endl;
	
	for(i = 0; i < tamanho; i++)
	{
		begin = inicio;
		next = begin->proximo;
		while(next != NULL)
		{
			if(begin->valor > next->valor) // Se o valor à esquerda é maior, queremos trocar, pois à esquerda o valor é menor
			{
				temp = begin->valor;
				begin->valor = next->valor;
				next->valor = temp;
			}
			begin = begin->proximo;
			next = begin->proximo;
		}
	}
	
	cout << "Fim de organizar lista" << endl;
	return inicio;
}

int main()
{
	elemento *begin; // O comeco da lista, até o momento está nulo.
	
	// Aqui adicionamos os elementos
	begin = lista_add(begin, 2);
	begin = lista_add(begin, 7);
	begin = lista_add(begin, 3);
	begin = lista_add(begin, 1);
	begin = lista_add(begin, 9);
	begin = lista_add(begin, 6);

	// Como a adicao foi no inicio, entao 2 eh o ultimo elemento, e 6 o primeiro
	// Entao a ordem que esta eh:
	// 6  9  1  3  7  2
	imprime_lista(begin);

	// Ordenamos a nossa lista
	begin = ordena_lista(begin);

	// Uma vez que ja organizamos a lista, eh esperado que os elementos estejam na ordem
	// Entao a ordem esperada eh:
	// 1  2  3  6  7  9
	imprime_lista(begin);

	return 0; // Fim do programa
}