Selection sort for 2-Dimensional array

[zwpL3TCk]

Hi,How to implement selection sort in 2-dimensional array?
I can only do it in 1-dimensional array.

[helios]

The definition of "being sorted" is: given a data structure S, S is sorted iff for every pair of S indices i and j, i < j implies S_i <= S_j.
If S is an n-dimensional structure, i and j are in Nⁿ. Elements of N^k where k > 1 don't have a "natural order", so to speak. For example, it's not clear whether (1, 0) < (0, 2).

In order to sort a higher-dimensional data structure, you need to be able to treat it as a 1-dimensional data structure.

[andywestken]

Out of blatant curiousity, do you have a particular problem you're trying to solve by sorting a 2D array??

Andy

[mighty asker]

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int A[4][3] =
	{ { 22, 23, 10 },
	{ 15, 25, 13 },
	{ 20, 74, 67 },
	{ 11, 18, 14 } };
	int rows = 4;
	int cols = 3;


	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < cols; j++)
		{
			for (int inside_i = i; inside_i < rows; inside_i++)
			{
				for (int inside_j = j; inside_j < cols; inside_j++)
				{
					if (A[i][j] > A[inside_i][inside_j])
					{
						swap(A[i][j], A[inside_i][inside_j]);
					}
				}
			}
		}
	}
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < cols; j++)
		{
			cout << A[i][j] << " ";
		}
		cout << endl;
	}


	system("Pause");
	return 0;
}

Not working properly.

[D80DSL3A]

Memory is contiguous across all elements so the array may be treated as 1-dimensional, which helios has pointed out is required.

Just use std::sort if you can.
Working properly:

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int A[4][3] =
	{ { 22, 23, 10 },
	{ 15, 25, 13 },
	{ 20, 74, 67 },
	{ 11, 18, 14 } };
	int rows = 4;
	int cols = 3;

    std::sort( A[0], A[4] );// given pointers to 1st element and 1 past last element
	
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < cols; j++)
		{
			cout << A[i][j] << " ";
		}
		cout << endl;
	}


	system("Pause");// boo!
	return 0;
}

EDIT: Maybe more helpful in writing a sort function yourself and using it.
I found this insertion sort code I wrote some time ago.
Here's a usage demo with a 2d array:

#include<iostream>
#include<algorithm>
using namespace std;

// find index to min element
int minIdx( int a[], int i )
{
    if( i == 0 ) return 0;
    int j = minIdx( a, i-1 );
    if( a[i-1] < a[j] ) return i-1;
    return j;
}

void mySwap( int& x, int& y )
{
    int temp = x;
    x = y;
    y = temp;
}

// insertion sort.
void mySort_rec( int* a, int sz )
{
    if( sz == 1 ) return;
    int j = minIdx( a, sz );
    if( j != 0 ) mySwap( *a, a[j] );
    mySort_rec( ++a, sz-1 );
}

int main()
{
	int A[4][3] =
	{ { 22, 23, 10 },
	{ 15, 25, 13 },
	{ 20, 74, 67 },
	{ 11, 18, 14 } };
	int rows = 4;
	int cols = 3;

//    std::sort( A[0], A[4] );
    mySort_rec( A[0], 4*3 );// given pointer to 1st element and # of elements

        // display array values
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < cols; j++)
		{
			cout << A[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}

EDIT2: In researching selection sort it appears that I've implemented it above.

[andywestken]

Sorting 2d array:
- in columns
- in rows
- in diaganols

starting array
22 23 10
15 25 13
20 74 67
11 18 14

sort_in_cols
10 15 23
11 18 25
13 20 67
14 22 74

sort_in_rows
10 11 13
14 15 18
20 22 23
25 67 74

sort_in_diags
10 13 18
11 15 23
14 22 67
20 25 74

Andy

#include <iostream>
using namespace std;

void sort_in_rows(int* A, int rows, int cols);
void sort_in_cols(int* A, int rows, int cols);
void sort_in_diags(int* A, int rows, int cols);
void output(const int* A, int rows, int cols);

template <int ROWS, int COLS>
void sort_in_rows(int (&A)[ROWS][COLS]) {
    sort_in_rows(&A[0][0], ROWS, COLS);
}

template <int ROWS, int COLS>
void sort_in_cols(int (&A)[ROWS][COLS]) {
    sort_in_cols(&A[0][0], ROWS, COLS);
}

template <int ROWS, int COLS>
void sort_in_diags(int (&A)[ROWS][COLS]) {
    sort_in_diags(&A[0][0], ROWS, COLS);
}

template <int ROWS, int COLS>
void output(const int (&A)[ROWS][COLS]) {
    output(&A[0][0], ROWS, COLS);
}

int main()
{
    const int ROWS = 4;
    const int COLS = 3;

    int A[ROWS][COLS] =
    { { 22, 23, 10 },
      { 15, 25, 13 },
      { 20, 74, 67 },
      { 11, 18, 14 } };

    cout << "starting array" << endl;
    output(A);
    cout << endl;

    cout << "sort_in_cols" << endl;
    sort_in_cols(A);
    output(A);
    cout << endl;

    cout << "sort_in_rows" << endl;
    sort_in_rows(A);
    output(A);
    cout << endl;

    cout << "sort_in_diags" << endl;
    sort_in_diags(A);
    output(A);
    cout << endl;

    return 0;
}

void ptr_select_sort(int* pp[], int elems) {
    for (int j = 0; j < (elems - 1); ++j) {
        int iMin = j;
        for (int i = (j + 1); i < elems; ++i) {
            if (*pp[i] < *pp[iMin])
                iMin = i;
        }
        if(iMin != j) {
            int tmp = *pp[j];
            *pp[j] = *pp[iMin];
            *pp[iMin] = tmp;
        }
    }
}

void sort_in_rows(int* A, int rows, int cols)
{
    int elems = rows * cols;
    int** pp = new int*[rows * cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            pp[i * cols + j] = &A[i * cols + j];
        }
    }
    ptr_select_sort(pp, elems);
    delete [] pp;
}

void sort_in_cols(int* A, int rows, int cols)
{
    int elems = rows * cols;
    int** pp = new int*[rows * cols];
    for (int j = 0; j < cols; ++j) {
        for (int i = 0; i < rows; ++i) {
            pp[i + j * rows] = &A[i * cols + j];
        }
    }
    ptr_select_sort(pp, elems);
    delete [] pp;
}

void sort_in_diags(int* A, int rows, int cols)
{
    int elems = rows * cols;
    int** pp = new int*[rows * cols];
    int k = 0;
    for (int i_start = 0; i_start < (rows + cols - 1); ++i_start) {
        int i = i_start;
        int j_start = 0;
        while(i > (rows - 1)) {
            --i;
            ++j_start;
        }
        for (int j = j_start; (j < cols) && (i >= 0); ++j)
            pp[k++] = &A[i-- * cols + j];
    }
    ptr_select_sort(pp, elems);
    delete [] pp;
}

void output(const int* A, int rows, int cols)
{
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++)
            cout << A[i * cols + j] << " ";
        cout << endl;
    }
}