WW #4

[Egor Suvorov]

Корректность на 1/10 есть, попытка засчитана.

[Шиповалов Артем]

Я понимаю что я не правильно делаю, но я не до конца понимаю как это можно исправить

[Egor Suvorov]

Кажется, пока что основная проблема — вы не обращаетесь к данным, которые лежат по указателю void *a, а просто делаете арифметику указателей.

Напишите сначала обычный merge sort для int'ов и убедитесь, что он работает.

А дальше потихоньку переписывайте на void*, можно ориентироваться на работу с указателями тут: ​https://github.com/yeputons/hse-2019-cpp/blob/master/05-191004p/02-lab/05b-print-generic.c (см. файлы с названием 04-*, 03-*).

Думаю, будет эффективнее либо в личке разобраться, либо в чатике оперативной помощи, либо завтра лично между 15 и 17.

[Шиповалов Артем]

Пока что только int, а то вдруг не успею всю доделать и оправить вовремя

[Шиповалов Артем]

Теперь работает и с char, но со string не работает, меняет только перую букву, я понимаю почему, но не понимаю как это исправить, не меняя mergeSort. Скорее всего надо отдельный компаратор для стрингов, а что делать дальше не знаю

[Egor Suvorov]

Нерекурсивный merge sort O_O. Прикольно. Но почему бы и нет :)

Рекомендации по багам в merge sort:

1. Очень странно, что у вас переменные для внутренних циклов объявлены вне цикла, который увеличивает размер блока. Например, из-за этого вы их не обнуляете.
2. В строчках 23, 28, 34, 39 вы перемещаете только первый байт. Это будет работать только с типами размера 1 (например, char). Чтобы работало с произвольными типами, надо для присваивания элемента написал цикл, который по очереди скопирует все element_size байтов. То, что у вас при этом работает со строчками — счастливое совпадение (потому что вы сейчас перемещаете младшие байты у указателей, что странное действие).
3. Напоминаю, что баллы за корректность получает только реализация, которая соответствует условию (берёт произвольный массив из argv и всё такое). Если вы хотите сделать свои тесты — без проблем, только сделайте их лучше в отдельном файле test.c, который компилируется в ./test вместо ./lab_04. А в ./lab_04 оставьте основное решение. Тогда можно будет и баллов заработать и параллельно тесты свои иметь.

По корректности:

1. В mergesort.h не хватает #include <stddef.h>, потому что там объявлен size_t, нужный для объявления my_mergesort.

По стилю:

1. Поехавшие отступы: то табы, то пробелы. Пройдитесь автоформаттером.
2. Вынесите лучше тесты в отдельные функции. Тогда не потребуется выдумывать новые имена массивам, можно будет везде назвать их data.
3. Непонятно, зачем делать if (elements % 2 == 1) mid++, должно работать и без этого.

[Egor Suvorov]

А, да, со строчками у вас происходит следующее:

1. Вы передаёте в mergesort указатель на двумерный массив d. Он размера 3 * 4 * sizeof char = 12 байт. Элемент d[0] массива d — это одна строчка, она размера 4 байта. Соответственно, mergesort пытается переставлять элементы d, то есть строчки целиком. Но он умеет переставлять только первый байт, действительно, а должен все element_size.
2. Вы вызываете компаратор, который читает первый байт из каждого char* (именно из значения указателя) и сравнивает их. То есть сортирует строчки по их адресам в памяти. Они исходно лежат последовательно => компаратор их так и должен оставить. А вообще да: компараторы для разных типов должны быть разные, в этом вся идея: сортировка одинаковая для всех типов, а вот компаратор тип знает.

Дальше у вас будут проблемы, когда строчки разного размера, причём неизвестного на этапе компиляции. Там вы не можете разумно расположить строчки разной длины в одном массиве (ну разве что куча пустого места будет). Поэтому более удобной стратегией будет положить в массив указатели на строчки и сортировать их специальным компаратором.

[Egor Suvorov]

Кажется, неуспех :(

Захотите дорешать — переоткрывайте тикет.