У меня есть таблица, хранящаяся в памяти. Как мне отсортировать его по столбцу?

Question

У меня есть таблица, хранящаяся в непрерывной памяти.После сортировки он должен оставаться в этом формате.

Например:

int table[5][3] = {
    { 60, 5, 10 },
    { 0, 200, 15 },
    { 55, 50, 365 },
    { 4, 7, 78 },
    { 555, 8, 11 },
};

За исключением гораздо большего (размер самого большого в байтах составляет приблизительно 27 КБ).Каждая ячейка всегда представляет собой int32, и все строки имеют одинаковое количество столбцов.

Допустим, я хочу отсортировать его по первому столбцу, чтобы результат был эквивалентен:

    { 0, 200, 15 },
    { 4, 7, 78 },
    { 55, 50, 365 },
    { 60, 5, 10 },
    { 555, 8, 11 },

Какой лучший способ сделать это?Я предполагаю, что есть лучший способ, чем преобразовать это в std::list, вызвать sort() и преобразовать обратно.

Кроме того, что-то встроенное в C ++, где мне просто нужно вызвать какую-то функцию, было бы лучше.

Answer 1

std::sort не будет делать это легко, потому что массивы нельзя назначить.

Однако, std::qsort сделает это:

int cmp_first_column(const void *lhs_, const void *rhs_) {
    // optimize this to taste
    const int *lhs = static_cast<const int*>(lhs_);
    const int *rhs = static_cast<const int*>(rhs_);
    if (lhs[0] < rhs[0]) return -1;
    if (lhs[0] > rhs[0]) return 1;
    return 0;
}

std::qsort(table, 5, 3*sizeof(int), cmp_first_colum);

ОК, поэтому std::qsort не получает преимущества от оптимизации вставки шаблона, но выполняет свою работу, и, по крайней мере, вы не выделяете много памяти и не выполняете ненужного копирования.

Вместо этого вы можете заменить ваш массив int[3] на массив структур с int[3] в качестве члена данных. Тогда это можно было бы назначить, и вы могли бы использовать std::sort как обычно. Зависит от того, сколько другого написанного вами кода зависит от текущего типа, и от того, можно ли нарушить интерфейс, используемый этим кодом.

Answer 2

Да - сортировка с такими крупными объектами имеет тенденцию быть медленной просто потому, что копирование крупных предметов происходит медленно.

Вы можете (вероятно) ускорить его, создав индекс, содержащий ключ (элемент из первого столбца, который вы используете для сортировки) и указатель или индекс на исходную строку данных. Сортируйте индекс, затем используйте его, чтобы скопировать данные в новый массив в отсортированном порядке (и, при необходимости, вернуться к оригиналу). Это помогает сократить копирование до минимума, что может сэкономить значительное количество времени, если у вас много столбцов.

OTOH, учитывая, что вы говорите только о десятках килобайт (или около того) данных, вы можете довольно легко обойтись, просто используя qsort прямо на столе (с подходящей функцией сравнения). Это одна из тех редких ситуаций, где может иметь смысл использовать qsort в C ++. Поскольку Стив Джессоп исправил свой ответ, показывая этот метод, я оставлю это ему, а не покажу здесь.

Answer 3

Лично я бы написал простую сортировку, вроде пузырьковой сортировки, чтобы сделать это для меня, а не конвертировать, используя сортировку, конвертировать обратно.

Для пузырьковой сортировки вы просто просматриваете таблицу, просматривая данные в ряду и перед ним, затем переключаете их, если a> b и т. Д., Промываете и повторяете, пока ваши данные не будут отсортированы. Это не самый эффективный, но простой и быстрый по сравнению с небольшими наборами данных.