Напишите программу на C, которая считывает целые числа из сопровождающего файла данных и использует сортировку вставками для сохранения отсортированных данных в массиве.

Question

Напишите программу на C, которая реализует простую сортировку на основе массива. Ваша программа должна прочитать целые числа из сопровождающего файла данных и использовать сортировку вставкой для сохранения отсортированных данных в массиве. Если вы должны вставить элемент между двумя существующими значениями, то вы также должны переместить (или сдвинуть) элементы на все элементы с индексом>= индексом, в который вы хотите вставить новый элемент. Обратите внимание, что вы можете найти алгоритм вставки сортировки в учебнике и слайдах.

Это целые числа из текстового файла. Вставки расположены друг под другом, а не так, как они показаны здесь: 879 646 80 385 741 57 370 240 111 400 262 678 951 506 720 508 792 863 677 864 70 5 591 440 989 478 867 636 278 827 692 243 806 676 158 550 425 226 783 129 876 714 125 721 164 555 730 146 596 947 174 837 48 589 808 868 694 677 379 62 580 165 956 139 215 14 45 552 98 154 702 661 997 825 363 782 229 915 281 397 295 219 231 476 253 22 873 504 653 698 772 184 453 508 977 863 624 947 104 926

Этот код у меня сейчас. Я получаю адреса в порядке, но теперь целые числа из файла. Когда я закомментирую функцию inserttionSort, числа печатаются нормально, но, очевидно, не в порядке. Что я делаю неправильно?

#include <stdio.h>
#include<stdio.h>

void insertionSort(int *, int);

int main()
{
    int i,num,array[1000];

    FILE *fp = fopen("data_a5.txt","r");

    fscanf(fp,"%d",&num); 

    if(fp== NULL)
    {
        printf("Error reading File!\n");
        return;
    }  

    while(!feof(fp))
    { 
        fscanf(fp,"%d", &array[num]);
        //printf("%d\n", array[num]);
    }

    insertionSort(array,num);

    for(i=0;i<num;i++)
        printf("%d\n",&array[i]);

    fclose(fp);

    return 0;
}

void insertionSort(int *value, int size)
{
    int i,j,temp;

    for(i = 0; i <= size; i++)
    {
        for(j = i; j >= 0; j--)
        {
            if(value[j+1]<value[j])
            {
                temp=value[j+1];
                value[j+1]=value[j];
                value[j]=temp;
            }
            else
                break;
        }
    }
}

Answer 1

Если ваша задача состоит в том, чтобы сортировать массив при вставке элементов (т. Е. "Вживую"), лучше всего использовать связанные структуры.

Например:

struct myinst
{
  int mynum;
  struct myinst *prev;
  struct myinst *next;
};

Есть много примеров, вот один: http://www.tutorialspoint.com/data_structures_algorithms/linked_list_program_in_c.htm

Когда вы вставляете новый элемент для сортировки массива / связанного списка, вы просматриваете связанный список и находите элемент, ближайший к новому, а затем выполняете вставку, создавая новую память, изменяя прежние / следующие адреса в существующих элементах, так что они указывают на новый предмет.