sorting 2d arrays using qsort

[yatindran]

hai
this is my 2d array.
int a[][6] = {
{5,2,20,1,30,10 },
{23,15,7,9,11,3 },
{40,50,34,24,14 ,4},
{9,10,11,12,13, 14},
{31,4,18,8,27,1 7},
{44,32,13,19,41 ,19},
{1,2,3,4,5,6},
{80,37,47,18,21 ,9}
};
after
for(i=0;i<box;i ++)
qsort(a[i],dim,sizeof(int ),dim*_sort);
int dim_sort(const void *a,const void *b)
{
return ( *(int*)a - *(int*)b);
}
where dim=6, i get the foll o/p:
1 2 5 10 20 30
3 7 9 11 15 23
4 14 24 34 40 50
9 10 11 12 13 14
4 8 17 18 27 31
13 19 19 32 41 44
1 2 3 4 5 6
9 18 21 37 47 80
(works fine!)
now i want to sort each row of elements for above array,
like
1 2 3 4 5 6
1 2 5 10 20 30
....
etc.

what is the qsort routine and function, can anybody help me ?
cheers,
badri

[James Daughtry]

> return ( *(int*)a - *(int*)b);
That's a dangerous way to compare two signed integers. You're risking
underflow, which is undefined.

now i want to sort each row of elements for above array

You can't do it with qsort because qsort tries to directly exchange two
items; an operation that arrays don't support. You can, however, create
an array of pointers to int, point them to each array in a, and then
sort that array by writing another comparison function that compares
the first mismatch in the two arrays being compared:

#include <stdio.h>
#include <stdlib.h>

static int arraya[][6] = {
{5,2,20,1,30,10 },
{23,15,7,9,11,3 },
{40,50,34,24,14 ,4},
{9,10,11,12,13, 14},
{31,4,18,8,27,1 7},
{44,32,13,19,41 ,19},
{1,2,3,4,5,6},
{80,37,47,18,21 ,9}
};

static int *arrayb[8];

int cmp_int(const void *a,const void *b)
{
const int *ia = a;
const int *ib = b;

if (*ia < *ib) return -1;
else if (*ia > *ib) return +1;
else return 0;
}

int cmp_array(const void *a, const void *b)
{
const int **ia = a;
const int **ib = b;
int i, cmp;

for (i = 0; i < 6; i++) {
if ((cmp = cmp_int(&(*ia)[i], &(*ib)[i])) != 0)
return cmp;
}

return 0;
}

int main(void)
{
int i, j;

for (i = 0; i < 8; i++)
qsort(arraya[i], 6, sizeof(int), cmp_int);

for (i = 0; i < 8; i++) {
for (j = 0; j < 6; j++)
printf("%4d", arraya[i][j]);
printf("\n");
}

printf("\n");

for (i = 0; i < 8; i++)
arrayb[i] = arraya[i];

qsort(arrayb, 8, sizeof(int*), cmp_array);

for (i = 0; i < 8; i++) {
for (j = 0; j < 6; j++)
printf("%4d", arrayb[i][j]);
printf("\n");
}

printf("\n");
}

[Lawrence Kirby]

On Sat, 11 Jun 2005 05:35:06 -0700, yatindran wrote:

hai
this is my 2d array.
int a[][6] = {
{5,2,20,1,30,10 },
{23,15,7,9,11,3 },
{40,50,34,24,14 ,4},
{9,10,11,12,13, 14},
{31,4,18,8,27,1 7},
{44,32,13,19,41 ,19},
{1,2,3,4,5,6},
{80,37,47,18,21 ,9}
};
after
for(i=0;i<box;i ++)
qsort(a[i],dim,sizeof(int ),dim*_sort);
You could write this as
int dim_sort(const void *a,const void *b)
{
return ( *(int*)a - *(int*)b);
}
Be caseful, subtracting 2 ints can overflow so this isn't well defined
unless you can be sure that the difference between any 2 values in the
array is representable as an int. It would be safer not to make
assumptions like this:

int dim_sort(const void *va, const void *vb)
{
int a = *(const int *)va;
int b = *(const int *)vb;

return (a<b) ? -1 : (a>b);
}
where dim=6, i get the foll o/p:
1 2 5 10 20 30
3 7 9 11 15 23
4 14 24 34 40 50
9 10 11 12 13 14
4 8 17 18 27 31
13 19 19 32 41 44
1 2 3 4 5 6
9 18 21 37 47 80
(works fine!)
OK, you're sorting the contents each row individually which is fine.
now i want to sort each row of elements for above array,
like
1 2 3 4 5 6
1 2 5 10 20 30
...
etc.

what is the qsort routine and function, can anybody help me ?

You just have to remember that the array a is simply an array of elements
where each of those elements is itself an array, so you can write:

qsort(a, sizeof a/sizeof *a, sizeof *a, compare_rows);

Where sizeof a/sizeof *a is the number of rows in a, sizeof *a is the
size in bytes of a row. The comparison function would be something like

static int compare_rows(co nst void *va, const void *vb)
{
const int *pa = *(const int (*)[6])va;
const int *pb = *(const int (*)[6])vb;
int i;

for (i = 0; i < 6; i++) {
if (pa[i] != pb[i])
return (pa[i] > pb[i]) ? 1 : -1;
}

return 0;
}

Lawrence

[Lawrence Kirby]

On Sat, 11 Jun 2005 07:27:29 -0700, James Daughtry wrote:

return ( *(int*)a - *(int*)b); That's a dangerous way to compare two signed integers. You're risking
underflow, which is undefined.

now i want to sort each row of elements for above array

You can't do it with qsort because qsort tries to directly exchange two
items; an operation that arrays don't support.

C doesn't directly supply an exchange operation for any type, arrays are
no different in this respect. In fact there is nothing in the definition
of qsort() that requires it to use exchanges as such, although many common
sorting algorithms do use them. The more fundamental operation is a copy.
qsort() doesn't know or care about the type of the elements of the array
it is sorting, in particular it doesn't care whether they are are
themselves arrays or not. In C you can copy (and therefore exchange a
pair of) ANY object by treating it as an array of sizeof(object) bytes
(specifically an array of unsigned char). An implementation of qsort() is
likely to use memcpy() or something equivalent for copying which works
fine on arrays. All it needs to do this is a pointer to the object and the
size of the object in bytes. All the necessary information is passed in
qsort()'s arguments.
You can, however, create
an array of pointers to int, point them to each array in a, and then
sort that array by writing another comparison function that compares
the first mismatch in the two arrays being compared:

You can do that, and there may be efficiency advantages to doing so (i.e.
copying a pointer is likely to be quicker than copying a row), but you
don't have to.

Lawrence

[James Daughtry]

> An implementation of qsort() is likely to use memcpy() or something equivalent for

copying which works fine on arrays.

True, but can that be relied on to portably sort a two dimensional
array as you suggested?

[Lawrence Kirby]

On Sat, 11 Jun 2005 12:02:34 -0700, James Daughtry wrote:

An implementation of qsort() is likely to use memcpy() or something equivalent for
copying which works fine on arrays.

True, but can that be relied on to portably sort a two dimensional
array as you suggested?

Yes. There's nothing that makes arrays different to any other type of
object for the purposes of qsort(). Remember again that the implementation
of qsort() knows nothing about the type of the data being sorted - C
doesn't have any form of runtime type information.

More fundamentally there is noting in the standard's specification of
qsort() that precludes it from sorting arrays whose elements are
themselves arrays.

Lawrence

[CBFalconer]

Lawrence Kirby wrote:

On Sat, 11 Jun 2005 12:02:34 -0700, James Daughtry wrote:

An implementation of qsort() is likely to use memcpy() or
something equivalent for copying which works fine on arrays.

True, but can that be relied on to portably sort a two dimensional
array as you suggested?

Yes. There's nothing that makes arrays different to any other type
of object for the purposes of qsort(). Remember again that the
implementation of qsort() knows nothing about the type of the data
being sorted - C doesn't have any form of runtime type information.

More fundamentally there is noting in the standard's specification
of qsort() that precludes it from sorting arrays whose elements
are themselves arrays.

Except you have to decide and codify what makes A1 > A2, or A1 <
A2, or A1 == A2.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Lawrence Kirby]

On Sat, 11 Jun 2005 22:21:45 +0000, CBFalconer wrote:

Lawrence Kirby wrote:

....

More fundamentally there is noting in the standard's specification
of qsort() that precludes it from sorting arrays whose elements
are themselves arrays.

Except you have to decide and codify what makes A1 > A2, or A1 <
A2, or A1 == A2.

As you do with any type of array element.

Lawrence

[pete]

ya*******@gmail .com wrote:

hai
this is my 2d array.
int a[][6] = {
{5,2,20,1,30,10 },
{23,15,7,9,11,3 },
{40,50,34,24,14 ,4},
{9,10,11,12,13, 14},
{31,4,18,8,27,1 7},
{44,32,13,19,41 ,19},
{1,2,3,4,5,6},
{80,37,47,18,21 ,9}
};
after
for(i=0;i<box;i ++)
qsort(a[i],dim,sizeof(int ),dim*_sort);
int dim_sort(const void *a,const void *b)
{
return ( *(int*)a - *(int*)b);

}

where dim=6, i get the foll o/p:
1 2 5 10 20 30
3 7 9 11 15 23
4 14 24 34 40 50
9 10 11 12 13 14
4 8 17 18 27 31
13 19 19 32 41 44
1 2 3 4 5 6
9 18 21 37 47 80
(works fine!)
now i want to sort each row of elements for above array,
like
1 2 3 4 5 6
1 2 5 10 20 30
...
etc.

what is the qsort routine and function, can anybody help me ?

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>

int int_comp(const void *a, const void *b);
int a6int_comp(cons t void *a, const void *b);

int main(void)
{
int a[][6] = {
{5,2,20,1,30,10 },
{23,15,7,9,11,3 },
{40,50,34,24,14 ,4},
{9,10,11,12,13, 14},
{31,4,18,8,27,1 7},
{44,32,13,19,41 ,19},
{1,2,3,4,5,6},
{80,37,47,18,21 ,9}
};
const size_t dim = sizeof *a / sizeof **a;
const size_t box = sizeof a / sizeof *a;
size_t i, j;

puts("\n/* BEGIN new.c output */\n");
for (i = 0; i != box; ++i) {
for (j = 0; j != dim; ++j) {
printf("%d ", a[i][j]);
}
putchar('\n');
}
putchar('\n');
for (i = 0; i != box; ++i) {
qsort(a[i], dim, sizeof *a[i], int_comp);
}
for (i = 0; i != box; ++i) {
for (j = 0; j != dim; ++j) {
printf("%d ", a[i][j]);
}
putchar('\n');
}
putchar('\n');
qsort(a, box, sizeof *a, a6int_comp);
for (i = 0; i != box; ++i) {
for (j = 0; j != dim; ++j) {
printf("%d ", a[i][j]);
}
putchar('\n');
}
puts("\n/* END new.c output */");
return 0;
}

int int_comp(const void *a, const void *b)
{
return *(int *)b > *(int *)a ? -1 : *(int *)b != *(int *)a;
}

int a6int_comp(cons t void *a, const void *b)
{
size_t n;
const int *a_ptr = a;
const int *b_ptr = b;

for (n = 0; n != 6; ++n) {
if (b_ptr[n] > a_ptr[n]) {
return -1;
}
if (a_ptr[n] > b_ptr[n]) {
return 1;
}
}
return 0;
}

/* END new.c */
--
pete

[pete]

Lawrence Kirby wrote:

In C you can copy (and therefore exchange a
pair of) ANY object by treating it as an array of sizeof(object) bytes
(specifically an array of unsigned char).

/* BEGIN new.c */

#include <stdio.h>

void swap(void *s1, void *s2, size_t n);

int main(void)
{
char odd[] = "1 3 5 7 9";
char even[] = "0 2 4 6 8";
double three = 3.0;
double four = 4.0;

swap(&odd, &even, sizeof odd);
printf("odd %s\n", odd);
printf("even %s\n", even);
swap(&three, &four, sizeof three);
printf("three %f\n", three);
printf("four %f\n", four);
return 0;
}

void swap(void *s1, void *s2, size_t n)
{
unsigned char *p1, *p2, *end, temp;

p1 = s1;
p2 = s2;
end = p2 + n;
do {
temp = *p1;
*p1++ = *p2;
*p2++ = temp;
} while (p2 != end);
}

/* END new.c */
--
pete