// lab2v23.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

struct List
{
	int x;
	List *Next;
};

/*ФУНКЦИЯ ДОБАВЛЕНИЯ ЭЛЕМЕНТА В СТЕК */
List* Add(int x, List *top)
{
	List *temp = new List;

	temp->x = x;
	temp->Next = top;
	top = temp;

	return(top);
}

/*ФУНКЦИЯ СОРТИРОВКИ СТЕКА*/
List* Sort(int s, List *top)
{
	List *temp1, *temp2, *temp3;

	for (int i = 1; i < s; i++) {
		temp1 = top;
		temp2 = top->Next;

		if (temp1->x > temp2->x) {
			top = temp2;
			temp1->Next = temp2->Next;
			temp2->Next = temp1;
		}

		temp1 = top;
		temp2 = top->Next;
		temp3 = temp2->Next;

		for (int j = 1; j < s - i; j++) {

			if (temp2->x > temp2->Next->x) {
				temp1->Next = temp3;
				temp2->Next = temp3->Next;
				temp3->Next = temp2;
			}

			cout << j << temp1->x << temp2->x << temp3->x << endl;

			temp1 = temp2;
			temp2 = temp3;
			temp3 = temp3->Next;
		}
	}

	return(top);
}

/*ФУНКЦИЯ ОТОБРАЖЕНИЯ СТЕКА*/
void Show(List *top)
{

	while (top->Next != NULL){

		cout << top->x << " ";
		top = top->Next;
	}
}


int main()
{
	List *top = new List;
	top->Next = NULL;

	int x, s;

	cout << "Enter size" << " ";
	cin >> s;

	for (int i = 0; i < s; i++) {

		cout << "Enter value" << " ";
		cin >> x;

		top = Add(x, top);
	}

	Show(top);

	top = Sort(s, top);

	Show(top);
}