Gaming32 / ArrayV

New home of https://github.com/MusicTheorist/ArrayVisualizer
MIT License
303 stars 47 forks source link

Some sorts access out-of-bounds indices #61

Closed Ibozz91 closed 2 years ago

Ibozz91 commented 3 years ago

Some sorts are attempting to access indice 32768 on 32768 numbers, which is out of bounds. This does not happen on 2048 numbers.

thatsOven commented 3 years ago

this happens because ArrayV internally uses an array of size 32768 (unless you change it via command prompt when starting the program) so these sorts actually write out of bounds for every size, but you usually don't notice it because the array is actually bigger

Gaming32 commented 3 years ago

On 2048 numbers, you should notice warnings being printed to the console.

Ibozz91 commented 3 years ago

I think that there should be warnings instead of errors on higher numbers.

EmeraldBlock commented 3 years ago

There are warnings on sizes below the max because the out-of-bounds index actually exists, but on max size it's truly out of bounds and there is an error.

Whether warning or error, you'd probably need all sorts to access the array by "proxy" (since if they access it directly, the array would act as if it was max size).

Personally, I think it should always error, but that would break the problematic sorts.

MusicTheorist commented 3 years ago

I think that there should be warnings instead of errors on higher numbers.

I actually disagree. Accessing out-of-bounds memory is a serious problem. In languages without Java's safety precautions, it leads to undefined behavior. Algorithms that have this issue should straight up be fixed without question.

Ibozz91 commented 3 years ago

Okay. this sounds good. The sorts so far I have had problems with the psuedo-heap and grail sort.

picc-lu commented 3 years ago

I found same problem in Binary Merge sort, something wrong in Highlights:

save index: - ![1](https://user-images.githubusercontent.com/32639909/125843225-6da5825f-2c10-47db-a144-d2dca387ca91.png) - ![2](https://user-images.githubusercontent.com/32639909/125843168-69344ed6-4ceb-4634-b10f-7a0702fecd23.png)
read index: - ![3](https://user-images.githubusercontent.com/32639909/125863599-d1a1c9b6-3ae5-4045-95d0-15d8ce06abe9.png) - ![4](https://user-images.githubusercontent.com/32639909/125863607-66a99e15-1e3e-4101-84fc-39f87b97aea8.png) - ![5](https://user-images.githubusercontent.com/32639909/125863609-7b84a267-c892-4ce9-8aa5-4e016cc0d13c.png)

Hope this will help.

EmeraldBlock commented 3 years ago

Yeah, though it's mainly the sort's fault: once low or high reaches the end of its subarray, it just sits there and still gets highlighted (Highlights doesn't have a check for out-of-bounds)

...wow those screenshots take up a lot of space lol EDIT: I put your screenshots in collapsible sections to not make the message so long, sorry!

Gaming32 commented 3 years ago

Related: #60

Gaming32 commented 2 years ago

If sorts attempt to highlight out-of-bounds indices, the request to highlight is ignored. Attempting to write to out-of-bounds indices is still an error, however. This was such an easy fix, I have no clue why we didn't do it before.