How to sort an array in a single loop?

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.

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] + " ");
    }

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.

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)

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++;
        }
    }

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);

public class SinleLoopeSorting {

public static void main(String[] args) {
    Integer[] x = new Integer[] { 1, 7, 8, 0, 4, 2, 3 };

    for (int i = 0; i < x.length - 1; i++) {
        if (x[i] > x[i + 1]) {
            int p = x[i];
            x[i] = x[i + 1];
            x[i + 1] = p;
            i = -1;
        }
    }
    for (int i = 0; i < x.length; i++) {
        System.out.println(x[i]);
    }
}

}

This can be used to sort array usinga single loop:- Points to be noed:

1. updating the value of i to -1 so that it alwasy starts from 0 after i++
2. reducing the length(size--) of array as maximum valued element ends up at the end for every time the loop completes

Code:

void sort(int *arr,int size){
    int i;
    for (i = 0; i <size; 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];
            if(i==size-2){
                printf("%s\n","inside if loop" );
                i=-1;
                size--;
            }
        }
    }
}

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;
        }
}

    #include<stdio.h>

    void sort(int a[],int n,int k,int w)
    {   
      int i,j,z,key;
      n=n-1;
      j = k+1;
      key = a[j];
      i = j-1;
      while(i>0 && a[i]>key)
      {
        a[i+1] = a[i];
        i = i-1;
      }
      a[i+1] = key;
      k = k + 1;
      if(n!=0)
      {
       sort(a,n,k,w);
      }
    }

  int main()
 {
    int i,n,w,k=1,z=5,g;
    printf("enter the size of an array\n");
    scanf("%d",&n);
    g=n;
    int a[n];
    for(i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    w = n;
    sort(a,n-1,k,w);

    for(i = 1; i <= n; i++)
    {
        printf("%d", a[i]);
    }
 }

Here is the solution. This might help you.

public int find2ndLargest() {
    int[] arr = {1,3,14,25,7,20,11,30};
    int temp;

    // sort array
    for (int i=0;i<arr.length-1;i++) {
        if (arr[i]>arr[i+1]) {
            temp = arr[i];
            arr[i]=arr[i+1];
            arr[i+1]=temp;
            i=0;
        }
    }
    return arr[arr.length-2];
}

static int[] sort(int[] arr){
        int idx = 0;
        int len = arr.length - 1;
        int counter = len;
        while(true){
            if(idx != len && arr[idx] > arr[idx+1]){
                swap(arr, idx, idx + 1);
                counter--;
            }
            idx++;
            if(counter == len && idx == len){
                break;
            }
            if(idx == len){
                idx = 0;
                counter = len;
            }
        }
        return arr;
    }


    void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

it as much simple as below, please flow easy step

         var arr=[5,1,4,3];
             for(var i=0;i<arr.length-1;i++){
                 var num=arr[i];
                 var num2=arr[i+1];
                //Check if first index value with next index value
                if(num>num2){
                  var temp=arr[i];
                  arr[i]=arr[i+1];
                  arr[i+1]=temp;
                  //assign i=0 to re start the loop to check the index value
                  i=0;
                 }
             }

console.log(arr)

you can use a while loop and play around with the index

       int i=0;
       int a[]={1,2,3,4,7,3};
       while(i<a.length)
       {
           if((i+1<a.length && a[i]>a[i+1]) )
           {
                swap(i,i+1,a);
               i=i-1;
           }
         if(i-1>=0 && a[i]<a[i-1] )
             {
             swap(i,i-1,a);
            i=i-1;
             }
           else
               i++;
       }
    

Swift Code

func sortingOneArray(array: [Int]) -> [Int] {
    var sortedArray = array
    var i = 0
    while (i < sortedArray.count - 1) {
        if sortedArray[i] > sortedArray[i+1] {
            let temp = sortedArray[i]
            sortedArray[i] = sortedArray[i+1]
            sortedArray[i+1] = temp
            print("i \(i)")
            i = 0
        } else {
            i = i + 1
        }
    }
    return sortedArray
}

print(sortingOneArray(array: [1,3,7,4,2,0]))

Of course not O(n)

def sort(array):
    n = len(array);
    i = 0;
    mod = 0;
    if(len(array)<= 1):
        return(array)

    while n-1:
        if array[mod] > array[mod+1]:
            array[mod], array[mod+1] = array[mod+1], array[mod]

        mod+=1
        if mod+1 >= n:
            n-=1
            mod = 0

    return array

public class CustomSorting {
    public static void main(String[] args) {
        int a[] = {1,5,7,45,65,4,3,6,75,24};

        int i = 0;
        int j = 1;
        int k = 1;

        boolean isSorted = true;
        while(k < a.length){
            if(a[i]> a[j]){
                int temp = a[j];
                a[j]= a[i];
                a[i] = temp;
                isSorted = false;
            }
            i++;
            j++;
            //will reset i and j value on below condition to prevent extra integration as result of every iteration last element will be sorted
            if(i >= a.length - k){
                if(isSorted)
                {
                    System.out.println("already sorted , no iteration required");
                    break;
                }
                //once it reach to last element , start from first, this iteration will happen array length - 1 time ,which we are maintain through K
                //reset all
                i=0;
                j=1;
                k++;
                isSorted = true;

            }
        }

        for(int p : a){
            System.out.print(p+" ");
        }
    }
}

<!-- example array -->
var a = [9,8,7,6,5,4,3,2,1]


const sort = () => {
    for(i = 0 ; i < a.length ; i++){
        if(a[i] > a[i+1]){
            var temp = a[i]
            a[i] = a[i+1]
            a[i+1] = temp
            i = 0
        }
        if(a[0] > a[1]){
            var temp = a[0]
            a[0] = a[1]
            a[1] = temp
        }
    }
}

sort()

console.log(a)

Single for loop for insertion sort:

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--
        } else{i++}
    }
    return array
}

This is a very fast sorting of an array of unique values. Using the features of arrays in PHP, one pass is enough. It is also possible to sort two-dimensional arrays in one cycle pass.

$a = [8,3,4,9,1];
$b = [];
for($i=0;$i<count($a);$i++){
 $b[$a[$i]]=$a[$i];
}
$a = array_values($b);
print_r($a);