13
Май
2018

Одновременная сортировка слиянием массива чисел и строк

Нужно отсортировать массив городов по количеству людей в нём проживающих при помощи сортировки слиянием. Программа выдаёт ошибку сегментации, при помощи GDB узнал, что в результате выполнения цикла While возникает переполнение массива temp_b. Помогите исправить ошибку в коде. Заранее благодарю за Ваше время.

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

//Размер массива
#define size 9

/*cityName - массив указателей на константные строки.
В нём можно менять местами указатели, но сами строки изменять нельзя.*/ 
char *cityName[size] = {"Moscow","New-York","London","Minsk","Kiev","Warsaw","Berlin","Tokio","Hong-Kong"};
int urbanPopulation[size] = {12330126, 8400000, 8500000, 1836808, 2893000, 1700536, 3950887, 13370198, 7071576};

void arrayCity(int *array1, char **array2);
void swapArray(int *array1, char **array2);

int main (void) {
  arrayCity(urbanPopulation, cityName);
  swapArray(urbanPopulation, cityName);
  for (int i = 0; i < size; i++)
    printf("In %-10s %s %-9d peoples\n", cityName[i],"lives", urbanPopulation[i]);
  return 0;
}

void arrayCity(int *array1, char **array2) {
  printf("\r\n[-]Unsorted Urban Population:\r\n");
  printf("=====================================\r\n");
  for (int i = 0; i < size; i++)
    printf("In %-10s %s %-9d peoples\r\n", array2[i], "lives", array1[i]);
}
void swapArray(int *array1, char **array2) {
  printf("\r\n\r\n[+] Sorted Urban Population:\r\n");
  printf("=====================================\r\n");
  int mid = size / 2; // находим середину массива
  if (size % 2 == 1)
    mid++;
  int h = 1;   // шаг
  int i = 0;   // индекс первого пути
  int j = mid; // индекс второго пути
  int k = 0;   // индекс элемента в результирующей последовательности
  int *temp_a = (int *) malloc(size * sizeof(int)); // выделение памяти
  char **temp_b = (char **) malloc(size * sizeof(char));
  int step;
  while(h < size) {
    step = h;
    while (step <= mid) {
      while ((i < step) && (j < size) && (j < (mid + step))) {
        /*пока не дошли до конца пути
        заполняем следующий элемент формируемой последовательности
        меньшим из двух просматриваемых*/
        if (array1[i] < array1[j]) {
          temp_a[k] = array1[i];
          temp_b[k] = array2[i];
          i++; k++;
        }
        else {
          temp_a[k] = array1[j];
          temp_b[k] = array2[j];
          i++; k++;
        }
      }
      while(i < step) { // переписываем оставшиеся элементы первого пути (если второй кончился раньше)
        temp_a[k] = array1[i];
        temp_b[k] = array2[i];
        i++; k++;
      }
      while((j < (mid + step)) && (j < size)) {  // переписываем оставшиеся элементы второго пути (если первый кончился раньше)
        temp_a[k] = array1[j];
        temp_b[k] = array2[j];
        i++; k++;
      }
      step = step + h; // переходим к следующему этапу
    }
    h *= 2;
    // Переносим упорядоченную последовательность (промежуточный вариант) в исходный массив
    for(i = 0; i < size; i++) {
      array1[i] = temp_a[i];
      array2[i] = temp_b[i];
    }
  }
}

Источник: https://ru.stackoverflow.com/questions/827360/%D0%9E%D0%B4%D0%BD%D0%BE%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0-%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC-%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2%D0%B0-%D1%87%D0%B8%D1%81%D0%B5%D0%BB-%D0%B8-%D1%81%D1%82%D1%80%D0%BE%D0%BA

Тебе может это понравится...

Добавить комментарий