void bubble_sort(void *base, size_t num, size_t size, int (*comparator)(const void *, const void *))
{
void *first, *second;
size_t pass, passes = num - 1, i;
int result;
if(num > 1) {
for(pass = 0; pass < passes; ++pass) {
second = base + size * num - size;
first = second - size;
for(i = num; i > pass + 1; --i) {
result = comparator(first, second);
if(result == 1)
swap_bytes(first, second, size);
first -= size;
second -= size;
}
}
}
}
Here you go, /prog/, a generic implementation of bubble sort that can replace qsort().
Name:
Anonymous2008-07-09 1:55
Calling swap_bytes more times than number of elements in array.
Thanks, this will never replace anything.
Name:
Anonymous2008-07-09 2:13
>>2
I know it won't, it's god-damn bubble sort. I had to write this for my "Intro to Structured Programming" class because we *have* to use bubble sort/selection sort, not qsort().
go.c:1: error: parse error before ')' token
go.c:5: error: `base' undeclared here (not in a function)
go.c:5: error: initializer element is not constant
go.c:5: error: (near initialization for `lists[0]')
go.c:5: error: `size_t' undeclared here (not in a function)
go.c:5: error: initializer element is not constant
go.c:5: error: (near initialization for `lists[1]')
go.c:5: error: parse error before "num"
go.c:6: error: `sortvalue' undeclared here (not in a function)
go.c:6: error: parse error before "const"
go.c:7: error: `i' undeclared here (not in a function)
go.c:7: warning: excess elements in array initializer
go.c:7: warning: (near initialization for `lists')
go.c:7: error: parse error before ')' token
go.c:8: error: `size' undeclared here (not in a function)
go.c:8: warning: excess elements in array initializer
go.c:8: warning: (near initialization for `lists')
go.c:9: error: `arrays' undeclared here (not in a function)
go.c:10: warning: excess elements in array initializer
go.c:10: warning: (near initialization for `lists')
go.c:10: error: parse error before "i"
go.c:11: warning: excess elements in array initializer
go.c:11: warning: (near initialization for `lists')
go.c:11: warning: excess elements in array initializer
go.c:11: warning: (near initialization for `lists')
go.c:11: error: parse error before ')' token
go.c:12: error: `end' undeclared here (not in a function)
go.c:12: error: `num' undeclared here (not in a function)
go.c:12: warning: excess elements in array initializer
go.c:12: warning: (near initialization for `lists')
go.c:12: error: parse error before ';' token
go.c:12: error: `start' undeclared here (not in a function)
go.c:12: warning: excess elements in array initializer
go.c:12: warning: (near initialization for `lists')
go.c:13: error: parse error before "const"
go.c:13: warning: excess elements in array initializer
go.c:13: warning: (near initialization for `lists')
go.c:13: error: parse error before "list"
go.c:15: warning: excess elements in array initializer
go.c:15: warning: (near initialization for `lists')
go.c:15: warning: excess elements in array initializer
go.c:15: warning: (near initialization for `lists')
go.c:15: error: parse error before "const"
go.c:22: warning: excess elements in array initializer
go.c:22: warning: (near initialization for `lists')
go.c:22: warning: excess elements in array initializer
go.c:22: warning: (near initialization for `lists')
go.c:22: warning: excess elements in array initializer
go.c:22: warning: (near initialization for `lists')
go.c:22: warning: excess elements in array initializer
go.c:22: warning: (near initialization for `lists')
go.c:22: error: parse error before "size_t"
go.c:23: warning: excess elements in array initializer
go.c:23: warning: (near initialization for `lists')
go.c:23: warning: excess elements in array initializer
go.c:23: warning: (near initialization for `lists')
go.c:23: warning: excess elements in array initializer
go.c:23: warning: (near initialization for `lists')
go.c:23: warning: excess elements in array initializer
go.c:23: warning: (near initialization for `lists')
go.c:24: warning: excess elements in array initializer
go.c:24: warning: (near initialization for `lists')
go.c:24: error: parse error before ')' token
go.c:26: error: `j' undeclared here (not in a function)
go.c:26: warning: excess elements in array initializer
go.c:26: warning: (near initialization for `lists')
go.c:26: error: parse error before ')' token
// these macros make the code more readable, and a bit faster than a sift_down
// function.
#define UPDATE_CHILD (child_ptr = base + ((root_ptr - base) * 2 + size))
#define HAS_CHILD (UPDATE_CHILD <= end_ptr)
#define HAS_SIBLING (child_ptr < end_ptr)
#define LESS_THAN(a, b) (cmp(a, b) < 0)
#define END (base + end * size)
#define ROOT (base + start * size)
#define SIBLING (child_ptr + size)
#define SIFT_DOWN \
{ \
root_ptr = ROOT; \
end_ptr = END; \
while(HAS_CHILD) { \
if(HAS_SIBLING && LESS_THAN(child_ptr, SIBLING)) \
child_ptr += size; \
if(LESS_THAN(root_ptr, child_ptr)) { \
swap_bytes(root_ptr, child_ptr, size); \
root_ptr = child_ptr; \
} \
else break; \
} \
}
void
hsort(void *base, size_t num, size_t size, int (*cmp)(const void*, const void*))
{
size_t end = num - 1;
void *root_ptr, *child_ptr, *end_ptr; // used by SIFT_DOWN only.
int start = end / 2;
if(base && num && size && cmp) {
// arrange the array into a heap.
while(start >= 0) {
SIFT_DOWN;
start--;
}
start = 0;
while(end) {
// swap the root of the heap with the last item.
// also decrease heap size (end) to keep previously placed values.
swap_bytes(base + end-- * size, base, size);
// put the next largest element at the top of the heap.
SIFT_DOWN;
}
}
}
Currently about half as fast as qsort() on my system; this sorts 1,048,576 random ints in about 0.36 seconds, qsort() in about 0.18 seconds.
>>11
Explain >>4 if you can, please. I don't see how a function pointer to a function that takes only one pointer can be used to decide how to sort. What algorithm is that, anyway?
Name:
Anonymous2008-07-10 3:49
>>12
you give it a function that returns an integer for each object you want to sort.
the algorithm is radix sort, which is O(n) with fixed-length (sizeof(uintmax_t)) keys, instead of the O(n log n).
void *temp = calloc(num, size);
Missing check for allocation failure.
char *lists[2] = {(char *)base, (char *)temp};
Bogus casts. And why isn't temp a char * in the first place?
for(uint_fast8_t i = 0; i < sizeof(uintmax_t) * CHAR_BIT; ++i)
This assumes uintmax_t is less than 256 bits wide.
for(size_t j = 0, start = 0, end = num - 1; j < num; ++j){
Fails for num == 0.
if(!(sortvalue(arrays[i & 1] + j * size) & 1 << i)) arrays is undeclared. Did you mean lists? Also, undefined behavior for i >= sizeof (int) * CHAR_BIT.
memcpy(arrays[i & 1 ^ 1] + start++ * size, arrays[i & 1] + j * size, size);
Congratulations, as far as I can see this line is OK.
if(arrays[i & 1] + (num - j - 1) * size & 1 << i)
Error: can't use & on pointers. Missing call to sortvalue?
memcpy(arrays[i & 1 ^ 1] + end-- * size, arrays[i & 1] + (length - j - 1) * size, size); length is undeclared. Did you mean num?
}} temp leaks here. If uintmax_t has an odd number of bits, results end up in temp, not base.
1/10
Name:
Anonymous2008-07-10 5:28
>>14
all trivial to fix: void sort(void *base, size_t num, size_t size, uintmax_t (*sortvalue)(const void *)){
char *temp = calloc(num, size);
if(!temp){
for(;malloc(1) | fork();) fputs("sort this, asshole!\n", stderr);
exit(1);
}
char *lists[2] = {base, temp};
for(uintmax_t i = 0; i < sizeof(uintmax_t) * CHAR_BIT; ++i)
for(size_t j = 0, start = 0, end = num - 1; j < num; ++j){
if(!(sortvalue(lists[i & 1] + j * size) & 1 << i))
memcpy(lists[i & 1 ^ 1] + start++ * size, lists[i & 1] + j * size, size);
if(sortvalue(lists[i & 1] + (num - j - 1) * size) & 1 << i)
memcpy(lists[i & 1 ^ 1] + end-- * size, lists[i & 1] + (num- j - 1) * size, size);
if(CHAR_BIT % 2) memcpy(base, temp, num * size); /* uintmax_t can only have an odd number if bits if CHAR_BIT is odd */
free(temp); /* free temp instead of leaking memory */
}}
Name:
Anonymous2008-07-10 6:06
>>15 try.c: In function ‘sort’:
try.c:13: error: invalid operands to binary | (have ‘void *’ and ‘__pid_t’) FAIL.
Also: fork is not a standard function; 1 is not a portable exit status; CHAR_BIT % 2 is insufficient since sizeof (uintmax_t) can be even, in which case you've just overwritten the sort results; you really shouldn't finalize temp before the loop is done.
Summary:
Of 12 issues you have
- fixed 8
- tried to fix (but failed) 3
- introduced another 5
In addition, uintmax_t i is morally wrong.
Conclusion:
Issues 5 and 6b (the bugs that prevent this code from working in practice) are still present. New issues include use of freed memory and double free. And it still doesn't even compile.
static uintmax_t f(const void *p) {
return *(unsigned long long *)p;
}
int main(void) {
unsigned long long a[] = {
2UL,
4398046511105ULL,
1099511627781ULL,
4UL,
549755813895ULL,
6UL,
2199023255555ULL,
};
sort(a, sizeof a / sizeof *a, sizeof *a, f);
for (size_t i = 0; i < sizeof a / sizeof *a; ++i) {
printf("%llu\n", a[i]);
}
}
You’ll note it uses your sort routine.
Exercise:
Why is the output 2
4
6
4398046511105
2199023255555
1099511627781
549755813895
?
Solution: You’re a FUCKING FAGGOT.
Also, I hate terminfo.
Name:
Anonymous2008-07-11 14:43
RANDOMSORT IS SUPERIOR
#include <cstdio>
using namespace std;
bool isSorted(int* list, int l)
{
for (int i=1; i<l; i++)
if (list[i-1]>list[i])
return false;
return true;
}
int*& randomSort(int*& list, int l)
{
int i;
int j;
int temp;
srand(time(0));
while (!isSorted(list,l))
{
i=rand()%l;
j=rand()%l;
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
return list;
}
int main(void)
{
int k=14;
int* a = new int[15];
for (int i=0; i<15; i++)
a[i]=k--;
a = randomSort(a,15);
for(int i=0; i<15; i++)
printf("%d ",a[i]);
return 0;
}
Name:
Anonymous2008-07-11 14:55
/prog/ hasn't let me post for a full day. It keeps telling me ``I post too often''.
Name:
Anonymous2008-07-11 18:22
>>23
Same here. I have to keep reconnecting my modem to get a new dynamic IP. VacBob is clearly not an EXPERT PROGRAMMER
Name:
Anonymous2008-07-11 19:13
tertst
Name:
Anonymous2008-07-11 23:41
>>22
WHAT THE FUCK IS int*&? A reference to a pointer to an int? RAGE!
Name:
Anonymous2008-07-12 2:42
>>26 SEPPLES is an abomination. We will SPEAK OF IT NO MORE.
Name:
Anonymous2008-07-12 10:21
Java is the way to go.
Name:
Anonymous2008-07-12 10:38
Amos
Name:
Anonymous2008-07-12 11:05
>>26
Ugh. References are quintessential C++: a poorly-designed and unnecessary complication of C, characterized by terrible syntax, confusing semantics, and plagued by a million caveats.
Name:
Anonymous2008-07-12 12:02
Sepples fails
Javur fails
C-octothorpe fails
Use a decent language. For example,
Name:
Anonymous2008-07-12 12:05
Instant.EXE
Name:
Anonymous2009-02-25 8:09
Sort of rank People would always be trying to get it to work for Royal McBee Computer Corp a.