Как отсортировать многомерный массив?

Question

Здравствуйте, я написал программу для сортировки многомерного массива с использованием сортировки пузырьков. Мне было сложно сортировать многомерный массив столько же, сколько размеры увеличивались, поэтому я использовал технику: копирование многодискового массива в линейный, затем сортировку последнего, затем копирование его в исходное:

#include <iostream> 

int main(){ 

    const int d1 = 2, d2 = 3, d3 = 2; 
    int array[d1][d2][d3] = { 
     { {5 , 7}, {2, 55}, {17, 23} }, 
     { {57, 77}, {1, 0} , {21, 16} } 
     }; 

    std::cout << "Before sorting: " << std::endl << std::endl; 

    for(int i(0); i < 2; i++){ 
     for(int j(0); j < 3; j++){ 
      for(int k(0); k < 2; k++) 
       std::cout << array[i][j][k] << ", "; 
      std::cout << " "; 
     } 
     std::cout << std::endl; 
    } 

    std::cout << std::endl; 

    const int size = d1 * d2 * d3; 
    int array2[size] = {0}; 

    memcpy(array2, array, sizeof(int) * size); 

    for(int i(0); i < size; i++) 
     std::cout << array2[i] << ", "; 
    std::cout << std::endl << std::endl; 

    for(int i(0); i < size; i++) 
     for(int j(i + 1); j < size; j++) 
      if(array2[i] > array2[j]){ 
       array2[i] ^= array2[j]; 
       array2[j] ^= array2[i]; 
       array2[i] ^= array2[j]; 
      } 

    for(int i(0); i < size; i++) 
     std::cout << array2[i] << ", "; 
    std::cout << std::endl << std::endl; 

    memcpy(array, array2, sizeof(int) * size); 

    std::cout << "After sorting:" << std::endl << std::endl; 
    for(int i(0); i < 2; i++){ 
     for(int j(0); j < 3; j++){ 
      for(int k(0); k < 2; k++) 
       std::cout << array[i][j][k] << ", "; 
      std::cout << " "; 
     } 
     std::cout << std::endl; 
    } 

    std::cout << std::endl; 
    return 0; 
} 

выход:

Before sorting: 

5, 7, 2, 55, 17, 23, 
57, 77, 1, 0, 21, 16, 

5, 7, 2, 55, 17, 23, 57, 77, 1, 0, 21, 16, 

0, 1, 2, 5, 7, 16, 17, 21, 23, 55, 57, 77, 

After sorting: 

0, 1, 2, 5, 7, 16, 
17, 21, 23, 55, 57, 77, 

• код прекрасно и легко работает управлять любой массив однако количество измерений. Это хороший способ или есть другая лучшая альтернатива?

Answer 1

Многомерный массив в C++ хранит свои данные в смежной памяти. Таким образом, получение указателя на первый и один за последний элемент - это все, что требуется для использования функции алгоритма STL std::sort для сортировки массива.

Это будет намного проще, чем попытаться написать свой собственный вид и, скорее всего, будет работать быстрее, поскольку нет необходимости «сглаживать» массив во временном одномерном массиве и что вы пользуетесь от std::sort - гарантия логарифмической сложности во время выполнения (в отличие от сортировки пузырьков, которая имеет сложность O(n^2)).

Вот пример сортировки массива в вашем вопросе, используя std::sort:

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    const int d1 = 2, d2 = 3, d3 = 2; 
    int array[d1][d2][d3] = { 
     { {5 , 7}, {2, 55}, {17, 23} }, 
     { {57, 77}, {1, 0} , {21, 16} } 
     }; 

    // get the number of elements 
    const int numberOfElements = sizeof(array)/sizeof(int); 

    // get pointers to first and one past the last element 
    int *first = &array[0][0][0]; 
    int *last = first + numberOfElements; 

    // call sort function 
    std::sort(first, last); 

    // output results. 
    for(int i = 0; i < d1; ++i) 
     for (int j = 0; j < d2; ++j) 
     for (int k = 0; k < d3; ++k) 
      std::cout << array[i][j][k] << "\n"; 
}     

Live Example

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

Дополнительное примечание:

Поскольку многомерный массив хранит элементов в непрерывной памяти, а не только std::sort будет работать, но любой алгоритм STL будет работать на последовательности (например, std::unique, std::partition и т.д.)

Массивы, которые не уложены в непрерывной памяти

Если вы создали «массив», который делает не выкладывают данные в непрерывной памяти (например, создавая двумерный массив типа T динамически с использованием T** и динамически распределяя каждую строку данных), затем сглаживая массив во временном одномерном массиве, вызывая std::sort на одномерном массиве, и копирование назад одномерного массива обратно в многомерный массив будет одним из решений.