Объединить структуру сортировки по фамилии с ошибкой сегментации

Question

Я пытаюсь отсортировать массив структур по фамилии, если это та же фамилия, то по имени.

struct Person {
    std::string kNum;
    std::string last;
    std::string first;
    int zipCode;
};

Это функции для сортировки слиянием.

void nameSort(Person* array, int size) {
    int high = size - 1;
    mergeSort(array, 0, high);
}

void mergeSort(Person* arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - 1) / 2;

        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);

        merge(arr, low, mid, high);
    }
}

void merge(Person* arr, int low, int mid, int high) {
    Person *temp = new Person[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k =0;

    while (i <= mid && j <= high) {
        if (arr[i].last != arr[j].last) {
            if (arr[i].last <= arr[j].last) {
                temp[k++] = arr[j++];
            } else {
                temp[k++] = arr[i++];
            }
        } else {
            if (arr[i].first <= arr[j].last) {
                temp[k++] = arr[j++];
            } else {
                temp[k++] = arr[i++];
            }
        }
    }

    while (i < mid) {
        temp[k++] = arr[i++];
    }
    while(j <= high) {
        temp[k++] = arr[j++];
    }

    for (int x = low; x < high; ++x) {
        arr[x] = temp[x];
    }


    delete [] temp;
}

На консоли просто выходы. Я запустил его на DrMemory и выдает ошибку сегментации. Я пытался найти, где он вышел за пределы, но не могу его найти.

Answer 1

Наличие

 void mergeSort(Person* arr, int low, int high) {
   if (low < high) {
       int mid = low + (high - 1) / 2;

       mergeSort(arr, low, mid);

у вас возникла первая проблема с mid , например, если low равно 2 и high равно 3, тогда mid значения 3 и Вы снова вызываете mergeSort с низким равным 2 и высоким равным 3 для взрыва стека.

Видимо, поскольку его название означает, mid должен быть средним индексом между low и high , поэтому

int mid = (low + high) / 2;

Другие проблемы в объединить

делает

 while (i < mid) {
   temp[k++] = arr[i++];
 }

вы упускаете звание элемента mid , должно быть

while (i <= mid) {
    temp[k++] = arr[i++];
}

делает

for (int x = low; x < high; ++x) {
    arr[x] = temp[x];
}

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

for (i = low, k = 0; i <= high; ++i, ++k)
  arr[i] = temp[k];

После этих изменений ваша программа хорошо сортирует элементы

---

#include <string>
#include <iostream>

struct Person {
    std::string kNum;
    std::string last;
    std::string first;
    int zipCode;
};

void merge(Person* arr, int low, int mid, int high) {
    Person *temp = new Person[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k =0;

    while (i <= mid && j <= high) {
        if (arr[i].last != arr[j].last) {
            if (arr[i].last <= arr[j].last) {
                temp[k++] = arr[j++];
            } else {
                temp[k++] = arr[i++];
            }
        } else {
            if (arr[i].first <= arr[j].last) {
                temp[k++] = arr[j++];
            } else {
                temp[k++] = arr[i++];
            }
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while(j <= high) {
        temp[k++] = arr[j++];
    }

    for (i = low, k = 0; i <= high; ++i, ++k)
      arr[i] = temp[k];


    delete [] temp;
}

void mergeSort(Person* arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2; // mid

        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);

        merge(arr, low, mid, high);
    }
}

void nameSort(Person* array, int size) {
    int high = size - 1;
    mergeSort(array, 0, high);
}

int main()
{
  Person a[] = {
    { "K1000001","Thompson","Loyal",97894 },
    { "K1000002","Abbott","Ward",97095 },
    { "K1000003","Hauck","Mario",97587 },
    { "K1000004","Mertz","Bret",97070 },
    { "K1000005","Jacobs","Hubert",97364 },
    { "K1000006","Rolfson","Dixie",97335 },
    { "K1000007","Weber","Yoshiko",97091 },
    { "K1000008","Beier","Jessika",97858 },
    { "K1000009","White","Sophie",97719 },
    { "K1000010","Dibbert","Jordyn",97607 },
    { "K1000011","Schultz","Markus",97515 },
    { "K1000012","Kemmer","Bonnie",97264 },
    { "K1000013","Klein","Llewellyn",97699 },
    { "K1000014","Barton","Callie",97276 },
    { "K1000015","Bartell","Erich",97884 },
    { "K1000016","Marks","Annabel",97493 },
    { "K1000017","Hirthe","Mekhi",97487 },
    { "K1000018","Gleichner","Zita",97073 },
  };
  const int sz = sizeof(a)/sizeof(a[0]);

  for (int i = 0; i != sz; ++i)
    std::cout << a[i].last << ' ' << a[i].first << ' ' << a[i].kNum << ' ' << a[i].zipCode << std::endl;

  std::cout << "---------" << std::endl;

  nameSort(a, sz);

  for (int i = 0; i != sz; ++i)
    std::cout << a[i].last << ' ' << a[i].first << ' ' << a[i].kNum << ' ' << a[i].zipCode << std::endl;
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ g++ -g -pedantic -Wextra -Wall s.cc
pi@raspberrypi:/tmp $ ./a.out
Thompson Loyal K1000001 97894
Abbott Ward K1000002 97095
Hauck Mario K1000003 97587
Mertz Bret K1000004 97070
Jacobs Hubert K1000005 97364
Rolfson Dixie K1000006 97335
Weber Yoshiko K1000007 97091
Beier Jessika K1000008 97858
White Sophie K1000009 97719
Dibbert Jordyn K1000010 97607
Schultz Markus K1000011 97515
Kemmer Bonnie K1000012 97264
Klein Llewellyn K1000013 97699
Barton Callie K1000014 97276
Bartell Erich K1000015 97884
Marks Annabel K1000016 97493
Hirthe Mekhi K1000017 97487
Gleichner Zita K1000018 97073
---------
White Sophie K1000009 97719
Weber Yoshiko K1000007 97091
Thompson Loyal K1000001 97894
Schultz Markus K1000011 97515
Rolfson Dixie K1000006 97335
Mertz Bret K1000004 97070
Marks Annabel K1000016 97493
Klein Llewellyn K1000013 97699
Kemmer Bonnie K1000012 97264
Jacobs Hubert K1000005 97364
Hirthe Mekhi K1000017 97487
Hauck Mario K1000003 97587
Gleichner Zita K1000018 97073
Dibbert Jordyn K1000010 97607
Beier Jessika K1000008 97858
Barton Callie K1000014 97276
Bartell Erich K1000015 97884
Abbott Ward K1000002 97095