Sort in the Descending Order

[Luigi Napolitano]

Hello,

I use this algorithm to sort an array "v" in the descending order.

void quickSort(float v[], int lo0, int hi0)
{
int lo = lo0;
int hi = hi0;
if (lo >= hi) return;
float mid = v[(lo + hi) / 2];

while (lo < hi)
{
while (lo<hi && v[lo] > mid) lo++;
while (lo<hi && v[hi] < mid) hi--;
if (lo < hi) swap(v,lo, hi);
}

if (hi < lo) swap(v, hi, lo);

quickSort(v, lo0, lo);
quickSort(v, lo == lo0 ? lo+1 : lo, hi0);
}

I would like to have an array "index" to order another array "z".

Example:
v = [ 5, 9, 7 ]
index = [ 1, 2, 0 ]
z = [ 1, 2, 3 ]

so...
for (i = 0; i<=2; i++)
cout<<z[index[i]];
Output: [ 2, 3, 1 ]

I would like to have index = [ 1, 2, 0 ]. How?
Thanks to everybody.

Luigi Napolitano

[pete]

Luigi Napolitano wrote:

v = [ 5, 9, 7 ] z = [ 1, 2, 3 ] I would like to have index = [ 1, 2, 0 ]. How?

There's nothing you've written
which suggests an order of {1, 2, 0}.
Do you mean v = [ 7, 9, 5 ] ?

--
pete

[pete]

pete wrote:

Luigi Napolitano wrote:

v = [ 5, 9, 7 ]

z = [ 1, 2, 3 ]

I would like to have index = [ 1, 2, 0 ]. How?

There's nothing you've written
which suggests an order of {1, 2, 0}.
Do you mean v = [ 7, 9, 5 ] ?

This what I came up with, in case you did:

/* BEGIN order.c */

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

#if /**/ 0 /*/ 1 /**/
#define E_TYPE int
#define string "%d, "
#else
#define E_TYPE float
#define string "%.0f, "
#endif

#define NELM(X) (sizeof X / sizeof *X)

typedef E_TYPE e_type;

int compar(const void *key, const void *base);
void order(const void *key, void *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
e_type v[] = {7, 9, 5};
e_type z[] = {1, 2, 3};
e_type buff[NELM(v)];
size_t index[NELM(v)];
size_t i;

order(v, buff, index, NELM(v), sizeof *v, compar);
printf("Output: [ ");
for (i = 0; i != NELM(v); ++i) {
printf(string, z[index[i]]);
}
puts("\b\b ]");
return 0 ;
}

void order(const void *key, void *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
char *const b = base;
const char *k = key;
size_t n = nmemb;

memcpy(base, key, nmemb * size);
qsort(base, nmemb, size, compar);
while (nmemb-- != 0) {
*index++ = ((char *)bsearch(k, b, n, size, compar) - b) / size;
k += size;
}
}

int compar(const void *key, const void *base)
{
e_type k = *(e_type *)key;
e_type b = *(e_type *)base;

return b > k ? -1 : k > b;
}

/* END order.c */

--
pete

[Al Bowers]

pete wrote:

Luigi Napolitano wrote:

v = [ 5, 9, 7 ]

z = [ 1, 2, 3 ]

I would like to have index = [ 1, 2, 0 ]. How?

There's nothing you've written
which suggests an order of {1, 2, 0}.
Do you mean v = [ 7, 9, 5 ] ?

I believe the index set represents the element number
of v should it be sorted descending.
One approach would be to create an array of pointers
that point to each element in v. Sort descending the
array of pointers and then calculate offset.

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

int **CreatePointers(int *array, size_t nelems);
int cmp(const void *v1, const void *v2);

int main(void)
{
int v[] = {5 ,9 ,7};
size_t i , nelems = sizeof v / sizeof *v;
int **index = CreatePointers(v, nelems);

if(index)
{
qsort(index, nelems, sizeof *index, cmp);
printf("index = [ ");
for (i = 0; i < nelems; ++i)
printf(" %d", index[i] - v);
puts(" ]");
free(index);
}
else puts("Unable to create the pointer array");
return 0;
}

int **CreatePointers(int *array, size_t nelems)
{
int **parray;
size_t i;

if((parray = malloc(nelems * sizeof *parray)) != NULL)
for(i = 0; i < nelems; i++) parray[i] = &array[i];
return parray;
}

int cmp(const void *v1, const void *v2)
{
const int *i1 = *(const int **)v1;
const int *i2 = *(const int **)v2;

return *i1>*i2?-1:*i1!=*i2;
}

--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapidsys.com (remove the x to send email)
http://www.geocities.com/abowers822/

[Keith Thompson]

pete <pf*****@mindspring.com> writes:
[...]

#if /**/ 0 /*/ 1 /**/
#define E_TYPE int
#define string "%d, "
#else
#define E_TYPE float
#define string "%.0f, "
#endif

Without commenting on the rest of the code, that "#if" hurts my eyes.
I suppose you can change it from
#if /**/ 0 /*/ 1 /**/
to
#if /*/ 0 /**/ 1 /**/
if you want to enable the other block of code, but what's wrong with
#if 0
or
#if 1
?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

Keith Thompson wrote:

pete <pf*****@mindspring.com> writes:
[...]

#if /**/ 0 /*/ 1 /**/

Without commenting on the rest of the code, that "#if" hurts my eyes.

I read Al Bowers' post and stole all of his ideas and rewrote it.

/* BEGIN order.c */

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

#define E_TYPE float
#define STRING "%.0f, "

#define NELM(X) (sizeof X / sizeof *X)

typedef E_TYPE e_type;

int comparison(const void *key, const void *base);
void order(const void *key, void *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
e_type v[] = {5, 9, 7};
e_type z[] = {1, 2, 3};
void *buff[NELM(v)];
size_t index[NELM(v)];
size_t i;

order(v, buff, index, NELM(v), sizeof *v, comparison);
printf("Output: [ ");
for (i = 0; i != NELM(v); ++i) {
printf(STRING, z[index[i]]);
}
puts("\b\b ]");
return 0 ;
}

void order(const void *key, void *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
const char *k = key;
char const **b = base;
size_t n;

for (n = 0; n != nmemb; ++n) {
b[n] = n * size + k;
}
qsort(base, nmemb, size, compar);
while (n-- != 0) {
*index++ = (*b++ - k) / size;
}
}

int comparison(const void *key, const void *base)
{
const e_type k = **(const e_type **)key;
const e_type b = **(const e_type **)base;

return k > b ? -1 : k != b;
}

/* END order.c */

--
pete

[pete]

pete wrote:

Keith Thompson wrote:

pete <pf*****@mindspring.com> writes:
[...]

#if /**/ 0 /*/ 1 /**/

Without commenting on the rest of the code,
that "#if" hurts my eyes.

I read Al Bowers' post and stole all of his ideas and rewrote it.

void *buff[NELM(v)]; order(v, buff, index, NELM(v), sizeof *v, comparison); void order(const void *key, void *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{ qsort(base, nmemb, size, compar);
That's a bug. Should be "sizeof(void*)" instead of "size"
*index++ = (*b++ - k)

And you never know about ptrdiff_t expressions like (*b++ - k),
so I rewrote it again:

/* BEGIN order.c */

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

#define E_TYPE long double
#define STRING "%.0lf, "
#define NELM(array) (sizeof array / sizeof array[0])

struct ptr_index {
const void *pointer;
size_t index;
};

typedef E_TYPE e_type;

void order(const void *key, struct ptr_index *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
int comparison(const void *key, const void *base);

int main(void)
{
e_type v[] = {5, 9, 7};
e_type z[] = {1, 2, 3};
size_t index[NELM(v)];
size_t i;
struct ptr_index buff[NELM(v)];

order(v, buff, index, NELM(v), sizeof *v, comparison);
printf("Output: [ ");
for (i = 0; i != NELM(v); ++i) {
printf(STRING, z[index[i]]);
}
puts("\b\b ]");
return 0 ;
}

void order(const void *key, struct ptr_index *base, size_t *index,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
const char *const k = key;
size_t n, diff;

for (n = diff = 0; n != nmemb; ++n) {
base[n].index = n;
base[n].pointer = diff + k;
diff += size;
}
qsort(base, nmemb, sizeof *base, compar);
while (n-- != 0) {
index[n] = base[n].index;
}
}

int comparison(const void *key, const void *base)
{
const e_type k
= *(const e_type *)(((struct ptr_index *)key ) -> pointer);
const e_type b
= *(const e_type *)(((struct ptr_index *)base) -> pointer);

return k > b ? -1 : k != b;
}

/* END order.c */

--
pete

[pete]

pete wrote:

#define E_TYPE long double
#define STRING "%.0lf, "

That should be

#define STRING "%.0Lf, "

--
pete