By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,201 Members | 937 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,201 IT Pros & Developers. It's quick & easy.

Sort in the Descending Order

P: n/a
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
Nov 14 '05 #1
Share this Question
Share on Google+
7 Replies


P: n/a
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
Nov 14 '05 #2

P: n/a
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
Nov 14 '05 #3

P: n/a


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/

Nov 14 '05 #4

P: n/a
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.
Nov 14 '05 #5

P: n/a
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
Nov 14 '05 #6

P: n/a
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
Nov 14 '05 #7

P: n/a
pete wrote:
#define E_TYPE long double
#define STRING "%.0lf, "


That should be

#define STRING "%.0Lf, "

--
pete
Nov 14 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.