Как сделать целочисленные массивы двойной сортировки, используя C ++?

Question

У меня есть целочисленные массивы из 3 столбцов, последние 2 элемента которых предназначены для сортировки.Например,

10 0 1

11 0 2

12 1 2

13 0 1

Я хочу, чтобы они стали:

10 0 1

13 0 1

11 0 2

12 1 2

Массивы сначала сортируются по 2-му столбцу, а затем снова по 3-му столбцу.

У меня более 3000 строк, поэтому мне нужно что-то быстрое.Как это сделать в c ++?

Примечание. Массив будет динамически размещаться с использованием следующих шаблонов:

template <typename T>
T **AllocateDynamic2DArray(int nRows, int nCols){
    T **dynamicArray;

    dynamicArray = new T*[nRows];
    for( int i = 0 ; i < nRows ; i++ ){
        dynamicArray[i] = new T[nCols];
        for ( int j=0; j<nCols;j++){
            dynamicArray[i][j]= 0;
        }
    }
    return dynamicArray;
}

в основном,

int ** lineFilter =AllocateDynamic2DArray (2 * numberOfLines, 3);

Answer 1

вы можете использовать std::sort(); однако это усложняется тем, что ваш массив является 2D.

Как правило, std::sort() не может есть 2D-массивы; вам нужно создать класс, который будет накапливать предупреждения и жалобы компилятора:

#include <iostream>
#include <algorithm>

int data[4][3] = {
    {10,0,1},
    {11,0,2},
    {12,1,2},
    {13,0,1}
};

struct row_t { // our type alias for sorting; we know this is compatible with the rows in data
    int data[3];
    bool operator<(const row_t& rhs) const {
        return (data[1]<rhs.data[1]) || ((data[1]==rhs.data[1]) && (data[2]<rhs.data[2]));
    }
};              

int main() {
    std::sort((row_t*)data,(row_t*)(data+4));
    for(int i=0; i<4; i++)
        std::cout << i << '=' << data[i][0] << ',' << data[i][1] << ',' << data[i][2] << ';' << std::endl; 
    return 0;
}

Становится намного проще, если вы используете std::vector для хранения предметов, которые действительно относятся к типу row_t или тому подобное. Векторы имеют динамический размер и сортируются.

Answer 2

Я думаю, что это должно работать:

template<typename T>
struct compareRows {
    bool operator() (T * const & a, T * const & b) {
        if (a[1] == b[1])
            return a[2] < b[2];
        else
            return a[1] < b[1];
    }
};

std::sort(dynamicArray, dynamicArray+nrows, compareRows<int>());

Используйте функтор для реализации сравнения между строками.Сортировка будет брать указатели на начало каждой строки и менять их местами в соответствии с содержимым строк.Строки останутся в памяти в тех же местах.

Answer 3

ОК, у OP есть целочисленные массивы из трех столбцов, которые не так просто отсортировать, потому что вы не можете назначать массивы.

Один из вариантов - иметь массивы структур, где структура содержит одинэлемент для каждого столбца, написать пользовательскую процедуру сравнения и использовать std::sort.

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

#include <algorithm>
#include <iostream>

struct elt_t
{
  int e0;
  int e1;
  int e2;
};

int
compare (const elt_t &a, const elt_t &b)
{
  if (a.e1 == b.e1)
    return a.e2 < b.e2;
  else
    return a.e1 < b.e1;
}

int a [10][3] = 
{
  { 10, 0, 1 },
  { 11, 0, 2 },
  { 12, 1, 2 },
  { 13, 0, 1 }
};


int
main ()
{
  std::sort (reinterpret_cast<elt_t *>(&a[0]),
             reinterpret_cast<elt_t *>(&a[4]), compare);

  int i, j;

  for (i = 0; i < 4; ++i)
    std::cout << a [i][0] << ", " << a [i][1] << ", " << a [i][2] << std::endl;

  return 0;
}

конечно, будь это или не соответствует стандартам очень спорно:)

1013 * EDIT: 1017 * с дополнительным требованиемдля динамического размещения матрицы можно использовать массив std::vector или вектор std::vector:

#include <algorithm>
#include <iostream>
#include <vector>

int
compare (const std::vector<int> &a, const std::vector<int> &b)
{
  if (a[1] == b[1])
    return a[2] < b[2];
  else
    return a[1] < b[1];
}


std::vector<int> *
make_vec (unsigned int r, unsigned int c)
{
  std::vector<int> *v = new std::vector<int> [r];

  /* Don't care for column count for the purposes of the example.  */
  v [0].push_back (10); v [0].push_back (0); v [0].push_back (1);
  v [1].push_back (11); v [1].push_back (0); v [1].push_back (2);
  v [2].push_back (12); v [2].push_back (1); v [2].push_back (2);
  v [3].push_back (13); v [3].push_back (0); v [3].push_back (1);

  return v;
}

int
main ()
{
  std::vector<int> *v = make_vec (4, 3);

  std::sort (&v[0], &v[4], compare);

  int i, j;

  for (i = 0; i < 4; ++i)
    std::cout << v[i][0] << ", " << v [i][1] << ", " << v [i][2] << std::endl;

  delete [] v;
  return 0;
}

Answer 4

Вы можете сделать это, используя алгоритм пузырьковой сортировки (http://en.wikipedia.org/wiki/Bubble_sort)

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

Продолжайте итерацию до тех пор, пока не произойдет перестановка.

Чтобы использовать ваш пример:

10 0 1
11 0 2
12 1 2 (поменяйте местами со следующим)
13 0 1

10 0 1
11 0 2 (своп со следующим)
13 0 1
12 1 2

10 0 1
13 0 1
11 0 2
12 1 2

И готово!

Answer 5

используйте это для второго столбца, а затем для третьего.Теперь это работает для одиночных диммерных массивов

   int *toplace(int *start, int *end)
{
    int *i = start+1, *j= end-1;

    while(i<=j)
    {
    while(*i<=*start && i<=j) {i++;}
    while(*j>=*start && i<=j) {j--;}    
    if (i<j) std::swap(*i++,*j--); 
    }

    std::swap(*start,*(i-1)); 
    return i-1;
}



void quicksort(int *start, int *end)
{
    if (start >= end) return;

    int *temp = start;
    temp = toplace(start,end);

    quicksort(start,temp);
    quicksort(temp+1,end);

}