Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4FD6AB24.F3D@mindspring.com> (permalink) |
|---|---|
| Date | 2012-06-11 22:36 -0400 |
| From | pete <pfiland@mindspring.com> |
| Organization | PF |
| Newsgroups | comp.lang.c |
| Subject | Re: Breakthrough |
| References | (6 earlier) <98pus75mg8q054gcv696u78gvg7gs6h1nk@4ax.com> <4FCFEC9A.C74@mindspring.com> <jqrdv0$p9f$1@speranza.aioe.org> <4FD41941.2DB0@mindspring.com> <ba18aea5-a8ab-4987-a2d5-e083f9b3d42f@googlegroups.com> |
88888 Dihedral wrote:
>
> peteæ–¼ 2012å¹´6月10日星期日UTC+8上åˆ11時49分21秒寫é“：
> > jacob navia wrote:
> >
> > > Maybe you have some spare time?
> > ** This is a version of listgen.c with a new QSORT based on pqsort.
> > ** It's an introspective quicksort.
> > ** If you like, I can toss in a PRNG for the pivot selection.
> > /*---------------------------------------------------------------------------*/
> > /* qsort() - perform a quicksort on an
> > array */
> > /*---------------------------------------------------------------------------*/
> >
> > #ifndef COMPARE_EXPRESSION
> > #error foo
> > #define COMPARE_EXPRESSION(l,lo) comp(l, lo)
> > //COMPAR(A, B) (B > A ? -1 : B != A)
> > #endif
> >
> > #define E_TYPE LIST_ELEMENT *e_type
> > #define GT(A, B) (COMPARE_EXPRESSION((A), (B)) > 0)
> > #define MOV(A, B) ((void)(*(A) = *(B)))
> > #define SMALL_PARTITION 8
> >
> > #define SWAP(A, B, T) \
> > (MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))
> >
> > #define SORT_3(A, B, C, T) \
> > if (GT((A), (B))) { \
> > MOV((T), (A)); \
> > if (GT((C), (B))) { \
> > MOV((A), (B)); \
> > if (GT((T), (C))) { \
> > MOV((B), (C)); \
> > MOV((C), (T)); \
> > } else { \
> > MOV((B), (T)); \
> > } \
> > } else { \
> > MOV((A), (C)); \
> > MOV((C), (T)); \
> > } \
> > } else { \
> > if (GT((B), (C))) { \
> > MOV((T), (B)); \
> > if (GT((A), (C))) { \
> > MOV((B), (A)); \
> > MOV((A), (C)); \
> > } else { \
> > MOV((B), (C)); \
> > } \
> > MOV((C), (T)); \
> > } \
> > }
> >
> > #define SIFTDOWNM(P) \
> > { \
> > parent = (P); \
> > child = parent * 2; \
> > MOV(&temp, array + parent); \
> > while (nmemb - parent > parent) { \
> > if (GT(array + child + 1, array + child)) { \
> > ++child; \
> > } \
> > if (GT(array + child, &temp)) { \
> > MOV(array + parent, array + child); \
> > parent = child; \
> > child *= 2; \
> > } else { \
> > break; \
> > } \
> > } \
> > if (nmemb == child && GT(array + child, &temp)) { \
> > MOV(array + parent, array + child); \
> > parent = child; \
> > } \
> > MOV(array + parent, &temp); \
> > }
> >
> > typedef E_TYPE;
> >
> > static void sisort(e_type *array, size_t nmemb)
> > {
> > e_type *base, *low, *high, temp;
> >
> > if (nmemb-- > 1) {
> > base = array;
> > do {
> > low = array++;
> > if (GT(low, array)) {
> > high = array;
> > MOV(&temp, high);
> > do {
> > MOV(high, low);
> > if (--high == base) {
> > break;
> > }
> > --low;
> > } while (GT(low, &temp));
> > MOV(high, &temp);
> > }
> > } while (--nmemb != 0);
> > }
>
> This part is the heap sort here.
> In my experience this is good in sorting for more than 30 elelments.
>
> If the length of the unsorted array is considered, then one might need
> 3 to 4 sorting procedures to cover the desired range of the lengths of the arrays for the critical part.
sisort is an insertion sort.
hsortm is a heap sort.
QSORT, as implemented in this post, is an introsort.
The purpose of the heap sort is to take over
and keep the sort O(N*log(N))
in case of the quick sort starting to go quadratic.
http://en.wikipedia.org/wiki/Introsort
> > static void jnloop(e_type *array, size_t nmemb, size_t d)
> > {
> > e_type *i, *j, temp;
> >
> > while (nmemb > SMALL_PARTITION) {
> > if (!d--) {
> > hsortm(array, nmemb);
> > return;
> > }
> > i = nmemb / 2 + array;
> > SWAP(array, i, &temp);
> > i = 1 + array;
> > j = --nmemb + array;
> > SORT_3(j, array, i, &temp);
> > do {
> > SWAP(j, i, &temp);
> > do {
> > ++i;
> > } while (GT(array, i));
> > do {
> > --j;
> > } while (GT(j, array));
> > } while (j > i);
> > SWAP(array, j, &temp);
> > jnloop(j + 1, nmemb + array - j, d);
> > nmemb = j - array;
> > }
> > sisort(array, nmemb);
> > }
> >
> > static void hsortm(e_type *array, size_t nmemb)
> > {
> > size_t p, child, parent;
> > e_type temp;
> >
> > if (nmemb > 1) {
> > p = --nmemb / 2;
> > do {
> > SIFTDOWNM(p);
> > } while (p-- != 0);
> > SWAP(array, array + nmemb, &temp);
> > while (--nmemb != 0) {
> > SIFTDOWNM(0);
> > SWAP(array, array + nmemb, &temp);
> > }
> > }
> > }
> >
> > static void QSORT(e_type *array, size_t nmemb)
> > {
> > size_t d, n;
> >
> > assert(SMALL_PARTITION >= 4);
> > d = 2;
> > for (n = nmemb / 4; n != 0; n /= 2) {
> > ++d;
> > }
> > jnloop(array, nmemb, 2 * d);
> > }
> >
> > static int Sort(LIST_TYPE * l)
> > {
> > LIST_ELEMENT **tab;
> > size_t i;
> > LIST_ELEMENT *rvp;
> >
> > if (l == NULL)
> > return iError.NullPtrError("Sort");
> >
> > if (l->count < 2)
> > return 1;
> > if (l->Flags & CONTAINER_READONLY) {
> > l->RaiseError("iList.Sort", CONTAINER_ERROR_READONLY);
> > return CONTAINER_ERROR_READONLY;
> > }
> > tab = l->Allocator->malloc(l->count * sizeof(LIST_ELEMENT *));
> > if (tab == NULL) {
> > l->RaiseError("iList.Sort", CONTAINER_ERROR_NOMEMORY);
> > return CONTAINER_ERROR_NOMEMORY;
> > }
> > rvp = l->First;
> > for (i = 0; i < l->count; i++) {
> > tab[i] = rvp;
> > rvp = rvp->Next;
> > }
> > QSORT(tab, l->count );
> > for (i = 0; i < l->count - 1; i++) {
> > tab[i]->Next = tab[i + 1];
> > }
> > tab[l->count - 1]->Next = NULL;
> > l->Last = tab[l->count - 1];
> > l->First = tab[0];
> > l->Allocator->free(tab);
> > return 1;
> >
--
pete
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 13:38 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 14:20 +0200
Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-04 15:32 +0000
Re: Breakthrough Ike Naar <ike@iceland.freeshell.org> - 2012-06-04 15:44 +0000
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 18:03 +0200
Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:23 +1200
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:31 +0200
Re: Breakthrough Luca Risolia <luca.risolia@studio.unibo.it> - 2012-06-05 01:43 +0200
Re: Breakthrough Martin Shobe <martin.shobe@yahoo.com> - 2012-06-05 00:26 +0000
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 17:47 +0200
Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-05 05:36 +0000
Re: Breakthrough Paul <nospam@needed.com> - 2012-06-04 12:32 -0400
Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 21:44 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 22:01 +0200
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 22:42 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:16 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:47 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 03:34 +0200
Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-06 17:28 -0700
Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 17:30 +0100
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 19:30 +0200
Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 19:18 +0100
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 20:50 +0200
Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-05 00:31 +0100
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-04 17:23 -0400
Re: Breakthrough Noob <root@localhost> - 2012-06-05 09:10 +0200
Re: Breakthrough Ike Naar <ike@sverige.freeshell.org> - 2012-06-05 08:03 +0000
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 00:20 -0400
Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 00:06 -0500
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 09:10 -0400
Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 09:23 -0500
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 19:49 -0400
Re: Breakthrough Willem <willem@toad.stack.nl> - 2012-06-07 15:10 +0000
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-08 01:37 +0200
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 09:55 -0400
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 21:26 -0400
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-09 23:49 -0400
Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-11 06:50 -0700
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-11 22:36 -0400
Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:02 +1200
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:26 +0200
csiph-web