446,201 Members | 937 Online 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 mid) lo++; while (lo
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 #include #include #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 #include 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 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 San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 14 '05 #5

 P: n/a Keith Thompson wrote: pete 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 #include #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 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 #include #define E_TYPE long double #define STRING "%.0lf, " #define NELM(array) (sizeof array / sizeof array) 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. 