Untitled
unknown
plain_text
a year ago
5.5 kB
5
Indexable
Never
#include <iostream> using namespace std; void inclusion() { int size = 20; int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10}; int comparisons = 0; int permutations = 0; cout << "Массив ДО сортировки методом прямого включения:" << endl; for(int i = 0; i < size; i++) { cout << arr[i] << " "; } cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом прямого включения:" << endl; for (int i = 0; i<size; i++) { int value = arr[i]; int index = i; while ((index > 0) && (arr[index - 1] > value)) { arr[index] = arr[index - 1]; index --; permutations += 1; comparisons += 1; } arr[index] = value; comparisons += 1; } for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; cout << endl << "перестановки - " << permutations; cout << endl << "сравнения - " << comparisons << endl; } void selection() { int size = 20; int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10}; int comparisons = 0; int permutations = 0; int min, temp; // для поиска минимального элемента и для обмена cout << "Массив ДО сортировки методом прямого выбора:" << endl; for(int i = 0; i < size; i++) { cout << arr[i] << " "; } cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом прямого выбора:" << endl; for (int i = 0; i < size - 1; i++) { min = i; // запоминаем индекс текущего элемента // ищем минимальный элемент чтобы поместить на место i-ого for (int j = i + 1; j < size; j++) // для остальных элементов после i-ого { if (arr[j] < arr[min]) // если элемент меньше минимального, { min = j; // запоминаем его индекс в min comparisons += 1; } else{ comparisons += 1;} } temp = arr[i]; // меняем местами i-ый и минимальный элементы arr[i] = arr[min]; arr[min] = temp; permutations += 1; } for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; cout << endl << "перестановки - " << permutations; cout << endl << "сравнения - " << comparisons << endl; } void bubble() { int size = 20; int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10}; int comparisons = 0; int permutations = 0; cout << "Массив ДО сортировки методом пузырька:" << endl; for(int i = 0; i < size; i++) { cout << arr[i] << " "; } cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом пузырька:" << endl; // Для всех элементов for (int i = 0; i < size - 1; i++) { for (int j = (size - 1); j > i; j--) // для всех элементов после i-ого { if (arr[j - 1] > arr[j]) // если текущий элемент меньше предыдущего { int temp = arr[j - 1]; // меняем их местами arr[j - 1] = arr[j]; arr[j] = temp; permutations += 1; } comparisons += 1; } } for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; cout << endl << "перестановки - " << permutations; cout << endl << "сравнения - " << comparisons << endl; } void Shell() { int size = 20; int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10}; int comparisons = 0; int permutations = 0; int d = 4; cout << "Массив ДО сортировки методом Шелла:" << endl; for(int i = 0; i < size; i++) { cout << arr[i] << " "; } cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом Шелла:" << endl; while (d > 0) { for (int i = d; i < size; i++) { int index = i; int value = arr[i]; while ((index >=d) && (arr[index - d] > value)) { arr[index] = arr [index - d]; index = index - d; permutations += 1; comparisons += 1; } arr[index] = value; comparisons += 1; } if (d/2 != 0) d = d/2; else if (d == 1) d = 0; else break; } for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; cout << endl << "перестановки - " << permutations; cout << endl << "сравнения - " << comparisons; } int main() { inclusion(); cout << "==================================================" << endl; selection(); cout << "==================================================" << endl; bubble(); cout << "==================================================" << endl; Shell(); return 0; }