Как быстро отсортировать двумерный массив по определенной ячейке?

Question

Как быстро отсортировать двумерный массив по определенной ячейке?

У меня есть 2d массив, и я хотел бы быстро отсортировать его с помощью заданной функции qsort () в C ++:

unsigned work[N][3];

Я хотел бы отсортировать массив «работа» по третьему индексу … так что если work[i] идет раньше work[j] если work[i][2]>work[j][2],

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

редактировать:
Если бы я сделал следующее, это помогло бы:

unsigned work[3][N];
qsort(work[2], N, sizeof(unsigned), compare);

И сравнить было бы следующее:

int compare(const void* a, const void* b)
{
return(*(unsigned*)a-*(unsigned*)b);
}

?

4

c++multidimensional-array qsort quicksort

Решение

Другие решения

Да, ты можешь qsort() этот. qsort() работает, беря необходимый линейный блок «вещи», разбивая его на куски одинакового размера, где вы укажите размер (в байтах) и укажите базовый адрес каждого раздела блока для сравнения.

Сначала определите, какой размер вам нужен. Должно быть очевидно, что «вещи», которые вы сортируете, являются массивом строки три элемента в ширину. Во-вторых, напишите компаратор, который может принять базовый адрес двух таких вещей, как указатели, в нашем случае будет работать простой указатель, так как он хорошо снимает размер внешнего массива. Наконец, собственно сравнение будет состоять из трех элементов (p[2] чтобы быть точным) от каждого указателя p были даны:

Итак, давайте уточним код:

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <time.h>

static const size_t ROWSIZE = 3;

static void print_array(int rows, int ar[rows][ROWSIZE])
{
int i,j;
for (i=0;i<rows;++i)
{
for (j=0; j<ROWSIZE; printf("%d ", ar[i][j++]));
printf("\n");
}
printf("\n");
}

// compare function
static int compare_row(const void* left, const void* right)
{
const int *ileft = left, *iright = right;
return ileft[ROWSIZE-1] - iright[ROWSIZE-1];
}

int main()
{
int ar[10][ROWSIZE] = {0}, i;

// fill with random junk from 10 to 99
srand((unsigned)time(0));

for (i=0;i<ROWSIZE * sizeof(ar)/sizeof(ar[0]); ++i)
ar[i/ROWSIZE][i%ROWSIZE] = 10 + (rand() % 90);

// print prior to sort.
print_array(sizeof(ar)/sizeof(ar[0]), ar);

// send to qsort
qsort(ar, sizeof(ar)/sizeof(ar[0]), sizeof(ar[0]), compare_row);

// print again after sort.
print_array(sizeof(ar)/sizeof(ar[0]), ar);

return EXIT_SUCCESS;
}

Пример вывода

2

Источник

Accepted Answer

Ну, краткий ответ будет не использовать std::qsort вообще, но std::sort. Но, к сожалению, последний не будет работать, так как unsigned int[3] не присваивается Так что вот самый простой std::qsort решение.

Сначала мы определяем пользовательскую функцию компаратора:

// return -1 if a before b, 1 if after, 0 if equal
int compare(const void *a, const void *b)
{
const unsigned int *arg1 = reinterpret_cast<const unsigned int*>(a);
const unsigned int *arg2 = reinterpret_cast<const unsigned int*>(b);
if(arg1[2] > arg2[2])
return -1;
if(arg1[2] < arg2[2])
return 1;
return 0;
}

Который мы затем используем для сортировки массива. Имейте в виду, что work является массивом массивов, и, таким образом, work[0] это массив из 3 unsigned ints, нет никакого косвенного указания указателя. Так что он идеально подходит для сортировки по std::qsort:

std::qsort(work, sizeof(work)/sizeof(work[0]), sizeof(work[0]), compare);

Кстати, третий элемент индексируется с 2поскольку мы обычно начинаем считать 0 в C ++ (и многих других языках программирования).

РЕДАКТИРОВАТЬ: Тем не менее, наилучшим решением было бы удалить этот массив массивов и использовать что-то более подходящее для C ++, например std::vector из std::array<unsigned int,3>s (или любая другая структура данных, которая немного больше соответствует реальному контексту):

typedef std::array<unsigned int,3> uint3;
std::vector<uint3> work(N);

Который затем можно отсортировать с помощью простого:

std::sort(std::begin(work), std::end(work),
[](const uint3 &a, const uint3 &b) { return a[2] > b[2]; });

Или, если у вас нет C ++ 11 (хотя в этом случае у вас не будет std::array либо нужно подумать о резонируемой структуре данных, кроме простого 3-х массивов):

struct compare
{
bool operator()(const uint3 &a, const uint3 &b) const
{
return a[2] > b[2];
}
};

std::sort(work.begin(), work.end(), compare());

В качестве бонуса к гораздо более четкому коду, вы также, скорее всего, получите небольшое повышение производительности std::sort над std::qsort,

4