Can we sort using a single loop?

[Pavan Kumar Dittakavi]

Hi All,

I want to know if this is possible:" Writing a program that sorts an array by using only a single loop."; I dont want the solution but I wanted to know if this is really feasible.

Thanks,
Pavan.

[anirudh jagithyala]

for(int i=0; i<n-1; i++)
{
if(x[i] < x[i+1])
{
int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp; // swap values
again = true;
}
if(i==n-2 && again==true) { i = 0; again = false; }
}

where 'x' is the integer array name, 'n' is the number of elements in 'x'.
This for loop sorts the elements of the array in ascending order. To sort in descending order, change "if ( x[ i ] < x[ i + 1 ] )" to "if ( x[ i ] > x[ i + 1 ] )"

I have no way of testing all of these, but I'm pretty sure they'll work.

[Pavan Kumar Dittakavi]

I think I have got it.

    int j = 0;
    int prevI = 0;
       for(int i=0; i<n-1; i++)  
        {
        	j++;
        	if( j < n)
        	{        		
        		i = prevI;
        	}
        	else
        	{
        		j = i + 1;
        	}
        	
        	if(x[i] < x[j])  
        	{  
        		int temp = x[i]; 
        		x[i] = x[j]; 
        		x[j] = temp;
        	}       	
        	prevI = i;
        	
    	}  

@anirudh jagithyala: The code you provided fails for input 5 1 7 3 9. Thanks anyway.

Thanks,
-Pavan.

[Ryan McGuire]

Pavan Kumar Dittakavi wrote:Hi All,

I want to know if this is possible:" Writing a program that sorts an array by using only a single loop."; I dont want the solution but I wanted to know if this is really feasible.

Thanks,
Pavan.

Short answer: Any algorithm can be reworked as a single loop.

For this problems, you can implement what amounts to a bubble sort by using two indices (say i and j) and just have all the initialization, incrementing and termination expressions in a handful of if/then/else statements at the bottom of the single loop. It would still execute in O(n^2) time, but it would technically be a single loop.