合并排序算法在第 117 行后停止工作

Question

对于我的“计算机科学和编程基础”，我需要用 C 编写一个合并排序程序。我必须使用某个提供的文件，其中每行包含年份和温度，用逗号分隔（例如：1850，-0.41765878） .

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


struct globalAnnual {
  int year;
  float temp;
};

void merge_sort(struct globalAnnual array[], int size);
void merge_sort_recursion(struct globalAnnual array[], int left, int right);
void merge_sorted_arrays(struct globalAnnual array[], int left, int middle, int right);

int size = 0;


int main (int argc, char* argv[]) {
  if (argc != 2) {
    printf("Error: Invalid amount of augments. Insert exactly 2.\n");
    return 1;
  }
  FILE* inputData = fopen (argv[1], "r");
  if (inputData == NULL) {
    printf("Error: Input data is empty.\n");
    return 1;
  }

  //Einscannen der Datei
  struct globalAnnual data[200];

  while (fscanf(inputData, "%d,%f", &data[size].year, &data[size].temp) == 2) {
    size++;
  }
  fclose(inputData);

    merge_sort(data, size);

    printf("\n\n10 Coldest Years:\n");
    for (int i = 0; i < 10; i++) {
      printf("Year: %d, Temp: %.8f\n", data[i].year, data[i].temp);
    }
    printf("\n\n10 Hottest Years:\n");
    for (int i = size - 10; i <= size - 1; i++) {
      printf("Year: %d, Temp: %.8f\n", data[i].year, data[i].temp);
    }

  return 0;
}


void merge_sort(struct globalAnnual array[200], int size) {
  merge_sort_recursion(array, 0, size -1);
}

void merge_sort_recursion(struct globalAnnual array[200], int left, int right) {

  if (left < right) {
    int middle = left + (right - left) / 2;

    merge_sort_recursion(array, left, middle);
    merge_sort_recursion(array, middle + 1, right);

    merge_sorted_arrays(array, left, middle, right);

  }
}


void merge_sorted_arrays(struct globalAnnual array[200], int left, int middle, int right) {
  int left_size = middle - left + 1;
  int right_size = right - middle;

  struct globalAnnual temp_left[left_size];
  struct globalAnnual temp_right[right_size];

  int i, j, k;

  for (int i = 0; i < left_size; i++) {
    temp_left[i] = array[left + i];
  }
  for (int i = 0; i < right_size; i++) {
    temp_right[i] = array[middle + 1 + i];
  }

  for (i = 0, j = 0, k = left; k <= right; k++) {
    if ((i < left_size) && (j >= right_size) || temp_left[i].temp <= temp_right[j].temp) {
      array[k] = temp_left[i];
      i++;
    } else {
      array[k] = temp_right[j];
      j++;
    }

  }

}

1850,-0.41765878
1851,-0.2333498
1852,-0.22939907
1853,-0.27035445
1854,-0.29163003
1855,-0.2969512
1856,-0.32035372
1857,-0.46723005
1858,-0.3887657
1859,-0.28119546
1860,-0.39016518
1861,-0.42927712
1862,-0.53639776
1863,-0.3443432
1864,-0.4654367
1865,-0.33258784
1866,-0.34126064
1867,-0.35696334
1868,-0.35196072
1869,-0.31657043
1870,-0.32789087
1871,-0.3685807
1872,-0.32804197
1873,-0.34133235
1874,-0.3732512
1875,-0.37562594
1876,-0.42410994
1877,-0.101108834
1878,-0.011315193
1879,-0.30363432
1880,-0.31583208
1881,-0.23224552
1882,-0.29553008
1883,-0.3464744
1884,-0.49232006
1885,-0.47112358
1886,-0.42090362
1887,-0.49878576
1888,-0.37937889
1889,-0.24989556
1890,-0.50685817
1891,-0.40131494
1892,-0.5075585
1893,-0.49461925
1894,-0.48376393
1895,-0.4487516
1896,-0.28400728
1897,-0.25980017
1898,-0.48579213
1899,-0.35543364
1900,-0.23447904
1901,-0.29342857
1902,-0.43898427
1903,-0.5333264
1904,-0.5975614
1905,-0.40775132
1906,-0.3191393
1907,-0.5041577
1908,-0.5138707
1909,-0.5357649
1910,-0.5310242
1911,-0.5392051
1912,-0.47567302
1913,-0.46715254
1914,-0.2625924
1915,-0.19184391
1916,-0.42020997
1917,-0.54301953
1918,-0.42458433
1919,-0.32551822
1920,-0.2985808
1921,-0.24067703
1922,-0.33922812
1923,-0.31793055
1924,-0.3120622
1925,-0.28242525
1926,-0.12283547
1927,-0.22940508
1928,-0.20676155
1929,-0.39275664
1930,-0.1768054
1931,-0.10339768
1932,-0.14546166
1933,-0.32234442
1934,-0.17433685
1935,-0.20605922
1936,-0.16952093
1937,-0.01919893
1938,-0.012200732
1939,-0.040797167
1940,0.07593584
1941,0.038129337
1942,0.0014060909
1943,0.0064140745
1944,0.14410514
1945,0.043088365
1946,-0.1188128
1947,-0.091205545
1948,-0.12466127
1949,-0.14380224
1950,-0.22662179
1951,-0.06115397
1952,0.015354565
1953,0.07763074
1954,-0.11675021
1955,-0.19730993
1956,-0.2631656
1957,-0.035334926
1958,-0.017632553
1959,-0.048004825
1960,-0.115487024
1961,-0.019997388
1962,-0.06405444
1963,-0.03680589
1964,-0.30586675
1965,-0.2043879
1966,-0.14888458
1967,-0.11751631
1968,-0.1686323
1969,-0.031366713
1970,-0.08510657
1971,-0.20593274
1972,-0.0938271
1973,0.04993336
1974,-0.17253734
1975,-0.11075424
1976,-0.21586166
1977,0.10308852
1978,0.0052557723
1979,0.09085813
1980,0.19607207
1981,0.25001204
1982,0.034263328
1983,0.22383861
1984,0.04800471
1985,0.04972978
1986,0.09568697
1987,0.2430264
1988,0.28215173
1989,0.17925027
1990,0.36056247
1991,0.33889654
1992,0.124896795
1993,0.16565846
1994,0.23354977
1995,0.37686616
1996,0.2766894
1997,0.4223085
1998,0.57731646
1999,0.32448497
2000,0.3310848
2001,0.48928034
2002,0.5434665
2003,0.5441702
2004,0.46737072
2005,0.60686255
2006,0.5725527
2007,0.5917013
2008,0.46564984
2009,0.5967817
2010,0.68037146
2011,0.53769773
2012,0.5776071
2013,0.6235754
2014,0.67287165
2015,0.82511437
2016,0.93292713
2017,0.84517425
2018,0.762654
2019,0.8910726
2020,0.9227938
2021,0.7618559
2022,0.80128413
2023,0.9680127

不知何故，这只对前 117 行的数据进行了正确排序，然后完全停止。我已经尝试寻找解决方案几个小时，但还无法修复它。我必须改变什么？我尝试更改数组的大小，但这没有改变任何内容。我试图找出任何问题，但我完全无能为力

Answer 1

您的程序使用

merge_sorted_arrays

= 0、

left

= 0、

middle

= 1 调用

right

。该例程将

left_size

设置为 1，将

right_size

设置为 1，并将数组

temp_left

定义为具有 1 个元素和

temp_right

有 1 个元素。因此，这些数组的最大索引为 0。在第 87 行，例程使用

temp_left[i]

，而

i

为 1，这超出了数组的范围。