Skip to content

Instantly share code, notes, and snippets.

@romec512

romec512/Lab14.cpp

Created May 29, 2018 10:09
Show Gist options
  • Save romec512/52b472f5f9b73df2368119c5f3fce6f6 to your computer and use it in GitHub Desktop.
Save romec512/52b472f5f9b73df2368119c5f3fce6f6 to your computer and use it in GitHub Desktop.
Download ZIP
Lab13, Lab14, Lab15
Raw
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");
}
Raw
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");
}
Raw
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");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment