christian.bau wrote:
I think you're talking about a different version of
bubble sort from the one that was posted in this thread.
Knuth describes bubble sort as being O(N*N) for both
worst case and average case, but O(N) for best case.
The bubble sort posted by OP, sort_bub,
is just O(N*N) for everything.
void sort_bub(int a, int l, int r)
{
int i, n;
for (; l < r; r--)
for (i = l; i < r; i++)
if (a[i] > a[i + 1]){
n = a[i];
a[i] = a[i + 1];
a[i + 1] = n;
}
}
I don't understand why even a good bubble sort
would be faster than insertion sort for the
"one well-known situation" which you describe.
When insertion sort is implemented as an exchange type
of sorting algorithm, it takes the same number of exchanges
to sort an array as bubble sort does.
Insertion sort never requires more array element value
comparisons than bubble sort does; so if
bubble sort were to outperform insertion sort,
it would have to be that the book keeping part
of the implementation of the algorithm was more efficient,
or that I'm not understanding you correctly.
When insertion sort is implemented as a daisy chaining
algorithm, instead of as an exchange type,
(consider sisort vs. i_sort)
then it is even harder for me to envision a case
where a bubble sort could outperform it.
#define E_TYPE long unsigned
#define GT(A, B) (*(A) > *(B))
typedef E_TYPE e_type;
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;
temp = *high;
do {
*high-- = *low;
if (low == base) {
break;
}
--low;
} while (GT(low, &temp));
*high = temp;
}
} while (--nmemb != 0);
}
}
void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low, *p1, *p2, *end, swap;
if (nmemb-- > 1) {
array = base;
do {
low = array;
array += size;
high = array;
while (compar(low, high) > 0) {
p1 = low;
p2 = high;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}
I don't think there's any way that any bubble sort function
could outperform a bubble insertion sort hybrid like sisor2.
void sisor2(e_type *array, size_t nmemb)
{
e_type *low, *high, temp;
if (nmemb-- > 1) {
low = array + nmemb;
do {
high = low--;
if (GT(low, high)) {
temp = *high;
*high = *low;
*low = temp;
}
} while (low != array);
if (nmemb-- > 1) {
++array;
do {
low = array++;
if (GT(low, array)) {
high = array;
temp = *high;
do {
*high-- = *low--;
} while (GT(low, &temp));
*high = temp;
}
} while (--nmemb != 0);
}
}
}
The point of the hybrid, is that the initial bubblesort pass,
eliminates the need for the break statement in the insertion sort part.
Followup To: comp.programming
--
pete
