last day (15 days later) » 

23:28
0
Q: Why does my data structure heap sort break at 5761 numbers to sort?

Chris SilverI was asked to sort 50,000 random integers (from 0 to 1000) with heap sort, bubble sort, and selection sort, to see which method is most efficient. My bubble and selection sort works fine, but I noticed my heap sort did not sort correctly. I re-used my heap sort from another program and it worked...

You might be running out of stack space.
Further to @SteveSummit's point, you may want to change your local variables to use dynamic allocations (e.g. malloc) instead of allocating the whole array on the stack.
Re: numerical relevance - if you take 666, multiply it by 9 (a perfect square, BTW), and then subtract 233 (the fifty-first prime number, so it's a prime prime - and 5 is the first digit of 5761, while 1 is the last digit of 5761!!), you get 5761, which can hardly be a coincidence!
The global variable last should be a local variable in main(). The global variable heapcount seems to be some sort of call monitoring counter.
23:28
When you say it doesn't work, what doesn't work with it? Is the program crashing? Is it hanging? Is it completing, but not sorting correctly? We need more information before we can diagnose the problem.
the posted code is missing the statement: #include <stdlib.h> for the rand() function
regarding: rightKey = NULL; This is assigning a integer from a pointer. Your compiler should have told you about this problem. Suggest: rightKey = 0;
The contents of the file: heap.txt is not an ordered array of the values from the heap. So what is it expected to contain?
The contents of the array: arraytochange[] is not sorted. This indicates a logic error in the posted code.
@SteveSummit I tested the stack space, it was not an issue that I could find. I dynamically allocated the space for the array and the same issue still existed. I also tried to run the code on another machine and it broke exactly at index 5761 again.
@kaylum see above message i just said to steve summit
@JonathanLeffler My program always terminates. It never errors out. The issue is that the sorting fails after the 5760th number
@JimMischel The program is not crashing. The heap sort is simply no longer sorting correctly at 5761 numbers, but works at previous numbers.
How long does it take on your machine? And have you verified that the data is sorted?
@user3629249 I expect heap.txt to be sorted. It is correctly sorted when there are 5760 or less numbers, but not more than that. Rightkey = 0 didn't solve the issue, and the include statement also didn't help.
@JonathanLeffler it sorts almost instantly with 5761 or 50000 integers. I have verified that the data is sorted for amounts of numbers including and under 5760 and it is not sorted for values over 5761.
I’ll have another look later, but when I ran the code, it didn’t terminate. That suggests there may be an uninitialized variable or a buffer overflow causing grief. Both lead to undefined behaviour, which means different results are permissible.
23:28
I ran the posted code, on linux, with a 1000 entry count. The result was both the data in the array and the data in the file are not sorted
The correction to the setting of Rightkey was not an answer, but rather a indication of a 'problem' in the code that should be corrected.
Does smell like a memory corruption or some other undefined behvaiour. Suggest you use valgrind to help debug. It's very good at finding memory issues.
the posted code is missing the statement: #include <stdlib.h> for the system() function
@kaylum, We already mentioned that on windows, the stack is rather small so we think that the problem is the stack has been overflowed. However, I also proved that the sorting algorithm is not correctly implemented
the contents of the file: heap.txt are not sorted. Here is a copy of the first several entries: 0 858 979 268 503 266 456 681 927 820 947 843
the contents of the 'heap[]` array are not sorted: Here is a copy of the first several entries, obtained by inserting: for( size_t i = 0; i < MAX; i++ ) { printf( "entry: %zu, value: %d\n", i, heap[ i ] ); } at the end of function: buildheap() entry: 0, value: 0 entry: 1, value: 0 entry: 2, value: 0 entry: 3, value: 0 entry: 4, value: 2 entry: 5, value: 3 entry: 6, value: 1 entry: 7, value: 2 entry: 8, value: 0 entry: 9, value: 3 entry: 10, value: 2
Your system("pause"); calls interacted badly with my version of pause on my Mac — it sits around doing nothing by executing the POSIX pause() function, which doesn't return until interrupted. The command doing 'nothing' includes not echoing anything to say it is running. When I comment out those lines, the code completes promptly (10-20 ms with size 5761; heap.txt contains 5761 unsorted numbers). I forgot to look for such booby traps. Unix commands seldom wait for user to hit a character before exiting.

last day (15 days later) »