Breakthrough

[Noob]

I've never needed the three way comparison
to implement any sorting algorithm.

It has always been sufficient for me
to merely use a (Greater Than) macro, GT(A, B),
to implement any sorting algorithm.

#define GT(A, B) ((*A)->Data > (*B)->Data)

I have never needed to know whether two keys compare equal,
in order to implement a sorting algorithm.

Perhaps it is needed when writing "stable" sorting algorithms?
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

 

[Ike Naar]

Perhaps it is needed when writing "stable" sorting algorithms?
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Equality of A and B follows from

!(GT(A, B) || GT(B, A))

provided that GT defines a total order.

 

[88888 Dihedral]

Juha Nieminenæ–¼ 2012å¹´6月4日星期一UTC+8下åˆ11時32分34秒寫é“：

Your test is basically useless as a measurement of sorting speed because
the vast majority of the time will be spent on those push_back() calls.

If you want to test sorting speed and nothing else, you have to discard
the time spent in memory allocation.

For known numeric types of arrays to be sorted, then the radix sort is
faster if the allocation of the memory does not slow down a lot.illion

The problem is for the size of 100 million elements. I sugest
one can sort from the first digit of 8 to 12 bits for the first 2 or 3 digits.


Then one can sort those with the same prefax chunk by the traditional radix
sort if necessary, thus the cache hit rate is increased in all passes of digits.








Juha Nieminenæ–¼ 2012å¹´6月4日星期一UTC+8下åˆ11時32分34秒寫é“：

 

[Willem]

pete wrote:
) Anyway,
) the point that I was was originally trying to make to Jacob Navia,
) still stands; Which is,
) that I have never needed anything else but a GreaterThan macro,
) to implement any kind of comparison sorting algorithm,
) stable or otherwise.

Speaking theoretically: You can implement an 'Equals' macro in terms
of a 'GreaterThan' macro easily, so all you need is 'GreaterThan'.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[jacob navia]

Le 07/06/12 01:49, pete a écrit :

Anyway,
the point that I was was originally trying to make to Jacob Navia,
still stands; Which is,
that I have never needed anything else but a GreaterThan macro,
to implement any kind of comparison sorting algorithm,
stable or otherwise.

Maybe you have some spare time?

I am convinced my code would benefit from your critical eye Pete.

Just download it from

http://code.google.com/p/ccl/

and look at it. The file listgen.c contains the templated sort function.

 

[88888 Dihedral]

peteæ–¼ 2012å¹´6月10日星期日UTC+8上åˆ11時49分21秒寫é“：

/*
** On 6 September 2008, I posted pqsort.
**
** http://groups.google.com/group/comp.lang.c/msg/6a73e359f4814457
**
** 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.
** Try it.
*/
/* BEGIN listgen.c */
/*
* Value types generic list routines sample implementation
* ----------------------------------- ------------------
* Thisroutines handle the List container class. This is a very general
* implementation and efficiency considerations aren't yet primordial.
Lists
* can have elements of any size. This implement single linked Lists.
The
* design goals here are just correctness and showing how the
implementation
* of the proposed interface COULD be done.
*
----------------------------------------------------------------------
*/

#include "listgen.h"
#include "ccl_internal.h"

#include <assert.h>

/* Forward declarations */
static LIST_TYPE *SetVTable(LIST_TYPE *result);
static LIST_TYPE * Create(size_t elementsize);
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator);
#define CONTAINER_LIST_SMALL 2
#define CHUNK_SIZE 1000

static int DefaultListCompareFunction(const void * left, const void *
right, CompareInfo * ExtraArgs)
{
size_t siz = ((LIST_TYPE *)
ExtraArgs->ContainerLeft)->ElementSize;
return memcmp(left, right, siz);
}

/*------------------------------------------------------------------------
Procedure: Contains ID:1
Purpose: Determines if the given data is in the container
Input: The list and the data to be searched
Output: Returns 1 (true) if the data is in there, false
otherwise
Errors: The same as the function IndexOf
------------------------------------------------------------------------*/
static int Contains(const LIST_TYPE * l, const DATA_TYPE data)
{
size_t idx;
return (iList.IndexOf((List *)l, &data, NULL, &idx) < 0) ? 0 : 1;
}

static int Add(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.Add((List *)l,&elem);
}

/*------------------------------------------------------------------------
Procedure: GetElement ID:1
Purpose: Returns the data associated with a given position
Input: The list and the position
Output: A pointer to the data
Errors: NULL if error in the positgion index
------------------------------------------------------------------------*/
static DATA_TYPE GetElement(const LIST_TYPE * l, size_t position)
{
DATA_TYPE *pdata = iList.GetElement((List *)l,position);

if (pdata == NULL) return ERROR_RETURN;
return *pdata;
}

static DATA_TYPE Back(const LIST_TYPE * l)
{
DATA_TYPE *p = (DATA_TYPE *)iList.Back((List *)l);
if (p == NULL) return ERROR_RETURN;
return *p;
}

static DATA_TYPE Front(const LIST_TYPE * l)
{
DATA_TYPE *p = (DATA_TYPE *)iList.Front((List *)l);
if (p == NULL) return ERROR_RETURN;
return *p;
}

static int CopyElement(const LIST_TYPE * l, size_t position, DATA_TYPE
*outBuffer)
{
return iList.CopyElement((List *)l,position,outBuffer);
}

static int ReplaceAt(LIST_TYPE * l, size_t position, const DATA_TYPE
data)
{
return iList.ReplaceAt((List *)l,position,&data);;
}

static int PushFront(LIST_TYPE * l, const DATA_TYPE pdata)
{
return iList.PushFront((List *)l,&pdata);
}


static int PopFront(LIST_TYPE * l, DATA_TYPE *result)
{
return iList.PushFront((List *)l,result);
}


static int InsertAt(LIST_TYPE * l, size_t pos, const DATA_TYPE pdata)
{
return iList.InsertAt((List *)l,pos,&pdata);
}

static int Erase(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.Erase((List *)l, &elem);
}

static int EraseAll(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.EraseAll((List *)l, &elem);
}

static int IndexOf(const LIST_TYPE * l, const DATA_TYPE ElementToFind,
void *ExtraArgs, size_t * result)
{
return iList.IndexOf((List *)l, &ElementToFind, ExtraArgs, result);
}

static size_t Sizeof(const LIST_TYPE * l)
{
if (l == NULL) {
return sizeof(List);
}
return sizeof(LIST_TYPE) + l->ElementSize * l->count + l->count *
offsetof(LIST_ELEMENT,Data);
}

static size_t SizeofIterator(const LIST_TYPE * l)
{
return sizeof(struct ITERATOR(DATA_TYPE));
}

static LIST_TYPE *Load(FILE * stream, ReadFunction loadFn, void *arg)
{
LIST_TYPE *result = (LIST_TYPE *)iList.Load(stream,loadFn,arg);
return SetVTable(result);
}

/*
*
---------------------------------------------------------------------------
*
* Iterators
*
*
---------------------------------------------------------------------------
*/
static int ReplaceWithIterator(Iterator * it, DATA_TYPE data, int
direction)
{
struct ITERATOR(DATA_TYPE) *iter = (struct ITERATOR(DATA_TYPE) *)it;
return iter->ListReplace(it,&data,direction);
}

static Iterator *SetupIteratorVTable(struct ITERATOR(DATA_TYPE) *result)
{
if (result == NULL) return NULL;
result->ListReplace = result->it.Replace;
result->it.Replace = (int (*)(Iterator * , void * , int
))ReplaceWithIterator;
return &result->it;
}

static Iterator *NewIterator(LIST_TYPE * L)
{
return SetupIteratorVTable((struct ITERATOR(DATA_TYPE)
*)iList.NewIterator((List *)L));
}
static int InitIterator(LIST_TYPE * L, void *r)
{
iList.InitIterator((List *)L,r);
SetupIteratorVTable(r);
return 1;
}
static size_t GetElementSize(const LIST_TYPE * l)
{
return sizeof(DATA_TYPE);
}

static int Finalize(LIST_TYPE *l)
{
iList.Finalize((List *)l);
return 1;
}

static LIST_TYPE *Copy(const LIST_TYPE * l)
{
LIST_TYPE *result = (LIST_TYPE *)iList.Copy((List *)l);
return SetVTable(result);
}


static LIST_TYPE *SelectCopy(const LIST_TYPE *l,const Mask *m)
{
LIST_TYPE *result = (LIST_TYPE *)iList.SelectCopy((const List
*)l,m);
return SetVTable(result);
}

/*---------------------------------------------------------------------------*/
/* 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.

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 = rvp;
rvp = rvp->Next;
}
QSORT(tab, l->count );
for (i = 0; i < l->count - 1; i++) {
tab->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;

}
static LIST_TYPE *SetVTable(LIST_TYPE *result)
{
static int Initialized;
INTERFACE(DATA_TYPE) *intface = &INTERFACE_NAME(DATA_TYPE);

result->VTable = intface;
if (Initialized) return result;
Initialized = 1;
intface->FirstElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.FirstElement;
intface->LastElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.LastElement;
intface->Clear = (int (*)(LIST_TYPE *))iList.Clear;
intface->EraseAt = (int (*)(LIST_TYPE *,size_t))iList.EraseAt;
intface->RemoveRange = (int (*)(LIST_TYPE
*,size_t,size_t))iList.RemoveRange;
intface->Select = (int (*)(LIST_TYPE *,const Mask *))iList.Select;
intface->SetFlags = (unsigned (*)(LIST_TYPE
*,unsigned))iList.SetFlags;
intface->GetFlags = (unsigned (*)(const LIST_TYPE *))iList.GetFlags;
intface->SetDestructor = (DestructorFunction (*)(LIST_TYPE *,
DestructorFunction))iList.SetDestructor;
intface->Apply = (int (*)(LIST_TYPE *, int (Applyfn) (DATA_TYPE *,
void * ), void *))iList.Apply;
intface->Reverse = (int (*)(LIST_TYPE *))iList.Reverse;
intface->SetCompareFunction = (CompareFunction (*)(LIST_TYPE *,
CompareFunction ))iList.SetCompareFunction;
intface->GetRange = (LIST_TYPE *(*)(const LIST_TYPE * , size_t,
size_t))iList.GetRange;
intface->Skip = (LIST_ELEMENT *(*)(LIST_ELEMENT *,
size_t))iList.Skip;
intface->Append = (int (*)(LIST_TYPE *, LIST_TYPE *))iList.Append;
intface->Equal = (int (*)(const LIST_TYPE *, const LIST_TYPE
*))iList.Equal;
intface->InsertIn = (int (*)(LIST_TYPE *, size_t, LIST_TYPE
*))iList.InsertIn;
intface->AddRange = (int (*)(LIST_TYPE *, size_t, const DATA_TYPE
*))iList.AddRange;
intface->SetErrorFunction = (ErrorFunction (*)(LIST_TYPE *,
ErrorFunction))iList.SetErrorFunction;
intface->SetFlags = (unsigned (*)(LIST_TYPE * l, unsigned
newval))iList.SetFlags;
intface->RemoveRange = (int (*)(LIST_TYPE *, size_t,
size_t))iList.RemoveRange;
intface->UseHeap = (int (*)(LIST_TYPE *, const ContainerAllocator
*))iList.UseHeap;
intface->RotateLeft = (int (*)(LIST_TYPE *,
size_t))iList.RotateLeft;
intface->RotateRight = (int (*)(LIST_TYPE *,
size_t))iList.RotateRight;
intface->Save = (int (*)(const LIST_TYPE *, FILE *, SaveFunction,
void *))iList.Save;
intface->Size = (size_t (*)(const LIST_TYPE *))iList.Size;
intface->deleteIterator = (int (*)(Iterator *))iList.deleteIterator;
intface->SplitAfter = (LIST_TYPE *(*)(LIST_TYPE *, LIST_ELEMENT
*))iList.SplitAfter;
return result;
}

/*------------------------------------------------------------------------
Procedure: Create ID:1
Purpose: Allocates a new list object header, initializes the
VTable field and the element size
Input: The size of the elements of the list.
Output: A pointer to the newly created list or NULL if
there is no memory.
Errors: If element size is smaller than zero an error
routine is called. If there is no memory result is
NULL.

------------------------------------------------------------------------*/
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), allocator);
return SetVTable(result);
}

static LIST_TYPE * Create(size_t elementsize)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), CurrentAllocator);
return SetVTable(result);
}

static LIST_TYPE *InitializeWith(size_t elementSize, size_t n, const
void *Data)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.InitializeWith(sizeof(DATA_TYPE),n,Data);
return SetVTable(result);
}

static LIST_TYPE *InitWithAllocator(LIST_TYPE * result, size_t
elementsize,
const ContainerAllocator * allocator)
{
iList.InitWithAllocator((List *)result,sizeof(DATA_TYPE),allocator);
return SetVTable(result);
}

static LIST_TYPE * Init(LIST_TYPE * result, size_t elementsize)
{
return InitWithAllocator(result, elementsize, CurrentAllocator);
}

static const ContainerAllocator *GetAllocator(const LIST_TYPE * l)
{
if (l == NULL)
return NULL;
return l->Allocator;
}

static LIST_ELEMENT *NextElement(LIST_ELEMENT *le)
{
if (le == NULL) return NULL;
return le->Next;
}

static DATA_TYPE ElementData(LIST_ELEMENT *le)
{
if (le == NULL) return ERROR_RETURN;
return le->Data;
}

static int SetElementData(LIST_TYPE *l,LIST_ELEMENT *le,DATA_TYPE data)
{
return iList.SetElementData((List *)l,(ListElement *)le,&data);
}

static DATA_TYPE Advance(LIST_ELEMENT **ple)
{
LIST_ELEMENT *le;
DATA_TYPE result;

if (ple == NULL) {
iError.NullPtrError("Advance");
return ERROR_RETURN;
}
le = *ple;
if (le == NULL) return ERROR_RETURN;
result = le->Data;
le = le->Next;
*ple = le;
return result;
}

INTERFACE(DATA_TYPE) INTERFACE_NAME(DATA_TYPE) = {
NULL, // Size
NULL, // GetFlags,
NULL, // SetFlags,
NULL, // Clear,
Contains,
Erase,
EraseAll,
Finalize,
NULL, // Apply
NULL, // Equal
Copy,
NULL, // SetErrorFunction,
Sizeof,
NewIterator,
InitIterator,
NULL, // deleteIterator,
SizeofIterator,
NULL, // Save,
Load,
GetElementSize,
/* end of generic part */
Add,
GetElement,
PushFront,
PopFront,
InsertAt,
NULL, // EraseAt
ReplaceAt,
IndexOf,
/* End of sequential container part */
NULL, // InsertIn,
CopyElement,
NULL, // EraseRange,
Sort,
NULL, // Reverse,
NULL, // GetRange,
NULL, // Append,
NULL, // SetCompareFunction,
DefaultListCompareFunction,
NULL, // UseHeap,
NULL, // AddRange,
Create,
CreateWithAllocator,
Init,
InitWithAllocator,
GetAllocator,
NULL, // SetDestructor
InitializeWith,
Back,
Front,
NULL, // RemoveRange,
NULL, // RotateLeft,
NULL, // RotateRight,
NULL, // Select,
SelectCopy,
NULL, // FirstElement,
NULL, // LastElement,
NextElement,
ElementData,
SetElementData,
Advance,
NULL, // Skip,
NULL, // SplitAfter,
};
/* END listgen.c */