Styjun

Here, a single-loop Bubble Sort in Python:

def bubbly_sortish(data):
 for _ in xrange(len(data)**2):
 i, j = _/len(data), _%len(data)
 if i<j and data[i] > data[j]:
 data[i], data[j] = data[j], data[i]

A = [5, 1, 2, 3, 5, 6, 10]
bubbly_sortish(A)

print A 

Of course this is a joke. But this shows the number of loops has little to do with algorithm complexity.

Now, if you're asking if it is possible to sort an array with O(n) comparisons, no, it's not possible. The lower bound is Ω(n log n) for comparison-based sorting algorithms.

Single Loop Bubble Sort using C++

int a[7]=5,7,6,2,4,3,1;

int temp = 0;

int j = 0;

for(int i = 0 ; i<a[]-1 ; i++)

 int flag = 0;
 if(a[i]>a[i+1])
 
 temp = a[i];
 a[i] = a[i+1];
 a[i+1] = temp;
 flag = 1;
 
 if(i == 7-2-j)
 
 if(!flag) break;
 i = -1;
 j++;
 

In the general case you have O(n lg n) as an average.

But in particular cases, the best case is O(n), which I consider close enough to what you'd call "only one loop", even though the implementation may show more than one instance of the for keyword. And the good news with that, is that you're not depending on luck to make your best case a reality. Provided you know a few properties about your data, you can pick some specific algorithms. For example :

• 3-way quicksort runs very near O(n) when you have a lot of items with only a few distinct sorting keys (think server log entries as items and dates as keys).


• Counting sort runs in O(n+k) if your keys are easily indexable (like a character set, or small integers), and the index has a known upper bound k.


• Burstsort will run in O(wn) if you're dealing with strings of maximum length w.

Those are but three examples. There are many more, way too many to recall from the top of my head, for many types of constrained data sets.
If you have a real-life case at hand where O(n lg n) is not good enough, it's well worth doing some proper research, provided you identified a few interesting properties in your data.

int list[] = 45, 78, 22, 96, 10, 87, 68, 2 ;
 for (int i = 1; i < list.length; i++) 
 if (list[i] < list[i - 1]) 
 list[i] = list[i] + list[i - 1];
 list[i - 1] = list[i] - list[i - 1];
 list[i] = list[i] - list[i - 1];
 i = 0;
 
 
 System.out.print("Sorted array is : ");
 for (int i = 0; i < list.length; i++) 
 System.out.print(list[i] + " ");
 

Here is a working version for your given example:

One very fast efficiant and logical way of doing the problem works if you know the range of the values to be sorted, for example
0 <= val <= 100 where val is integer.

Then you can do it with a single read and write operation in only two loops... one for reading the array, one for writing it sorted:

Use a second array where the indices represent values 0-100, store in it the number of times every value 0-100 is encountered, for example val = 100 could exist 234 times in your target array...

There is only one loop for reading and one loop for writing, which is computationally as efficient as one loop which would do both the reading and the writing and faster than a loop that uses comparison... If you insist, you can do it in a single loop twice as long as the target array's length and reset i value to zero on the new array write operation.

The second loop simply writes in order the count of every value encountered in the first array.

Single loop array sort:

for(int i = 0, j=i+1; i < arr.length && j<arr.length;)
 
 if(arr[i] > arr[j])
 
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp; 
 i=0;
 j=i+1;
 
 else
 
 i++;
 j++;
 
 

javascript:
function bruteForce(arr)
 for(var i=0;i<arr.length; )
 if(arr[i+1]< arr[i])
 var temp = arr[i];
 arr[i]=arr[i+1];
 arr[i+1] = temp;
 i--;
 if(i === -1) i=0;
 else i++;
 

 return arr;
 

alert(bruteForce([2,3,4,5,6,23,1,1]));

Copy the code and paste in URL of the browser and hit enter. If the javascript: is missed then add it.

Here is the code to sort array using only single loop.

var array = [100, 110, 111, 1, 3, 19, 1, 11, -10]
var i = 1

while i < array.count - 1 
 if array[i] > array[i + 1] 
 let temp = array[i];
 array[i] = array[i + 1];
 array[i + 1] = temp;
 i = -1;
 
 i = i + 1;

print(array)

Single for loop for insertion sort:

strong text

function insertionSort (array) 
 for(var i = 1 ; i < array.length ;)
 if(array[1] < array[0]) 
 temp = array[i];
 array[i] = array[i -1];
 array[i -1] = temp; 
 
 if(array[i] < array[i-1])
 var temp = array[i]
 array[i] = array[i -1]
 array[i -1] = temp
 i--
 elsei++
 
 return array

public void sortArrayUsingSingleLoop(int[] intArray) 
 int temp;
 boolean swap = false;
 for(int i=0;i<intArray.length-1;i++)
 if(intArray[i]>intArray[i+1])
 temp=intArray[i];
 intArray[i]=intArray[i+1];
 intArray[i+1]=temp;
 swap=true;
 

 if(swap &&i==intArray.length-2)
 i=-1;swap=false;
 
 

 

The following code is in php. you can test the code on https://paiza.io/projects/4pAp6CuB-e9vhGIblDNCZQ.

 $a = [8,3,4,9,1];
 for($i=0;$i<count($a)-1;$i++)
 if($a[$i] > $a[$i+1])
 $temp = $a[$i];
 $a[$i] = $a[$i+1];
 $a[$i+1] = $temp;
 $i = -1;
 
 
 print_r($a);

def my_sort(num_list):
 x = 0
 while x < len(num_list) - 1:
 if num_list[x] > num_list[x+1]:
 num_list[x], num_list[x+1] = num_list[x+1], num_list[x]
 x = -1
 x += 1
 return num_list

print(my_sort(num_list=[14, 46, 43, 27, 57, 42, 45, 21, 70]))
#output [14, 21, 27, 42, 43, 45, 46, 57, 70]

Sorting an array using single loop (javascript)

var arr = [4,5,2,10,3,7,11,5,1];
for(var i = 1; i < arr.length; i++)
 
 if(arr[i] < arr[i-1])
 
 arr[i] = arr[i] + arr[i-1];
 arr[i-1] = arr[i] - arr[i-1]; 
 arr[i] = arr[i] - arr[i-1]; 
 i=0;
 

output : arr = [1, 2, 3, 4, 5, 5, 7, 10, 11]

The following code is in PHP to sort an array best case possible.
https://paiza.io/projects/r22X0VuHvPQ236jgkataxg

<?php
function quicksort($a)
 $n = count($a);
 $lt = [];
 $gt = [];

 if($n < 2)
 return $a;
 else
 $f = $a[0];
 

 for($i = 1;$i < $n ;$i++)
 if($a[$i] > $f)
 $gt [] = $a[$i];
 else
 $lt [] = $a[$i];
 
 

 return array_merge(quicksort($lt),array($f),quicksort($gt));



$ar = [7,4,3,6,5,1,2];
echo "Input array => ".implode(' , ',$ar).'<br>';
$a = quicksort($ar);

echo "Output array => ".implode(' , ',$a);;

?>

Sorting an array using java in Single Loop:

 public int[] getSortedArrayInOneLoop(int[] arr) 

 int temp;
 int j;

 for (int i = 1; i < arr.length; i++) 
 j = i - 1;

 if (arr[i] < arr[j]) 

 temp = arr[j];
 arr[j] = arr[i];
 arr[i] = temp;
 i = 1;

 

 

 return arr;

 

Late to the party but hope this helps

java solution

for(int i=1;i< arr.length;i++) 
 if(arr[i] < arr[i-1] )
 arr[i-1] += arr[i];
 arr[i] = arr[i-1] - arr[i];
 arr[i-1] -= arr[i];
 i=0;