Сортировка алмазного массива в C

Question

У меня есть следующее домашнее задание в C. Мне в основном нужен подход, а не решение.

У нас есть массив 13 х 13. В массиве мы имеем форму алмаза, которую мы должны рассмотреть. Все вне этого алмаза инициализируется -1 (неважно). Пример 5 x 5 массив ниже

x x 1 x x 
x 2 2 2 x 
3 3 3 3 3 
x 4 4 4 x 
x x 5 x x 

x=-1 

Теперь в этом массиве значения, которые мы имеем в алмазе для каждой записи, содержат 11 бит. 5 lsb содержит одну информацию (оттенок), а другая 6 содержит другие данные (диаметр). Нам нужно сортировать данные по ряду, монотонно для оттенка, а затем по столбцу по диаметру монотонно.

Что было бы самым эффективным способом сохранения памяти? Поскольку нам нужно сохранить это, лучше всего, если записи меняются местами, а не создают другой массив. В итоге мы получим сортированный алмазный массив (все еще с -1s). Большое спасибо заранее, ребята!

Answer 1

Я не понимаю, как именно вы хотите, чтобы изменить порядок элементов

рядам, монотонно оттенок, а затем по столбцам для диаметра, монотонно

, но здесь есть некоторые идеи, которые вы могли бы использовать.

• Ваш массив равен 13x13 (169 элементов); из этого почти половина (84) пуста, поэтому вы можете использовать их как временное хранилище (например, radix-sort).
• Ваши значения имеют 11 значащих битов; числа на реальных компьютерах имеют 16 или 32 бита, поэтому вы можете использовать наиболее важные биты 5 (или 21, в зависимости от вашей системы) как временное хранилище.
• Одним из возможных способов использования верхних 5 бит является размещение копии 5 LSB (оттенок). Это обратное значение двух частей при выполнении нормального целого сравнения (что делает оттенок более значительный, чем диаметр)

Answer 2

я вижу.
Я полагаю, что такая форма бриллианта может быть представлена ​​непосредственно массивом.
Игнорировать все -1 записей.

{ row-0 row-1 row-2 row-3 ... row-13 } 

{ 1 2 2 2 3 3 3 3 3 4 4 4 5 } 

Теперь вы можете отсортировать массив по своему усмотрению.
Сортируйте его дважды, один раз для оттенка, один раз для диаметра; или выяснить, как сортировать массив по двум критериям.

Вы также можете работать на месте, если вы просто напишете функцию преобразования индекса массива в координаты алмаза. Сделав это, вы можете просто работать над алмазной структурой, как если бы это был массив.

Answer 3

Написать сортировочную рутину с этим прототипом:

void sort(int startx, int starty, int dx, int dy, int count, int (*compare)(int, int)); 

или

void sort(int *start, int stride, int count, int (*compare)(int,int)); 

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