Выполнить сортировку данных с помощью метода вставки с убывающим шагом - 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;
}

Объяснение кода листинга программы

  1. В функции ShellSort происходит сортировка массива методом вставки с убывающим шагом.
  2. В функции Load считываются числа из файла в массив до тех пор, пока не будет достигнут конец файла или не будет заполнено определенное количество элементов.
  3. В функции Print элементы массива выводятся на экран через пробел.
  4. В функции Exec происходит чтение данных из файла, сортировка и вывод на экран, а также проверяется, были ли прочитаны все элементы.
  5. В функции main создается массив и открывается файл для чтения.
  6. Если файл не открыт, то выводится сообщение об ошибке и программа завершается.
  7. Если файл открыт, то происходит попытка считать данные и выполнить сортировку с разным размером массива.
  8. Если сортировка не удалась, то выводится сообщение об ошибке и программа завершается.
  9. Если все проверки пройдены успешно, то файл закрывается и программа завершается.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

6   голосов , оценка 4 из 5
Похожие ответы