Bases on algorithm suggested by Lucifer, I have coded the problem in C
(please see attachment).
The code has been tested against the following test cases:
1 3 4 8 9
2 5 18 25 50
6 7 22 45 55
and
1 2 7
3 5 8
4 6 9
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/kQ0gKL_2h7oJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
?#include <stdio.h>
#define ROWS 3
#define COLS 5
void swap(int *a, int *b)
{
/*swap numbers a & b*/
int temp = *a;
*a = *b;
*b = temp;
}
void print_array(int *arr)
{
/*prints the two dimensional array arr*/
int i,j;
for(i=0;i<ROWS;i++)
{
for(j=0;j<COLS;j++)
{
printf(" %d ",arr[COLS*i + j]);
}
printf("\n");
}
}
int min(int a, int b)
{
/*Finds the minimum of a and b*/
if(a<b)
return a;
return b;
}
void adjustrow(int *arr,int cur_row,int cur_col)
{
/*adjusts the row in ascending order*/
if(arr[COLS*cur_row + cur_col+1] >= arr[COLS*cur_row + cur_col]) //elem in next column is greater
return;
swap(&arr[COLS*cur_row + cur_col+1],&arr[COLS*cur_row + cur_col]);
adjustrow(arr,cur_row,cur_col+1);
}
void adjustcol(int *arr,int cur_row,int cur_col)
{
/*adjusts the column in asceding order*/
if(arr[COLS*(cur_row+1) + cur_col] >= arr[COLS*cur_row + cur_col]) //elem in next row is greater
return;
swap(&arr[COLS*(cur_row+1) + cur_col],&arr[COLS*cur_row + cur_col]);
adjustcol(arr,cur_row+1,cur_col);
}
void readjust(int *arr,int cur_row, int cur_col)
{
/*re-adjusts the array so that the initial property of ascending rows and columns is maintained*/
if(cur_row == ROWS-1) //into the last row
{
adjustrow(arr,cur_row,cur_col);
return;
}
if(cur_col == COLS -1) //into the last column
{
adjustcol(arr,cur_row,cur_col);
return;
}
//new elem in right place
if(arr[COLS*cur_row + cur_col] <= min(arr[COLS*(cur_row+1) + cur_col],arr[COLS*(cur_row) + cur_col+1]))
return;
int new_cur_row = arr[COLS*(cur_row+1) + cur_col] <= arr[COLS*cur_row + cur_col+1] ? (cur_row+1) : cur_row;
int new_cur_col = arr[COLS*(cur_row+1) + cur_col] <= arr[COLS*cur_row + cur_col+1] ? cur_col : (cur_col+1);
swap(&arr[COLS*cur_row + cur_col],&arr[COLS*new_cur_row + new_cur_col]);
readjust(&arr[0],new_cur_row,new_cur_col);
}
void sort_whole_array(int *arr)
{
/*interface function for sorting the complete array*/
int i,j;
for(i=0;i<ROWS-1;i++)
{
for(j=1;j<COLS;j++)
{
if(arr[COLS*i + j] <= arr[COLS*(i+1) + 0]) //arr[i][j] <= arr[i+1][0]
continue;
swap(&arr[COLS*i + j],&arr[COLS*(i+1) + 0]); //swap(&arr[i][j],&arr[i+1][0])
readjust(&arr[0],(i+1),0); //readjust(&arr[i+1][0],i+1,0);
}
}
}
int main()
{
int arr[ROWS][COLS] = {{1,3,4,8,9},{2,5,18,25,50},{6,7,22,45,55}};
printf("\n==Input Array==\n");
print_array(&arr[0][0]);
sort_whole_array(&arr[0][0]);
printf("\n==Sorted Array==\n");
print_array(&arr[0][0]);
return 0;
}
