main.cpp

#include <iostream>
#include <ctime>
#include <cstdio>

#define n 20

using namespace std;

void input(int k, int* a);

void output(int k, int a[]);

void copy(int k, int* a, int* b);

void bubble_sort(int k, int* a);

void bubble_sort_new(int k, int* a);

void shaker_sort(int k, int* a);

void insert_sort(int k, int* a);

void select_sort(int k, int* a);

void shell_sort(int k, int* a);

int increment(int* inc, long size);

void shell_sort_new(int k, int* a);

int main()
{
	//const int n = 20;
	//srand(time(0));

	cout << endl;
	int a[n], b[n];
	input(n, a);
	output(n, a);

	copy(n, a, b);
	bubble_sort(n, a);
	//output(n, a);

	copy(n, b, a);
	bubble_sort_new(n, a);
	//output(n, a);

	copy(n, b, a);
	shaker_sort(n, a);
	//output(n, a);

	copy(n, b, a);
	insert_sort(n, a);
	//output(n, a);

	copy(n, b, a);
	select_sort(n, a);
	//output(n, a);

	copy(n, b, a);
	shell_sort(n, a);
	//output(n, a);

	copy(n, b, a);
	shell_sort_new(n, a);
	//output(n, a);

	return 0;
}

void input(int k, int* a)
{
	for (int i = 0; i < k; i++)
		a[i] = rand() % 100;
}

void output(int k, int a[])
{
	for (int i = 0; i < k; i++)
		printf("%d ", a[i]);

	cout << endl << endl;
}

void copy(int k, int* a, int* b)
{
	for (int i = 0; i < k; i++)
		b[i] = a[i];
}

void bubble_sort(int k, int* a)
{
	cout << "Bubble sort";

	int c = 0;
	int r = 0;

	for (int i = 0; i < k - 1; i++)
	{
		for (int j = k - 1; j > 0; j--)
		{
			c++;
			if (a[j - 1] > a[j])
			{
				r++;
				int temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}
	}

	printf("\t\tcompared %d\treshuffled %d\n", c, r);
}

void bubble_sort_new(int k, int* a)
{
	cout << "Bubble sort (new)";

	int i = 0, j, temp, m, c = 0, r = 0;

	do
	{
		m = i;
		for (j = k - 1; j > m; j--)
		{
			c++;
			if (a[j - 1] > a[j])
			{
				r++;
				i = j;
				temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}
	} while (i - m);

	printf("\tcompared %d\treshuffled %d\n", c, r);
}

void shaker_sort(int k, int* a)
{
	cout << "Shaker sort";

	int i, j, temp, n1 = 0, n2 = k - 1, c = 0, r = 0;

	do
	{
		for (i = n2; i > n1; i--)
		{
			c++;
			if (a[i - 1] > a[i])
			{
				r++;
				j = i;
				temp = a[i - 1];
				a[i - 1] = a[i];
				a[i] = temp;
			}
		}

		n1 = j;

		for (i = n1; i <= n2; i++)
		{
			c++;
			if (a[i - 1] > a[i])
			{
				r++;
				temp = a[i - 1];
				a[i - 1] = a[i];
				a[i] = temp;
				j = i;
			}
		}

		n2 = j - 1;
	} while (n1 < n2);

	printf("\t\tcompared %d\treshuffled %d\n", c, r);
}

void insert_sort(int k, int* a)
{
	cout << "Insert sort";

	int i, j, temp, c = 0;
	double r = 0;

	for (i = 1; i < k; i++)
	{
		if (a[i] < a[i - 1])
		{
			c++;
			temp = a[i];
			r++;

			for (j = i - 1; j >= 0 && a[j] > temp; j--, c++)
			{
				r++;
				a[j + 1] = a[j];
				r++;
			}

			a[j + 1] = temp;
			r++;
		}
	}

	printf("\t\tcompared %d\treshuffled %lf\n", c, r / 3);
}

void select_sort(int k, int* a)
{
	cout << "Select sort";

	int i, j, temp, min, c = 0, r = 0;
	double r1 = 0;
	for (i = 0; i < k - 1; i++)
	{
		min = i;
		for (j = i + 1; j < k; j++)
		{
			c++;
			if (a[j] < a[min])
			{
				min = j;
				r1++;
			}
		}
		c++;
		if (i != min)
		{
			r++;
			temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}

	printf("\t\tcompared %d\treshuffled %lf\n", c, r + r1 / 3);
}

void shell_sort(int k, int* a)
{
	cout << "Shell sort";

	int i, j, temp, step = k / 2, c = 0, r = 0;

	while (step)
	{
		for (i = 0; i < (k - step); i++)
		{
			c++;
			j = i;

			while (j >= 0 && a[j] > a[j + step])
			{
				c++;
				r++;
				temp = a[j];
				a[j] = a[j + step];
				a[j + step] = temp;
				j -= step;
			}
		}
		step /= 2;
	}

	printf("\t\tcompared %d\treshuffled %d\n", c, r);
}

int increment(int* inc, long size)
{
	int p1, p2, p3, s;
	p1 = p2 = p3 = 1;
	s = -1;

	do
	{
		if (++s % 2)
			inc[s] = 8 * p1 - 6 * p2 + 1;
		else
		{
			inc[s] = 9 * p1 - 9 * p3 + 1;
			p2 *= 2;
			p3 *= 2;
		}

		p1 *= 2;
	} while (3 * inc[s] < size);

	return s > 0 ? s - 1 : 0;
}

void shell_sort_new(int k, int* a)
{
	cout << "Shell sort (new)";

	int i, j, temp, step, c = 0, r = 0, seq[40], s;
	s = increment(seq, k);

	do
	{
		step = seq[s--];
		for (i = 0; i < (k - step); i++)
		{
			c++;
			if (a[i] > a[i + step])
			{
				j = i;
				temp = a[i + step];
				r++;

				while (j >= 0 && a[j] > temp)
				{
					c++;
					r++;
					a[j + step] = a[j];
					j -= step;
				}

				a[j + step] = temp;
				r++;
			}
		}
	} while (step - 1);

	printf("\tcompared %d\treshuffled %d\n", c, r);
}