#include <iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;

int N;
struct vezana{
	int broj;
	vezana *sljedeci;
};

void generiranje(){

}

int main(){
	vezana *lista = new vezana();
	lista -> sljedeci = NULL;

	cout << "Unesite N: ";
	cin >> N;

	//generiranje
	vezana *novi, *zadnji;
	zadnji = lista;
	while(zadnji -> sljedeci){
		zadnji = zadnji -> sljedeci;
	}
		srand(time(NULL));
	for(int i = 0; i < N; i++){
		novi = new vezana;
		zadnji -> sljedeci = novi;
		novi -> sljedeci = NULL;

		novi -> broj = rand()%N+1;

		zadnji = novi;
	}


	//ispis
	cout << endl << "Nesortirani ispis " << endl << "-------------------------" << endl;
	zadnji = lista -> sljedeci;
	while(zadnji -> sljedeci){
		cout << zadnji -> broj << " ";
		zadnji = zadnji -> sljedeci;
	}

	//sortiranje

	zadnji = lista;
	vezana *iduci;

	while(zadnji){

		iduci = zadnji -> sljedeci;

		novi = new vezana;
		novi = zadnji;
		int swapped, i, temp;
	    struct vezana *trenutni;
	    struct vezana *kraj = NULL;

	    do
	    {
	        swapped = 0;
	        trenutni = lista;

	        while (trenutni->sljedeci != kraj)
	        {
	            if (trenutni->broj > trenutni->sljedeci->broj)
	            {
	                temp = trenutni -> broj;
	                trenutni -> broj = trenutni -> sljedeci -> broj;
	                trenutni -> sljedeci -> broj = temp;
	                swapped = 1;
	            }
	            trenutni = trenutni->sljedeci;
	        }
	        kraj = trenutni;
	    }
	    while (swapped);
	    zadnji = iduci;
	}

	cout << endl << endl << "Sortirani ispis " << endl << "-------------------------" << endl;
	zadnji = lista -> sljedeci;
	while(zadnji){
		cout << zadnji -> broj << " ";
		zadnji = zadnji -> sljedeci;
	}

	cout << endl;
	system("Pause");
	return 0;
}