100. Snake Order

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to sort a matrix of integer into snake order as follows.

p100.pngp100.png

Your need to write the following function to sort a matrix into snake order.

1
void snake(const int *ptr_array[100][100], int m);

Note that the first parameter is a two dimensional array of pointers to constant integer, so do not try to change the value pointed by the pointer in the array. Instead you should exchange the pointers in order to sort. Your function should work with the following main program.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <assert.h>
 
void snake(const int *ptr_array[100][100], int m);
 
int main()
{
  int array[100][100], check[100][100];
  const int *ptr_array[100][100];
  int i, j, m;
 
  scanf("%d", &m);
  for (i = 0; i < m; i++)
    for (j = 0; j < m; j++) {
      ptr_array[i][j] = &(array[i][j]);
      scanf("%d", &(array[i][j]));
      check[i][j] = array[i][j];
    }
 
  snake(ptr_array, m);
 
  for (i = 0; i < m; i++) {
    for (j = 0; j < m; j++) {
      assert(check[i][j] == array[i][j]);
      assert((ptr_array[i][j] >= &array[0][0]) && (ptr_array[i][j] <= &array[99][99]));
      printf("%d ", *(ptr_array[i][j]));
    }
    printf("\n");
  }
 
  return 0;
}

Input

The first line of the input has the $m$. Each of the next $m$ lines has the numbers in a row of the matrix.

Output

The output has $m$ lines. Each of the $m$ lines is a row in the sorted matrix in snake order.

Sample input

3
59 33 2
14 45 16
51 4 27

Sample output

2 4 14
33 27 16
45 51 59

Hint

You can think of the two dimensional array as a single one dimensional array, and perform a bubble sort on this one dimensional array.

Discussion