Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Mon, 11 Jun 2012 21:36:21 -0500 Message-ID: <4FD6AB24.F3D@mindspring.com> Date: Mon, 11 Jun 2012 22:36:20 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: Breakthrough References: <4FCD273B.5095@mindspring.com> <4fcdb0ef$0$6481$426a74cc@news.free.fr> <4FCEDA85.66BA@mindspring.com> <4FCF56CD.962@mindspring.com> <98pus75mg8q054gcv696u78gvg7gs6h1nk@4ax.com> <4FCFEC9A.C74@mindspring.com> <4FD41941.2DB0@mindspring.com> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Lines: 221 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.156.228.87 X-Trace: sv3-NUTVEfCaeXWnNEgPJS/U3/JFy8vvrMIcSH3+T9GBgQqudfT5+SXFv02jdaIWpaM5mtnyRYhLDgjpyu0!irlKT55LcEQYDxw3nyGmwNe5GIIlxwbQWOYkGRjB0Sg+ox+cqmQkc1DD+uy0qH2VQ9/+AcWrvvTW!LWSxK1/y X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 9531 X-Received-Bytes: 9672 Xref: csiph.com comp.lang.c:22131 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