Анализ и структура данных
Автор: Никита Циома • Октябрь 21, 2025 • Лабораторная работа • 1,486 Слов (6 Страниц) • 28 Просмотры
Задание.
Требуется считать из файла, находящегося на диске одномерный массив, состоящий из 30 произвольных целых чисел и отсортировать его в порядке убывания приведенными выше методами. На экран вывести количество операций сравнения и пересылки чисел и время выполнения программы для каждого метода.
- Программа метода выбора
#include <string>
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
const int SIZE = 30;
int input[SIZE];
int step1 = 0;
int step2 = 0;
void readData() {
string inFileName = "input.txt";
ifstream inFile;
inFile.open(inFileName.c_str());
if (inFile.is_open()) {
cout << "Входные данные: " << endl;
for (int i = 0; i < SIZE; i++) {
inFile >> input[i];
cout << input[i] << " ";
}
inFile.close(); // Close input file
}
}
int main() {
srand(time(0)); // Инициализация генератора случайных чисел
readData(); // Чтение данных из файла
int temp, check, big, index;
for (int i = 0; i < (SIZE - 1); i++) {
check = 0;
big = input[i];
for (int j = (i + 1); j < SIZE; j++) {
if (big < input[j]) {
step1++; // Увеличиваем счетчик сравнений
big = input[j];
index = j;
check = 1;
}
}
if (check == 1) {
step2++; // Увеличиваем счетчик перестановок
temp = input[i];
input[i] = big;
input[index] = temp;
}
}
cout << endl << "Результат сортировки: " << endl;
for (int i = 0; i < SIZE; i++) {
cout << input[i] << " ";
}
cout << endl << "Количество сравнений: " << step1 << endl;
cout << "Количество перестановок: " << step2 << endl;
cout << "Время работы программы = " << clock() / 1000.0 << endl;
return 0;
}
Результаты программы:
[pic 1]
- Программа для метода вставками
#include <string>
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
const int SIZE = 30;
int input[SIZE];
int step1 = 0;
int step2 = 0;
void readData() {
string fileName = "input.txt";
ifstream inFile;
inFile.open(fileName.c_str());
if (inFile.is_open()) {
cout << "Входные данные:" << endl;
for (int i = 0; i < SIZE; i++) {
inFile >> input[i];
cout << input[i] << " ";
}
inFile.close(); // Close input file
}
}
int main() {
srand(time(0));
readData();
for (int i = 0; i < (SIZE - 1); i++) {
int check = 0;
int big = input[i];
for (int j = (i + 1); j < SIZE; j++) {
if (big < input[j]) {
step1++;
big = input[j];
check++;
int index = j;
}
}
if (check != 0) {
step2++;
int temp = input[i];
input[i] = big;
input[index] = temp;
...