I have a 2D array of p*q. I want to sort this array in bunches of 2D arrays of m*n where p>m and p=km and q>n and q=kn and where k is and integer. for example i have array of 16*16 and i have divided it into 2d arrays of 4*4 now i want to sort these 4*4 arrays independently. Which algorithm can i use to sort these in place.means without using extra memory.
A:
If you want to sort the sub matrices, you have to provide a relational operator of some kind (for example compare the sum of all elements), and an order in which you want to sort (for example first left to right, then bottom-up)
Assuming you have both ;-) For minimizing memory usage, you can use any swap-based sorting algorithm, good old quicksort will do. An additional space for one single element of the sub matrix will always be neccessary though. The only thing you have to take care of is the actual swap operation, which has to swap elemnt by elemnt and not via a complete temporary sub matrix:
// swap sub matrix holding elements of T at position a with b
void swap(Matrix m, int ax, int ay, int bx, int by) {
for (int x=0; x<m; x++)
for (int y=0; y<m; y++)
std::swap(m[a+x][a+y], m[b+x][b+y])
}
You can find lots of implementations of quicksort everywhere, e. g. http://en.wikipedia.org/wiki/Quicksort
drhirsch
2009-08-15 08:00:34
+1
A:
You can use the regular STL sort algorithm if you write a specialized iterator that addresses your array the way you want. The more relevant question is: how do you want to order the 2D sub-arrays? Decide this first; this will tell you how to write the appropriate iterator.
comingstorm
2009-08-15 08:01:06
Can you guarantee std::sort does not use additional space, for example, a temporay matrix?
drhirsch
2009-08-15 08:14:46
The STL does not specify this -- although it does specify that it may change its behavior based on how much memory is available, which implies (suggests?) that it should be able to do an in-place sort if necessary.IIRC the usual STL sort is a quicksort (which is inplace) with small sub-cases handled by insertion sort (also inplace), but to avoid N^2 cases it may fall back on heapsort (which is also inplace). I don't know if it actually handles everything in an inplace way, though...
comingstorm
2009-08-15 08:44:34
Even if std::sort uses a in-place-swap, the swap operation is most likely implemented via a std::swap of the elements to be sorted, in this case, sub matrices. This requires a sub matrix as temporary, but for absolutly minimizing memory usage, you can swap the sub matrices element by element, as i wrote in my answer.Think of an emebedded device with a fixed size matrix and no additional memory. But OTOH in that case there wouldn't be a STL available too, probably ;-)
drhirsch
2009-08-15 10:58:53
A:
If you want absolutely the least additional memory usage for the sort and a guaranteed worst case sort-time, then heap-sort is the best choice. http://en.wikipedia.org/wiki/Heapsort
If your matrices are large you may want to have a look at intro-sort as well. It runs faster than heapsort and the memory requirements are guaranteed to be low (but not as low as heapsort) as well.
Intro-sort is a lot faster than heap-sort once your array is larger than your processor-cache. It's also the default sorting algorithm for most STL-implementations, so you may already have a good implementation sitting on your harddisk.
Nils Pipenbrinck
2009-08-15 10:07:44