Выполнить сортировку данных с помощью метода вставки с убывающим шагом - C (СИ)
Формулировка задачи:
Пусть даны три файла вещественных чисел, состоящих из 100, 1000 и 10000 чисел. Выполнить сортировку данных с помощью метода вставки с убывающим шагом. Определить количество операций сравнения для каждого из трёх файлов. Оценить эффективность метода, используя разные последовательности шагов.
Решение задачи: «Выполнить сортировку данных с помощью метода вставки с убывающим шагом»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> //----------------------------------------------------------------------------- size_t ShellSort(float array[], size_t size) { int i, j, x; size_t count = 0; size_t step = size / 2; for (; step; step /= 2) { for (i = step; i < size; ++i) { x = array[i]; for (j = i - step; (x < array[j]) && (j >= 0); j -= step) { array[j + step] = array[j]; count++; } array[j + step] = x; count++; } } return count; } //----------------------------------------------------------------------------- size_t Load(FILE* f, float array[], size_t size) { size_t i; rewind(f); for (i = 0; (i < size) && (fscanf(f, "%f", &array[i]) == 1); ++i) { ; } return i; } //----------------------------------------------------------------------------- void Print(float array[], size_t size) { size_t i; for (i = 0; i < size; ++i) { printf("%.2f ", array[i]); } printf("\n"); } //----------------------------------------------------------------------------- int Exec(FILE* f, float array[], size_t length) { size_t size = Load(f, array, length); printf("%u elements, %u comparisons:\n", size, ShellSort(array, size)); Print(array, size); return size == length; } //----------------------------------------------------------------------------- int main(int argc, char* argv[]) { float array[10000]; FILE* f; if (argc != 2) { fprintf(stderr, "Usage: %s <FILE>\n", argv[0]); return EXIT_FAILURE; } if ((f = fopen(argv[1], "r")) == NULL) { perror(argv[1]); return EXIT_FAILURE; } if (Exec(f, array, 100) == 0) { return EXIT_FAILURE; } if (Exec(f, array, 1000) == 0) { return EXIT_FAILURE; } if (Exec(f, array, 10000) == 0) { return EXIT_FAILURE; } fclose(f); return EXIT_SUCCESS; }
Объяснение кода листинга программы
- В функции ShellSort происходит сортировка массива методом вставки с убывающим шагом.
- В функции Load считываются числа из файла в массив до тех пор, пока не будет достигнут конец файла или не будет заполнено определенное количество элементов.
- В функции Print элементы массива выводятся на экран через пробел.
- В функции Exec происходит чтение данных из файла, сортировка и вывод на экран, а также проверяется, были ли прочитаны все элементы.
- В функции main создается массив и открывается файл для чтения.
- Если файл не открыт, то выводится сообщение об ошибке и программа завершается.
- Если файл открыт, то происходит попытка считать данные и выполнить сортировку с разным размером массива.
- Если сортировка не удалась, то выводится сообщение об ошибке и программа завершается.
- Если все проверки пройдены успешно, то файл закрывается и программа завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д