#include <stdio.h>
#include <stdlib.h>

#define N 100

int main()
{
	int a[N];

	// Заполнение массива случайными числами
	srand(37);
	for (int i = 0; i < N; i++) a[i] = rand() % 1000;

	// Вывод исходного массива
	for (int i = 0; i < N; i++) printf("%4d", a[i]);
	printf("\n");

	// Определение левой и правой границы сортируемой области
	int L = 0;
	int R = N - 1;
	int k = 0;

	while (true) // "Бесконечный" цикл, прерывается break;
	{
		bool f = true; // Флаг, что не было ни одной перестановки

		// Проход ====>>>>>
		for (int i=L; i<R; i++)
			if (a[i] > a[i + 1]) 
			{
			  f = false; k++;
		      int x = a[i]; a[i] = a[i + 1]; a[i + 1] = x;
			}
		if (f) break;
		R--; // Правый элемент сдвигаем влево

		f = true;
		// Проход  <<<<======
		for (int i=R-1; i>=L; i--)
			if (a[i] > a[i + 1])
			{
				f = false; k++;
				int x = a[i]; a[i] = a[i + 1]; a[i + 1] = x;
			}
		if (f) break;
		L++; // Левый элемент сдвигаем вправо

	}

	for (int i = 0; i < N; i++) printf("%4d", a[i]);
	printf("\n");

	printf("== %d ==\n", k);



}