For what i saw we need to previously know the max and minimum values, right ?
Btw...one small fix on Marinus version (perhaps on yours too it have the same issue).
The algo is calculating the middle of the table and getting the value of the last one in the table from the left, right ? I notice a small mistake when getting positive integers numbers.
At "FindSecondMiddleNumberLP" it is needed to change this:
mov edx, eax ; Save the first middle number to calculate the average of 2 middle numbers.
FindSecondMiddleNumberLP: ; pretty rare case, mostly with small data sets
inc eax
cmp dword ptr[edi+4*eax], 1 ; ecx must be 1
jb FindSecondMiddleNumberLP
add eax, edx ; Second middle number found, add it to the first middle number.
shr eax, 1 ; And get the average.
To something like this
mov edx, eax ; Save the first middle number to calculate the average of 2 middle numbers.
inc eax
FindSecondMiddleNumberLP: ; pretty rare case, mostly with small data sets
cmp dword ptr[edi+4*eax], 0 ; Search if the next address (so, the 1st one in the right table) is not empty
jne FoundFirstMiddleNumberRight ; If the address is already filled, exit the loop
inc eax ; search next address and jump over when the address at this position in the table is filled
jmp FindSecondMiddleNumberLP ; <---- Sorry, forgot to port this when i was editing this post
FoundFirstMiddleNumberRight:
add eax, edx ; Second middle number found, add it to the first middle number.
shr eax, 1 ; And get the average.
I believe it is the proper masm version. In RosAsm, it is:
mov edx eax ; Save the first middle number to calculate the average of 2 middle numbers
; here we are always at the end of the left middle. Ex if size = 100, we are at pos 49th
; FindSecondMiddleNumberLP.
inc eax
while D$edi+eax*4 = 0
inc eax
End_while
add eax edx
shr eax 1 ; And get the average.
You can test it on these values (Positive integers):
[DataSelect9: D$ 136, 151, 216, 40, 13, 215, 24, 104,
230, 154, 227, 219, 52, 217, 38, 131,
228, 95, 178, 51, 70, 14, 9, 34,
80, 195, 59, 27, 100, 118, 78, 137,
65, 104, 7, 32, 23, 58, 202, 154,
238, 12, 11, 165, 223, 197, 98, 26,
231, 92, 29, 131, 25, 99, 97, 77,
155, 120, 154, 182, 177, 211, 103, 238,
209, 86, 205, 213, 180, 126, 55, 95,
186, 232, 196, 121, 237, 187, 26, 120,
13, 56, 186, 167, 14, 136, 90, 196,
120, 23, 190, 79, 164, 41, 239, 39,
18, 109, 35, 169] ; Size = 100, Median = 119
The reason is that when you see the data in the proper order, you will see something like this:
Left Middle Table
0 ___________________________49 (Position starting from zero)
7 9 11 12 13 13 (...) 118 <--- marinus code found this value when reached FindSecondMiddleNumberLP
Right Middle Table
50 ___________________________100 (Position starting from 50)
120 120 120 121 (...) 238 238 239
________
|
and we need to find this
Since we have a gap of 2 (120-118), it means that the next address on the right that contains a value is the one 2 dword ahead. Since we already incremented this value at eax, we must 1st see if that address is not empty. If it is empty, we perform the loop untill the next address that is full and increment on each loop.
Can you please, test to see if this is correct. On the values i tested above, it found the proper median. (On positive integers it seems to work. Not sure how it will behave in negative or floats)
