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?

You can sort the array in place, just like my example. An array stores its data in contiguous memory, so knowing the address of the first and the address of the last element is all you need. Once you have those two items, then any traditional sorting algorithm will work since it's just a linear sequence. — PaulMcKenzie
– PaulMcKenzie, Commented Feb 14, 2017 at 23:20
@Lee_Wong Here is another example. I don't want to post these examples as answers, since I don't know if you're looking for a generic multidimension array sort, or looking for simpler code that sorts a multidimension array. — PaulMcKenzie
– PaulMcKenzie, Commented Feb 14, 2017 at 23:29

PaulMcKenzie · Accepted Answer · 2017-02-15 22:39:41Z

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.

edited Feb 15, 2017 at 22:39

answered Feb 15, 2017 at 14:32

PaulMcKenzie

35.6k4 gold badges26 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Lee_Wong Over a year ago

One last question: In the link you provided: Is if (*(first+j) > *(first+j+1)) std::swap(*(first+j), *(first+j+1)); identical to: if (first[j] > first[j+1]) std::swap(first[j], first[j+1]);?

PaulMcKenzie Over a year ago

Yes. You can use the array syntax.

Lee_Wong Over a year ago

Ok thanx for the good and thorough explanation. That's really helpful.

Collectives™ on Stack Overflow

How to sort a multi-dimension array?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related