0

Программа должна выполнить сортировку слиянием массива городов по массиву чисел(людей в нём проживающих). Проблема с алгоритмом сортировки слиянием. Прошу помочь исправить ошибку в коде.

Результат выполнения программы:

введите сюда описание изображения

#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 = malloc(size * sizeof *temp_a); // выделение памяти
  char **temp_b = malloc(size * sizeof *temp_b);
  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];
          j++; 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];
        j++; k++;
      }
      step = step + h; // переходим к следующему этапу
    }
    h *= 2;
    // Переносим упорядоченную последовательность (промежуточный вариант) в исходный массив
    for(i = 0; i < size; i++) {
      array1[i] = temp_a[i];
      array2[i] = temp_b[i];
    }
  }
}

2 ответа 2

1

В ветке else первого if идет копирование из индекса j, а инкремент почему-то для i.

Далее - код выполняет один проход-слияние, образуя 4 упорядоченных пары из элементов первой и второй половины. После этого i,j дошли до конца, и всё.

Подозреваю, что имелся в виду такой алгоритм слияния - на первом шаге сливаются элементы 0 + 1, 2 + 3 и т.д. На втором шаге - 0,1 + 2,3, 4,5 + 6,7 и т.д., пока длина сливаемых кусков не превысит длину массива.

2
  • Благодарю и вправду стало лучше, но алгоритм по прежнему не сортирует. Я использовал GDB но он ведь не выдаёт ошибки, код ведь компилируется. Проблема в логике алгоритма. Изменил результат в вопросе.
    – Frost0x
    15 мая 2018 в 15:17
  • Обновил ответ..
    – MBo
    15 мая 2018 в 16:05
0

Благодарю за помощь! Разобрался с алгоритмом и синтаксисом. Я выбрал не тот алгоритм слияния, вместо нисходящего делал двух-путевым. Выкладываю код может кому-то пригодится.

Результат:

введите сюда описание изображения

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

#define size 9

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 merge_sort(int *array1, char **array2, int l, int r);

int main(void) {
  arrayCity(urbanPopulation, cityName);
  merge_sort(urbanPopulation, cityName, 0, size - 1); // вызываем функцию сортировки
  printf("\n");
  // Выводим отсортированные массивы
  printf("\r\n\r\n[+] Sorted Urban Population:\r\n");
  printf("=====================================\r\n");
   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 merge_sort(int *array1, char **array2, int l, int r) {

  if (l == r)
    return; // границы сомкнулись массив отсортирован.
  int mid = (l + r) / 2; // определяем середину последовательности
  // и рекурсивно вызываем функцию сортировки для каждой половины

  merge_sort(array1, array2, l, mid);
  merge_sort(array1, array2, mid + 1, r);

  int i = l;  // начало первого пути
  int j = mid + 1; // начало второго пути

  int *temp_a = malloc(size * sizeof *temp_a); // дополнительный массив чисел
  char **temp_b = malloc(size * sizeof *temp_b); // дополнительный массив строк

  for(int step = 0; step < r - l + 1; step++) {
    // для всех элементов дополнительного массива
    // записываем в формируемую последовательность меньший из элементов двух путей
    // или остаток первого пути если j > r
    if ((j > r) || ((i <= mid) && (array1[i] < array1[j]))) {
      temp_a[step] = array1[i];
      temp_b[step] = array2[i];
      i++;
    }
    else {
      temp_a[step] = array1[j];
      temp_b[step] = array2[j];
      j++;
    }
  }
  // переписываем сформированную последовательность в исходный массив
  for (int step = 0; step < r - l + 1; step++) {
    array1[l + step] = temp_a[step];
    array2[l + step] = temp_b[step];
  }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.