# Infinite Loop problem in an array sorting program

Hi, I am writing a function that takes in a real data array and a key partition value, which will rearrange the array so that elements with a lower value than x are placed before the elements with values >= the partition value. It then returns the index of the last element of the array with a value less than the partition value.

We were given some pseudo-code which uses the idea that we start from the left and right and simultaneously switch elements using two loops excited together.

CODE
Code:
integer function partition_data( xdata, xmiddle )
implicit none

real, dimension(:) :: xdata
real :: xmiddle !INTENT?

integer ::  l = 1
integer ::  r = 16
real :: temp

do
if (xdata(l) < xmiddle) then
if (l == r) then
partition_data = l
exit
end if
l = l + 1
else
do
if (xdata(r) >= xmiddle) then
if (l == r) then
partition_data = l - 1
exit
end if

r = r - 1
else
temp = xdata(l)
xdata(l) = xdata(r)
xdata(r) = temp
exit
end if
end do

end if
end do

end function partition_data
With the xdata array

xdata = (/ 0.00392, 0.0251, 0.453, 0.667, 0.963, 0.838, 0.335, 0.975, &
0.796, 0.833, 0.345, 0.871, 0.0899, 0.888, 0.701, 0.735 /)

The xmiddle was set to 0.5 in the main test program.

When I compile, I seem to get an infinite loop and I cannot find where it is.

If anyone can spot where I went wrong, that would be great.

Last edited by a moderator:

Related Programming and Computer Science News on Phys.org
Mark44
Mentor
The OP hasn't been around for years, but in case others are interested, here's what I found. I implemented the code shown above in C++, and it worked without any problems. After the partition function returned, the array was ordered with all of the elements < 0.5 appearing before all those that were >= 0.5. The only changes I made were to replace the initial values of l and r with 0 and 15 respectively, since arrays in C/C++ are zero-based.

Without seeing the code you actually wrote, it's impossible to say why your code goes into an infinite loop.
My code:
C:
int partitionData(float xdata[], float xmiddle)
{
int l = 0, r = 15;
float temp;
while (1)
{
if (xdata[l] < xmiddle)
{
if (l == r) return l;
l++;
}
else {
if (xdata[r] >= xmiddle)
{
if (l == r) return l - 1;
r--;
}
else
{
temp = xdata[l];
xdata[l] = xdata[r];
xdata[r] = temp;
}
}
}
}
The partitionData() function returned 5.
Output with xmiddle set to 0.5. :
Code:
0.00392
0.0251
0.453
0.0899
0.345
0.335  << index 5, the last element of the array whose value is < xmiddle
0.838
0.975
0.796
0.833
0.963
0.871
0.667
0.888
0.701
0.735

Last edited:
• sysprog