Sorting an array of structures alphabetically (Merge sort)

Question

The file contains several records of structures in which there is a field with a surname ( char sname[50] ). The data from the file is transferred to the array, sorting is performed by name in alphabetical order. What condition should be put in brackets ("Condition") for the array to be sorted? or is it necessary to call a function in that place?

 #include "stdafx.h" #include<iostream> #include<cstring> using namespace std; struct contact { char nomer[50]; char adress[50]; char sname[50]; }; int base_output(contact *buf, int kol_el) { cout << "Полный список контактов базы данных\n"; cout << "-----------------------------------------------------------\n"; for (int i = 0; i < kol_el; i++) { cout << (i + 1) << ".) " << buf[i].sname; cout << "\n" << buf[i].nomer; cout << "\n" << buf[i].adress; cout << "\n\n"; } cout << "-----------------------------------------------------------\n"; system("pause"); return 0; } void Merge(contact *buf, int first, int last) { int middle, start, final, j; contact *mas = new contact[100]; middle = (first + last) / 2; start = first; final = middle + 1; for (j = first; j <= last; j++) if ((start <= middle) && ((final > last) || ("условие"))) //замена условия { mas[j] = buf[start]; start++; } else { mas[j] = buf[final]; final++; } for (j = first; j <= last; j++) buf[j] = mas[j]; delete[]mas; } void MergeSort(contact *buf, int first, int last) { if (first<last) { MergeSort(buf, first, (first + last) / 2); MergeSort(buf, (first + last) / 2 + 1, last); Merge(buf, first, last); } } int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "RUS"); FILE *f; f = fopen("telbook.dat", "r+b"); fseek(f, 0, SEEK_END); int size = ftell(f); int kol_el = size / sizeof(contact); contact *buf = new contact[kol_el]; fseek(f, 0, SEEK_SET); fread(buf, sizeof(contact), kol_el, f); fclose(f); int first = 0; int last = kol_el; unsigned int rezh = 0; do { system("cls"); const int NotUsed = system("color 03"); cout << "Выберите действие:\n"; cout << "1.Показать базу контактов.\n"; cout << "2.Сортировка по алфавиту.(слиянием)\n"; cout << "3.Выйти из программы.\n"; cin >> rezh; switch (rezh) { case 1: { base_output(buf,kol_el); break; } case 2: { MergeSort(buf, first, last); break; } } } while (rezh != 3); system("cls"); system("pause"); return 0; }

 #include "stdafx.h" #include<iostream> #include<cstring> #include<cstdlib> using namespace std; struct contact { char nomer[50]; char adress[50]; char sname[50]; }; int base_output(contact *buf, int kol_el) { cout << "Полный список контактов базы данных\n"; cout << "-----------------------------------------------------------\n"; for (int i = 0; i < kol_el; i++) { cout << (i + 1) << ".) " << buf[i].sname; cout << "\n" << buf[i].nomer; cout << "\n" << buf[i].adress; cout << "\n\n"; } cout << "-----------------------------------------------------------\n"; system("pause"); return 0; } void Merge(contact *buf, int first, int last) { int middle, start, final, j; contact *mas = new contact[100]; middle = (first + last) / 2; start = first; final = middle + 1; for ( j = first; j < last; j++) //j<=last if ((start < middle) && ((final > last) || (strcmp(buf[start].sname,buf[final].sname)<0))) //start <= middle { mas[j] = buf[start]; start++; } else { mas[j] = buf[final]; final++; } for ( j = first; j < last; j++) //j<=last buf[j] = mas[j]; delete[]mas; } void MergeSort(contact *buf, int first, int last) { if (first<last) { MergeSort(buf, first, (first + last) / 2); MergeSort(buf, (first + last) / 2 + 1, last); Merge(buf, first, last); } } int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "RUS"); FILE *f; f = fopen("telbook.dat", "r+b"); fseek(f, 0, SEEK_END); int size = ftell(f); int kol_el = size / sizeof(contact); contact *buf = new contact[kol_el]; fseek(f, 0, SEEK_SET); fread(buf, sizeof(contact), kol_el, f); fclose(f); int first = 0; int last = kol_el; unsigned int rezh = 0; do{ system("cls"); const int NotUsed = system("color 03"); cout << "Выберите действие:\n"; cout << "1.Показать базу контактов.\n"; cout << "2.Сортировка по алфавиту.(слиянием)\n"; cout << "3.Выйти из программы.\n"; cin >> rezh; switch (rezh) { case 1: { base_output(buf,kol_el); break; } case 2: { MergeSort(buf, first, last); break; } } } while (rezh != 3); system("cls"); system("pause"); return 0; }

Accepted Answer · 2016-04-27T03:25:08

A condition is a comparison between buf[start] and buf[final] - it depends on how you compare ... For example, if it is sname , then something like strcmp(buf[start].sname,buf[final].sname) < 0 .

Only you still will not work, if only because you are confused with the boundaries. See, you pass two indices into your functions and work with them inclusively . But in the very first call, first is 0, and last is the number of elements, i.e. pre-program out of the array. It is better to use half-open intervals - believe me, this is more convenient - i.e. The last parameter indicates the last element. Then the main call to main correct, but the functions themselves must be rewritten.

Update

Here’s how I would MergeSort function:

 void MergeSort(contact* buf, int first, int last) { if (first >= last-1) return; int mid = (first+last)/2; MergeSort(buf,first,mid); MergeSort(buf,mid,last); contact * mas = new contact[last - first]; for(int i = first; i < last; ++i) mas[i-first] = buf[i]; int l = 0, r = mid - first; for(int i = first; i < last; ++i) { if (l == mid-first) buf[i] = mas[r++]; else if (r == last-first) buf[i] = mas[l++]; else if (strcmp(mas[l].sname,mas[r].sname) < 0) buf[i] = mas[l++]; else buf[i] = mas[r++]; } delete[] mas; }

Thanks for the answer, as I understood, going beyond the array only in a loop?
I fixed these places, here's the code, the options before the fix are commented out.
Now after sorting, some elements are clogged with arbitrary characters, some are duplicated, although all the others are ordered correctly.
Well, I did not see the corrected code, so where did I know from? ..
Corrected code at the top right under the original code, in a separate window
Sorry, there is not much time to fix your code :( I quickly sketched my own - vpaste.net/macfc - I hope you figure out how it works. Left and right parts are sorted, all this is copied into the auxiliary array, and from it merges into the original array l and r - indices of the current elements of the left and right parts, which are compared (if both parts are not completed) or simply transferred without comparison, if one part has already been completed. Check ...

Sorting an array of structures alphabetically (Merge sort)

1 answer 1

More articles: