Битшифинг элементов в массиве
У меня есть задание, в котором я должен прочитать список из 4000 имен из текстового файла и затем отсортировать их в массив стилей C, когда они читаются (вместо того, чтобы читать их все, а затем сортировать). Поскольку это будет включать в себя множество элементов, меняющих индексы, можно ли будет использовать сдвиг битов для перегруппировки большого количества элементов одновременно? Например,
- объявить массив на основе кучи размером 20
- переменная место х индекс 10
- выполнить битовое смещение по индексу 9 с размером типа данных массива, чтобы х теперь находился в индексе 11
Кроме того, если у вас есть какие-либо советы по этой задаче в целом, я буду благодарен.
Решение
Нет, это совсем не похоже на то, для чего вы использовали бы сдвиг битов.
У вас будут отдельные элементы (имена), хранящиеся в массиве, и вам нужно изменить порядок всех элементов. Это не то, для чего используется битовое смещение; он используется для перемещения битов в одном целом числе влево или вправо.
Вы должны просто учиться qsort(),
Не уверен насчет требования «сортировать как они читаются», но самое простое решение — просто позвонить qsort() по мере добавления каждого имени. Если это не разрешено или считается слишком дорогим, подумайте о том, как выполнить «сортированную вставку» для массива.
Кстати, типичным подходом в C будет работать с массивом указателей на строки, а не с массивом реальных строк. Это хорошо, так как сортировать массив указателей намного проще.
Итак, вы должны иметь:
char *names[4000];
вместо
char names[4000][64 /* or whatever */];
Это потребует от вас динамического выделения места для каждого имени по мере его загрузки, хотя это не так сложно. Особенно, если у вас есть strdup(), 🙂
Другие решения
Если использование qsort () недопустимо (это было бы довольно глупо после каждой вставки), вы можете написать собственную сортировку вставки. Это не совсем эффективный способ сортировки больших массивов, но я полагаю, это то, чего ожидает ваш учитель.
detector