#include <iostream>

using namespace std;

const int POCET=10;

void bubble(int p[],int n);

void shaker(int p[],int n);

int main()

{

	int a[POCET];

	int pole[POCET];		// vstupní pole pro trideni bubble sort

	int pole2[POCET];		// vstupní pole pro trideni  shaker sort

	int pocet=POCET;		// vstupni parametr - pocet prvku

	int k;

	for (k=0; k<pocet; k++)

    {        cout<<k<<".prvek pole = ";  cin>>a[k];  }

    cout<<endl; cout<<endl;

	for (k=0; k<pocet; k++)		// pole tridenych prvku presuneme

		pole[k]=a[k];			// do vstupniho pole pro trideni

	bubble(pole,pocet);

	cout<<"   Setridene pole (bubblesort):"<<endl;

	for (k=0; k<pocet; k++)		// cyklus pro zobrazeni vysledku

		{cout<<pole[k]<<"  " ;}

        cout<<endl; cout<<endl;

	for (k=0; k<pocet; k++)

		pole2[k]=a[k];

	shaker(pole2,pocet);

	cout<<"   Setridene pole (shakersort): "<<endl;

	for (k=0; k<pocet; k++)

		{cout<<pole2[k]<<"  " ;}

        cout<<endl;

	return 0;

}

void bubble(int p[],int n)  // trideni pole vymenou - bubblesort

{

	int i,j;

	int x;						// pomocna promenna pro vymenu

	for (i=1; i<n; i++)     // v 1. pruchodu se dostane nejmensi prvek nahoru

	{

	   for (j=n-1; j>=i; j--)

	   {

		 if (p[j-1] > p[j])		// inverze - provede se vymena

		 {

			x = p[j-1];

			p[j-1] = p[j];

			p[j] = x;

		 }

	   }

	}

}

void shaker(int p[],int n)

//trideni pole pretrasanim - shakersort

// vylepseni bublinkoveho sortu tim, ze se

// porovnava v obou smerech a pamatuji se

// mista poslednich zmen; prohlizime jen

// usek, kde jeste muze dojit k vymene

{

	int j,k,l,r;

	int x;

	l=1; r=k=n-1;

	do

	{

		for (j=r; j>=l; j--)  // probublava nejmensi prvek nahoru

		{

			if (p[j-1]>p[j])

			{

				x=p[j-1]; p[j-1]=p[j]; p[j]=x;

				k=j;			// oznaceni, kde doslo ke zmene

			}

		}

		l=k+1;					// misto posledni zmeny shora

		if (l>r) return;

		for(j=l; j<=r; j++)		// nejvetsi prvek dolu

		{

			if(p[j-1]>p[j])

			{

				x=p[j-1]; p[j-1]=p[j]; p[j]=x;

				k=j;			// oznaceni, kde doslo ke zmene

			}

		}

		r=k-1;					// misto posledni zmeny zdola

	}

	while (l<=r);

}