Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- sort.h:
- #pragma once
- int* create_hand(int* A, int N); // ручной ввод
- int* create_rand(int* A, int N); // случайный ввод
- int* create_file(int* A, int* N); // ввод из файла
- int bubble(int* A, int N); // метод пузырька
- int simple_selection(int* A, int N); // метод простого выбора
- int* sort(int* A, int N); // выбор метода сортировки
- int partition(int arr[], int low, int high, int& c, int& m); // метод пирамидной осртировки
- void quickSort(int arr[], int low, int high, int& c, int& m);// метод пирамидной осртировки
- void print(int* A, int N);
- lib_sort.cpp:
- #include <malloc.h>
- #include <algorithm>
- #include <iostream>
- #include "sort.h"
- #define _CRT_SECURE_NO_WARNINGS
- using namespace std;
- int* create_hand(int* A, int N)
- {
- A = (int*)malloc(N * sizeof(int));
- for (int i = 0; i < N; i++)
- cin >> A[i];
- return A;
- }
- int* create_rand(int* A, int N)
- {
- A = (int*)malloc(N * sizeof(int));
- for (int i = 0; i < N; ++i)
- A[i] = rand() % 100;
- return A;
- }
- int* create_file(int* A, int* N)
- {
- *N = 0; // для подсчета кол-ва символов в массиве
- int t = 0;
- char name[20];
- cout << "\nEnter a name file: ";
- cin >> name;
- *N = 0;
- int mas = 0;
- FILE* f;
- errno_t err;
- err = fopen_s(&f, name, "r"); // открытие файла для чтения
- if (err) // проверка открытия файла
- {
- cout << "Error openning file!" << endl;
- A = NULL;
- }
- else {
- for (int i = 0; !feof(f); i++)
- {
- fscanf_s(f, "%d", &mas); // считываем массив с файла и считаем кол-во символов
- *N = *N + 1;
- }
- A = (int*)malloc(*N * sizeof(int));
- rewind(f); // переход на начало файла
- for (int i = 0; !feof(f); i++)
- {
- fscanf_s(f, "%d", &mas); // считываем массив из файла и записываем в массив A
- A[i] = mas;
- }
- fclose(f); // закрытие файла
- }
- return A;
- }
- int bubble(int* A, int N)
- {
- cout << "\nThe method of bubble sort!\n" << endl;
- int t, c = 0, m = 0;// c - кол-во сравнений, m - кол-во пересылок
- for (int i = 0; i < N - 1; i++) {
- for (int j = 0; j < N - i - 1; j++) {
- c++;// подсчет сравнений
- if (A[j] > A[j + 1]) {
- m++; // подсчет пересылок;
- t = A[j];
- A[j] = A[j + 1];
- A[j + 1] = t;
- }
- }
- }
- cout << "Number of comparisons C = " << c << "\nNumber of transfers M = " << m << endl;
- return c + m;
- }
- int simple_selection(int* A, int N)
- {
- cout << "\nSimple selection method! " << endl;
- int t, min, c = 0, m = 0;
- for (int i = 0; i < N; i++) {
- min = i;
- for (int j = i + 1; j < N; j++) {
- c++;
- if (A[j] < A[min])
- min = j; // индекс минимального символа
- }
- m++;
- t = A[i]; //меняем местами
- A[i] = A[min];
- A[min] = t;
- }
- cout << "Number of comparisons C = " << c << "\nNumber of transfers M = " << m << endl;
- return c + m;
- }
- int* sort(int* A, int N)
- {
- int c, L = 0;// L - трудоемкость (с+m)
- cout << "\nSelect the sorting method:\n\t1)Bubble selection method;\n\t2)The heapsort algorithm;\n\t3)Simple selection method;\n\t4)Output\nYour select: ";
- cin >> c;
- if (c == 1)
- {
- L = bubble(A, N);
- cout << "\nYour sorted array: ";
- print(A, N);
- cout << "\nThe complexity of the bubble sorting method = " << L << endl;
- }
- if (c == 2)
- {
- int C = 0, M = 0;
- quickSort(A, 0, N - 1, C, M);
- cout << "\nYour sorted array: ";
- print(A, N);
- cout << "Number of comparisons C = " << C << "\nNumber of transfers M = " << M << endl;
- cout << "\nThe complexity of the Hoara sorting method = " << C + M << endl;
- }
- if (c == 3)
- {
- L = simple_selection(A, N);
- cout << "\nYour sorted array: ";
- print(A, N);
- cout << "\nThe complexity of the simple selection sorting method = " << L << endl;
- }
- if (c == 4)
- c = 0;
- cout << endl;
- return A;
- }
- void print(int* A, int N)
- {
- for (int i = 0; i < N; i++)
- cout << A[i] << " ";
- cout << endl;
- }
- int partition(int arr[], int low, int high, int& c, int& m)
- {
- int pivot = arr[high]; // pivot
- int i = (low - 1); // Index of smaller element
- for (int j = low; j <= high - 1; j++)
- {
- // If current element is smaller than or
- // equal to pivot
- c++;
- if (arr[j] <= pivot)
- {
- i++; // increment index of smaller element
- m++;
- swap(arr[i], arr[j]);
- }
- }
- m++;
- swap(arr[i + 1], arr[high]);
- return (i + 1);
- }
- /* The main function that implements QuickSort
- arr[] --> Array to be sorted,
- low --> Starting index,
- high --> Ending index */
- void quickSort(int arr[], int low, int high, int& c, int& m)
- {
- c++;
- if (low < high)
- {
- /* pi is partitioning index, arr[p] is now
- at right place */
- int pi = partition(arr, low, high, c, m);
- // Separately sort elements before
- // partition and after partition
- quickSort(arr, low, pi - 1, c, m);
- quickSort(arr, pi + 1, high, c, m);
- }
- }
- lab_17.cpp:
- #include <malloc.h>
- #include <algorithm>
- #include <iostream>
- #include "sort.h"
- #define _CRT_SECURE_NO_WARNINGS
- using namespace std;
- int main()
- {
- int n=0, c = 1; // Размер массива
- int* a = NULL; // массив чисел
- while (c != 0)
- {
- cout << "Select the method for filling in the array:\n\t1)Enter the array manually;\n\t2)Array of random numbers;\n\t3)Array from the file;\n\t4)End\nYour select: ";
- cin >> c;
- if (c == 1)
- {
- cout << "\nEnter the size of the array: ";
- cin >> n;
- cout << "Enter your array: ";
- a = create_hand(a,n);
- a = sort(a,n);
- }
- if (c == 2)
- {
- cout << "\nEnter the size of the array: ";
- cin >> n;
- a = create_rand(a,n);
- cout << "Your array: ";
- print(a,n);
- a = sort(a,n);
- }
- if (c == 3)
- {
- a = create_file(a,&n);
- if (a != NULL)
- {
- cout << "Your array: ";
- print(a,n);
- a = sort(a,n);
- }
- }
- if (c == 4)
- c = 0;
- cout << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment