Infinite Loop problem in an array sorting program

[scothoward]

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

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.

Thanks in advance!

 

[Mark44]

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:

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. :

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