pete
4/24/2011 3:59:00 PM
Eric Sosman wrote:
>
> On 4/24/2011 3:13 AM, C learner wrote:
> > Why calculation of complexity of various algorithms(Linear search,
> > bubble sort) confined to number of comparisons,
> > whereas the arithmetic
> > operations and other operations are not considered,
> > though these also
> > may eat significant processing power.
>
> Your question isn't about the C programming language, nor about
> any particular programming language, and probably belongs in a forum
> like comp.programming.
>
> ... but for what it's worth, try the analysis yourself. Take
> some simple algorithm, implement it, study the machine instructions
> that it generates, and try to predict how much time it will take.
Binary insertion sort uses O(n * log(n)) comparisons,
but O(n * n) data movement, and runs in O(n * n) time.
#include <stddef.h>
void
bisort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
if (nmemb-- > 1) {
size_t n;
size_t low, middle, high;
size_t bytes = 0;
const size_t odd_size = size ^ size - 1;
unsigned char *const array = base;
unsigned char *key = array;
do {
low = 0;
key += size;
bytes += size;
high = bytes;
do {
n = high - low;
middle = ((n & odd_size ? n - size : n) >> 1) + low;
if (0 > compar(key, middle + array)) {
high = middle;
} else {
low = middle;
}
} while (n != size);
base = array + high;
if (base != key) {
unsigned char *end = key;
unsigned char *after = end + size;
do {
const unsigned char swap = *--end;
*end = *--after;
*after = swap;
} while (end != base);
}
} while (--nmemb != 0);
}
}
--
pete