How to sort a multi-dimension array?

Question

Hello I have written a program to sort a multi-dimension array using bubble sort. I found it a bit difficult to sort a multi-dimension array as much as dimensions increase so I used a technique: copying a multi-dim array to a linear one then sort the latter then copy back it to the original:

#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;
}

The output:

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,

• The code works fine and easy to manage any array however the number of dimensions. Is this a good way or there's another better alternative?

Answer 1

A multidimensional array in C++ stores its data in contiguous memory. Thus getting a pointer to the first and one past the last item is all that is required to use the STL std::sort algorithm function to sort the array.

This will be much easier than trying to write your own sort, and will more than likely run faster since there is no need to "flatten" the array into a temporary one-dimensional array, and that you're taking advantage of std::sort's guarantee of logarithmic run-time complexity (as opposed to the bubble sort, which has O(n^2) complexity).

Here is an example of sorting the array in your question using 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

If you have to write a bubble sort (or any other type of sort), the basic reasoning still applies. As long as you get a pointer to the first item, you can write the traditional bubble sort, as shown here.

Additional Note:

Since the multidimensional array stores items in contiguous memory, not only std::sort will work, but any STL algorithm will work on the sequence (for example, std::unique, std::partition, etc.)

Arrays that are not layed out in contiguous memory

If you have created an "array" that does not lay out the data in contiguous memory (for example, creating a two-dimensional array of type T dynamically using a T** and dynamically allocating each row of data), then flattening the array to a temporary one-dimensional array, calling std::sort on the one-dimensional array, and copying back the one-dimensional array back to the multidimensional array would be one solution.