Блог

У меня есть массив чисел a[n] , и я хочу отсортировать его очень быстро , но я хочу сохранить исходные позиции. поэтому я думаю , что мне следует использовать 2D-массив a[2][n] , как a[0][n] для начальных позиций, так и a[1][n] для значений. поэтому я хочу отсортировать этот массив на основе второй строки. например, мой массив является

 a[2][5] = [{ 0, 1, 2, 3, 4 }, { 10, 30, 40, 20, 50 }];  

и после сортировки я хочу

 a[2][5] = [{ 0, 3, 1, 2, 4 }, { 10, 20, 30, 40, 50 }];  

Я попытался изменить сортировку слиянием, чтобы она сортировала первую строку на основе второй строки (а также сортировала вторую строку), но в строке 14 есть ошибка сегментации, вот мой код

 #include lt;stdio.hgt; #include lt;stdlib.hgt;  void merge(int arr[][201], int l, int m, int r) {  int i, j, k;  int n1 = m - l   1;  int n2 = r - m;   /* create temp arrays */  int L[2][n1], R[2][n2];   /* Copy data to temp arrays L[] and R[] */  for (i = 0; i lt; n1; i  )  L[1][i] = arr[1][l   i];  L[0][i] = arr[0][l   i];  for (j = 0; j lt; n2; j  )  R[1][j] = arr[1][m   1   j];  R[0][j] = arr[0][m   1   j];   /* Merge the temp arrays back into arr[l..r]*/  i = 0; // Initial index of first subarray  j = 0; // Initial index of second subarray  k = l; // Initial index of merged subarray  while (i lt; n1 amp;amp; j lt; n2) {  if (L[1][i] lt;= R[1][j]) {  arr[1][k] = L[1][i];  arr[0][k] = L[0][i];  i  ;  } else {  arr[1][k] = R[1][j];  arr[0][k] = R[0][j];  j  ;  }  k  ;  }   /* Copy the remaining elements of L[], if there  are any */  while (i lt; n1) {  arr[0][k] = L[0][i];  arr[1][k] = L[1][i];  i  ;  k  ;  }   /* Copy the remaining elements of R[], if there  are any */  while (j lt; n2) {  arr[1][k] = R[1][j];  arr[0][k] = R[0][j];  j  ;  k  ;  } }  /* l is for left index and r is right index of the sub-array of arr to be sorted */ void mergeSort(int arr[][201], int l, int r) {  if (l lt; r) {  // Same as (l r)/2, but avoids overflow for  // large l and h  int m = l   (r - l) / 2;   // Sort first and second halves  mergeSort(arr, l, m);  mergeSort(arr, m   1, r);   merge(arr, l, m, r);  } }  void get_array(int length, int array[]) {  for (int i = 0; i lt; length; i  ) {  scanf("%d", amp;array[i]);  } }  int main() {  int n;  scanf("%d", amp;n);   int packages[2][n];    for (int i = 0; i lt; n; i  ) {  packages[0][i]= i;  }  get_array(n, packages[1]);  mergeSort(packages, 0, n);   return 0; }  

Я просто хочу решить эту проблему, я не против использовать другую функцию.

Циклы инициализации для массивов L и R неверны: вы должны использовать {} для группировки нескольких операторов в виде блока в C. В отличие от Python, отступ не определяет структуру:

 for (i = 0; i lt; n1; i  ) {  L[1][i] = arr[1][l   i];  L[0][i] = arr[0][l   i]; } for (j = 0; j lt; n2; j  ) {  R[1][j] = arr[1][m   1   j];  R[0][j] = arr[0][m   1   j]; }  

Кроме того, ваша функция сортировки ожидает 2D-массив с фиксированным количеством столбцов 201 , поэтому вы не можете передать ему массив, выделенный main() с переменным количеством столбцов. Вы должны либо использовать фиксированный массив, int packages[2][201]; либо передавать n свои mergeSort merge функции и явно и arr последовательно.

Вы должны передать n - 1 как смещение последнего элемента в начальном вызове mergeSort() . Это соглашение подвержено ошибкам и сбивает с толку.

Обратите внимание также, что merge это можно упростить: требуется сохранить только левую часть и требуется один цикл.

Вот измененная версия:

 #include lt;stdio.hgt; #include lt;stdlib.hgt;  void merge(int n, int arr[][n], int l, int m, int r) {  int i, j, k;  int n1 = m - l;   /* create temp array */  int L[2][n1];   /* Copy data to temp array L[] */  for (i = 0; i lt; n1; i  ) {  L[1][i] = arr[1][l   i];  L[0][i] = arr[0][l   i];  }   /* Merge the temp arrays back into arr[l..r]*/  i = 0; // Initial index of first subarray  j = m; // Initial index of second subarray  k = l; // Initial index of merged subarray  while (i lt; n1) {  if (j == r || L[1][i] lt;= arr[1][j]) {  arr[1][k] = L[1][i];  arr[0][k] = L[0][i];  i  ;  } else {  arr[1][k] = arr[1][j];  arr[0][k] = arr[0][j];  j  ;  }  k  ;  } }  /* l is for left index and r is right index of the  sub-array of arr to be sorted */ void mergeSort(int n, int arr[][n], int l, int r) {  if (r - l gt; 1) {  // Same as (l r)/2, but avoids overflow for  // large l and h  int m = l   (r - l) / 2;   // Sort first and second halves  mergeSort(n, arr, l, m);  mergeSort(n, arr, m, r);  merge(n, arr, l, m, r);  } }  int main() {  int n = 0;  scanf("%d", amp;n);   int packages[2][n];   for (int i = 0; i lt; n; i  ) {  packages[0][i] = i;  packages[1][i] = 0;  scanf("%d", amp;packages[1][i]);  }  mergeSort(n, packages, 0, n);   printf("a[2][%d] = [{ ", n);  for (int i = 0; i lt; n; i  ) {  printf("%d, ", packages[0][i]);  }  printf("}, { ");  for (int i = 0; i lt; n; i  ) {  printf("%d, ", packages[1][i]);  }  printf("}];n");  return 0; }  

Выход:

 5 10 30 40 20 50 a[2][5] = [{ 0, 3, 1, 2, 4, }, { 10, 20, 30, 40, 50, }];