#include <iostream>

using namespace std;

template <class T>
int compare(T zm1, T zm2)
    {
    if(zm1 > zm2)
	{
	return 1;
	}
    else if( zm1 < zm2)
	{
	return -1;
	}
    else
	{
	return 0;
	}

    }

template <class A>
class Lista
    {
    struct Element
	{
	A value;
	Element *next;
	};
    public:
    Element *lista;
    Lista(){lista=new Element;};
    Lista(const Lista&wzorzec);
    ~Lista(){};
    void dodajElement(A elm)
	{
	Element *nowy=new Element;
	nowy->value=elm;
	nowy->next=NULL;
	if(lista==NULL)
	    {
	    lista=nowy;
	    }
	else
	    {
	    Element *poczatek=lista;
	    while(poczatek->next!=NULL)
		{
		poczatek=poczatek->next;
		}
	    poczatek->next=nowy;
	    }
	}

    void wyswietl()
	{
	Element *pocz=lista;
	pocz=pocz->next;
	while(pocz)
	    {
	    cout<<pocz->value<<endl;
	    pocz=pocz->next;
	    }

	}

    void sortuj()
	{
	Element *wyn=lista;
	Element *sort=lista;
	Element *sort2=lista;
	wyn=wyn->next;
	sort=sort->next;
	sort2=sort2->next->next;
	while(wyn)
	    {
	    if(compare(sort,sort2)==1)
		{
		wyn->next=sort2;
		sort=sort->next;
		sort2=sort2->next;
		}
	    else if(compare(sort,sort2)==-1)
		{
		wyn->next=sort;
		sort=sort->next;
		sort2=sort2->next;

		}
	    else
		{
		wyn->next=sort;
		sort=sort->next;
		sort2=sort2->next;

		}
	    }

	}

    };

int main()
{
int ilosc,x;
cout<<"Podaj ilosc liczb ktore chcesz umiescic na liscie: ";
cin>>ilosc;
Lista<int> a;
while(ilosc!=0)
    {
    cout<<"Podaj wartosc do wpisania na liste: ";
    cin>>x;
    a.dodajElement(x);
    ilosc--;
    }
a.sortuj();
a.wyswietl();

}