Lab13, Lab14, Lab15

lab13.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void RandomShuffle(int *a, int n)
{
	srand(time(NULL));
	for (int i = n; i > 0; --i)
	{
		int cur = a[i - 1];
		int index = rand() % i;
		a[i - 1] = a[index];
		a[index] = cur;
	}
}
void create(int *mass, int size)
{
	for (int t = 0; t < size; t++)
	{
		mass[t] = t;
	}
	RandomShuffle(mass, size);
}

void BubbleSort(int *main, int size)
{
	if (main == NULL)
	{
		return;
	}
	int *mass = (int*)malloc(size * sizeof(int));
	memcpy(mass, main, size * sizeof(int));
	unsigned long countCompare = 0, countShift = 0;
	for (int i = 0; i < size; i++)
	{
		for (int j = size-1; j > i; j--)
		{
			countCompare++;
			if (mass[j] < mass[j - 1])
			{
				int cur = mass[j - 1];
				mass[j - 1] = mass[j];
				mass[j] = cur;
				countShift++;
			}
		}
		//printf("%d ", mass[i]);
	}
	printf("\nСортировка пузырьком:\nСравнений: %d.\nПерестановок: %d.\n", countCompare, countShift);
}

void PasteSort(int *mass, int size)
{
	if (mass == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	for (int i = 1; i < size; i++)
	{
		shiftCount++;
		int temp = m[i];
		int j = i - 1;
		compareCount++;
		while (j >= 0 && temp < m[j])
		{
			compareCount++;
			shiftCount++;
			m[j + 1] = m[j];
			j--;
		}
		shiftCount++;
		m[j + 1] = temp;
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", m[i]);
	//}
	printf("\nМетод вставок:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount/3);
}

void SelectSort(int *mass, int size)
{
	if (mass == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	for (int i = 0; i < size; i++)
	{
		shiftCount++;
		int min = m[i];
		int k = i;
		for (int j = i + 1; j < size; j++)
		{
			compareCount++;
			if (m[j] < min)
			{
				shiftCount++;
				min = m[j];
				k = j;
			}
		}
		if (k != i)
		{
			m[k] = m[i];
			m[i] = min;
			shiftCount = shiftCount + 2;
		}
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", m[i]);
	//}
	printf("\nСортировка выбором:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount);
}

void SelectSortClassic(int *mass, int size)
{
	if (mass == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	for (int i = 0; i < size; i++)
	{
		int k = i;
		for (int j = i + 1; j < size; j++)
		{
			compareCount++;
			if (m[j] < m[k])
			{
				k = j;
			}
		}
		if (k != i)
		{
			int min = m[k];
			m[k] = m[i];
			m[i] = min;
			shiftCount++;
		}
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", m[i]);
	//}
	printf("\nСортировка выбором(классическая):\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount);
}
void main()
{
	setlocale(LC_ALL, "rus");
	int size;
	printf("Введите кол-во элементов в массиве.\n");
	scanf("%d", &size);
	int *mass = (int*)malloc(size * sizeof(int));
	create(mass, size);
	//printf("Исходные данные:\n");
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", mass[i]);
	//}
	printf("\n");
	int select;
	while (true)
	{
		printf("1)Сортировка обменом.\n2)Сортировка вставками.\n3)Сортировка выбором.\n4)Сортировка выбором(классическая).\n5)Выход.\n");
		scanf("%d", &select);
		if (select == 1)
		{
			BubbleSort(mass, size);
		}
		else if (select == 2)
		{
			PasteSort(mass, size);
		}
		else if (select == 3)
		{
			SelectSort(mass, size);
		}
		else if (select == 5)
		{
			break;
		}
		else if (select == 4)
		{
			SelectSortClassic(mass, size);
		}
	}
	system("pause");
}

Lab14.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <locale.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>
void RandomShuffle(int *a, int n)//перемешивание массива
{
	srand(time(NULL));
	for (int i = n; i > 0; --i)
	{
		int cur = a[i - 1];
		int index = rand() % i;
		a[i - 1] = a[index];
		a[index] = cur;
	}
}
void create(int *mass, int size)//создание массива с неповт. ключами
{
	for (int t = 0; t < size; t++)
	{
		mass[t] = t;
	}
	RandomShuffle(mass, size);
}

void BubbleSort(int *main, int size)
{
	if (main == NULL)
	{
		return;
	}
	int *mass = (int*)malloc(size * sizeof(int));
	memcpy(mass, main, size * sizeof(int));
	unsigned long countCompare = 0, countShift = 0;
	for (int i = 0; i < size; i++)
	{
		for (int j = size - 1; j > i; j--)
		{
			countCompare++;
			if (mass[j] < mass[j - 1])
			{
				int cur = mass[j - 1];
				mass[j - 1] = mass[j];
				mass[j] = cur;
				countShift++;
			}
		}
		//printf("%d ", mass[i]);
	}
	printf("\nСортировка пузырьком:\nСравнений: %d.\nПерестановок: %d.\n", countCompare, countShift);
}

void PasteSort(int *mass, int size)
{
	if (mass == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	for (int i = 1; i < size; i++)
	{
		shiftCount++;
		int temp = m[i];
		int j = i - 1;
		compareCount++;
		while (j >= 0 && temp < m[j])
		{
			compareCount++;
			shiftCount++;
			m[j + 1] = m[j];
			j--;
		}
		shiftCount++;
		m[j + 1] = temp;
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", m[i]);
	//}
	printf("\nМетод вставок:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount / 3);
}

void SelectSort(int *mass, int size)
{
	if (mass == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	for (int i = 0; i < size; i++)
	{
		shiftCount++;
		int min = m[i];
		int k = i;
		for (int j = i + 1; j < size; j++)
		{
			compareCount++;
			if (m[j] < min)
			{
				shiftCount++;
				min = m[j];
				k = j;
			}
		}
		if (k != i)
		{
			m[k] = m[i];
			m[i] = min;
			shiftCount = shiftCount + 2;
		}
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", m[i]);
	//}
	printf("\nСортировка выбором:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount / 3);
}

void SelectSortClassic(int *mass, int size)
{
	if (mass == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	for (int i = 0; i < size; i++)
	{
		int k = i;
		for (int j = i + 1; j < size; j++)
		{
			compareCount++;
			if (m[j] < m[k])
			{
				k = j;
			}
		}
		if (k != i)
		{
			int min = m[k];
			m[k] = m[i];
			m[i] = min;
			shiftCount++;
		}
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", m[i]);
	//}
	printf("\nСортировка выбором(классическая):\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount);
}

void QuickSort(int *mass, int left, int right, unsigned long &compareCount, unsigned long &shiftCount)
{
	if (mass == NULL)
	{
		return;
	}
	int i = left, j = right;
	int medium = mass[(i + j)/2];
	do
	{
		compareCount++;
		while (mass[i] < medium)
		{
			i++;
			compareCount++;
		}
		compareCount++;
		while (mass[j] > medium)
		{
			compareCount++;
			j--;
		}
		if (i <= j)
		{
			shiftCount++;
			int temp = mass[i];
			mass[i] = mass[j];
			mass[j] = temp;
			i++;
			j--;
		}
	} while (i < j);
	if (left < j)
	{
		QuickSort(mass, left, j, compareCount, shiftCount);
	}
	if (right > i)
	{
		QuickSort(mass, i, right, compareCount, shiftCount);
	}
}

void ShellSort(int *m, int size)
{
	if (m == NULL)
	{
		return;
	}
	unsigned long compareCount = 0, shiftCount = 0;
	int *mass = (int*)malloc(size * sizeof(int));
	memcpy(mass, m, size * sizeof(int));
	int k = (int)log2(size);
	int *steps = (int*)malloc(k * sizeof(int));
	for (int i = 0; k >= 1; k--, i++)
	{
		steps[i] = pow(2, k) - 1;
	}
	for (int m = 0; m < (int)log2(size); m++)
	{
		for (int i = steps[m]; i < size; i++)
		{
			shiftCount++;
			int temp = mass[i], j = i - steps[m];
			compareCount++;
			while (j >= 0 && temp < mass[j])
			{
				shiftCount++;
				compareCount++;
				mass[j + steps[m]] = mass[j];
				j = j - steps[m];
			}
			shiftCount++;
			mass[j + steps[m]] = temp;
		}
	}
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", mass[i]);
	//}
	printf("\nМетод Шелла:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount/3);
}

void step2(int *mass, int size, unsigned long &shiftCount, unsigned long &compareCount)
{
	int k = size - 1;
	int temp, num = 0, i = 0, step = 0;
	bool stop = false;
	while (k > 0)//кол шагов
	{
		shiftCount++;
		temp = mass[0];
		mass[0] = mass[k];
		mass[k] = temp;//последний перемещается в начало
		k--;//последний на своем месте
		while ((2 * i + 1 <= k) && (stop == false))//просеиванием элемента через пирамиду
		{//пока у элемента есь потомки
			if (2 * i + 2 <= k)
			{
				if (mass[2 * i + 1] < mass[2 * i + 2])
				{
					compareCount++;
					num = 2 * i + 2;
				}
				else
				{
					compareCount++;
					num = 2 * i + 1;
				}
			}
			else
			{
				num = 2 * i + 1;
			}
			if (mass[i] <= mass[num])//замена элемента одним из его потомком
			{
				compareCount++;
				shiftCount++;
				temp = mass[num];
				mass[num] = mass[i];
				mass[i] = temp;
				i = num;
			}
			else //если ни один из потомков не больше заданного
			{
				compareCount++;
				stop = true;
			}
		}
		stop = false;
		i = 0;
	}
}
void PyramidSort(int *m, int size)
{
	bool stop = false;
	int i = size / 2 - 1;
	unsigned long compareCount = 0, shiftCount = 0;
	int *mass = (int*)malloc(size * sizeof(int));
	memcpy(mass, m, size * sizeof(int));
	int max, temp, num, p1, p2, co = 0;
	while (i >= 0)
	{
		if ((2 * i + 1 <= size - 1) && (2 * i + 2 <= size - 1))//выбирается максимальный потомок
		{
			p1 = mass[2 * i + 1];
			p2 = mass[2 * i + 2];
		}
		else
		{
			if (2 * i + 1 <= size - 1)
			{
				p1 = mass[2 * i + 1];
				p2 = p1 - 1;
			}
		}
		if (p1 > p2)
		{
			compareCount++;
			max = p1;
			num = 2 * i + 1;
		}
		else
		{
			compareCount++;
			max = p2;
			num = 2 * i + 2;
		}//выбирается максимальный потомок
		if (mass[i] < max)
		{
			compareCount++;
			if (num > size / 2 - 1)//у потомка нет потомков
			{
				shiftCount++;
				temp = mass[i];
				mass[i] = mass[num];
				mass[num] = temp;
			}
			else//у потомка есть свои потомки
			{
				shiftCount++;
				temp = mass[i];
				mass[i] = mass[num];
				mass[num] = temp;
				int j = num;
				while ((2 * j + 1 <= size - 1) && (stop != true))
				{

					p1 = mass[2 * j + 1];
					if (2 * j + 2 <= size - 1)
					{
						p2 = mass[2 * j + 2];
					}
					if (p1 > p2)
					{
						compareCount++;
						max = p1;
						num = 2 * j + 1;
					}
					else
					{
						max = p2;
						num = 2 * j + 2;
					}
					if (mass[j] < max)
					{
						shiftCount++;
						compareCount++;
						temp = mass[j];
						mass[j] = mass[num];
						mass[num] = temp;
						j = num;
					}
					else
					{
						stop = true;
					}
				}
				stop = false;
			}
		}
		else
		{
			compareCount++;
		}
		i--;
	}
	step2(mass, size, shiftCount, compareCount);
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", mass[i]);
	//}
	printf("\nПирамидальная сортировка:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount);
}
void main()
{
	setlocale(LC_ALL, "rus");
	int size;
	printf("Введите кол-во элементов в массиве.\n");
	scanf("%d", &size);
	int *mass = (int*)malloc(size * sizeof(int));
	create(mass, size);
	//printf("Исходные данные:\n");
	//for (int i = 0; i < size; i++)
	//{
	//	printf("%d ", mass[i]);
	//}
	printf("\n");
	int select;
	while (true)
	{
		printf("1)Сортировка обменом.\n2)Сортировка вставками.\n3)Сортировка выбором.\n4)Быстрая сортировка.\n5)Метод Шелла.\n6)Пирамидальная сортировка.\n7)Выход.\n");
		scanf("%d", &select);
		if (select == 1)
		{
			BubbleSort(mass, size);
		}
		else if (select == 2)
		{
			PasteSort(mass, size);
		}
		else if (select == 3)
		{
			SelectSort(mass, size);
		}
		else if (select == 7)
		{
			break;
		}
		else if (select == 4)
		{
			unsigned long compareCount = 0, shiftCount = 0;
			int *m = (int*)malloc(size * sizeof(int));
			memcpy(m, mass, size * sizeof(int));
			QuickSort(m, 0, size-1, compareCount, shiftCount);
			//for (int i = 0; i < size; i++)
			//{
			//	printf("%d ", mass[i]);
			//}
			printf("\nБыстрая сортировка:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount);
		}
		else if (select == 5)
		{
			ShellSort(mass, size);
		}
		else if (select == 6)
		{
			PyramidSort(mass, size);
		}
	}
	system("pause");
}

lab15.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <string.h>
#include <time.h>

struct ListItem
{
	int inf;
	ListItem *next;
	ListItem *left;
};
struct MassItem {
	ListItem *item;
	ListItem *tail;
};
void createRandom(int *mass,int size) //абсолютно рандомный массив
{
	srand(time(NULL));
	for (int i = 0; i < size; i++)
	{
		mass[i] = rand()%(size);
		//printf("%d ", mass[i]);
	}
	//printf("\n");
}
void RandomShuffle(int *a, int n)//перемешка массива
{
	srand(time(NULL));
	for (int i = n; i > 0; --i)
	{
		int cur = a[i - 1];
		int index = rand() % i;
		a[i - 1] = a[index];
		a[index] = cur;
	}
}
void create(int *mass, int size)//массив с неповт. ключами
{
	for (int t = 0; t < size; t++)
	{
		mass[t] = t;
	}
	RandomShuffle(mass, size);
}

void PocketSort2Mass(int *mass, int size)
{

	int shiftCount = 0;
	int *result = (int*)malloc(size * sizeof(int));
	for (int i = 0; i < size; i++)
	{
		printf("%d ", mass[i]);
	}
	for (int i = 0; i < size; i++)
	{

		result[mass[i]] = mass[i];
		shiftCount++;
	}
	printf("Карманная сортировка с вспомогательным массивом:\nСравнений: 0.\nПерестановок: %d.\n", shiftCount/3);

	printf("\n");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", result[i]);
	}
}

void PocketSort1Mass(int *mass, int size)
{
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	unsigned long shiftCount = 0, compareCount = 0;
	for (int i = 0; i < size; i++)
	{
		compareCount++;
		while (m[i] != i)
		{
			compareCount++;
			int temp = m[i];
			m[i] = m[temp];
			m[temp] = temp;
			shiftCount++;
		}
	}

	printf("\n");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", m[i]);
	}
	printf("\nКарманная сортировка:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount);
}

void PocketSortCommon(int *mass, int size)
{
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	unsigned long shiftCount = 0, compareCount = 0;
	MassItem *result = (MassItem*)malloc(size*(sizeof(MassItem)));
	for (int i = 0; i < size; i++)
	{
		result[i].item = NULL;
		printf("%d ", m[i]);
	}
	printf("\n");
	for (int i = 0; i < size; i++)
	{
		shiftCount++;
		ListItem *next = result[m[i]].item;
		result[m[i]].item = (ListItem*)malloc(sizeof(ListItem));
		result[m[i]].item->next = next;
		result[m[i]].item->inf = m[i];
	}
	for (int i = 0, j = 0; i < size; i++, compareCount++)
	{
		
		while (result[i].item != NULL && i < size)
		{
			compareCount++;
			shiftCount++;
			m[j] = result[i].item->inf;
			j++;
			result[i].item = result[i].item->next;
		}
	}
	printf("\nОбобщенная карманная сортировка:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount / 3);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", m[i]);
	}
}
void createForBitwise(int *mass, int size)//создание массива для поразрядной сортировке(3х разрядные числа)
{
	srand(time(NULL));
	printf("\n");
	for (int i = 0; i < size; i++)
	{
		mass[i] = rand() % 300 + 100;
		printf("%d ", mass[i]);
	}
	printf("\n");
}
void PocketSortBitwise(int *mass, int size)
{
	int *m = (int*)malloc(size * sizeof(int));
	memcpy(m, mass, size * sizeof(int));
	unsigned long shiftCount = 0, compareCount = 0;
	MassItem *result = (MassItem*)malloc(10*(sizeof(MassItem)));//*size
	for (int bitwise = 1; bitwise < 1000; bitwise = bitwise * 10)
	{
		for (int i = 0; i < 10; i++)
		{
			result[i].item = NULL;
			result[i].tail = NULL;
		}
		for (int i = 0; i < size; i++)
		{
			shiftCount++;
			int index = (m[i] % (10*bitwise)) / bitwise;
			ListItem *next = result[index].item;
			result[index].item = (ListItem*)malloc(sizeof(ListItem));
			result[index].item->next = next;
			result[index].item->left = NULL;
			result[index].item->inf = m[i];
			if (next != NULL)
			{
				//result[index].tail = next;	
				next->left = result[index].item;
			}
			else
			{
				result[index].tail = result[index].item;
			}
		}
		for (int i = 0, j = 0; i < 10; i++, compareCount++)
		{
			while ( result[i].tail != NULL && j < size)
			{
				compareCount++;
				shiftCount++;
				m[j] = result[i].tail->inf;
				result[i].tail = result[i].tail->left;
				j++;
			}
		}
	}
	printf("\n");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", m[i]);
	}
	printf("\nПоразрядная сортировка:\nСравнений: %d.\nПерестановок: %d.\n", compareCount, shiftCount / 3);
}
void main()
{
	setlocale(LC_ALL, "rus");
	int size;
	printf("Введите кол-во элементов в массиве.\n");
	scanf("%d", &size);
	int *mass = (int*)malloc(size * sizeof(int));
	create(mass, size);
	PocketSort2Mass(mass, size);
	PocketSort1Mass(mass, size);
	createRandom(mass, size);
	PocketSortCommon(mass, size);
	createForBitwise(mass, size);
	PocketSortBitwise(mass, size);
	system("pause");
}