How to sort an array in a single loop?

Question

So I was going through different sorting algorithms. But almost all the sorting algorithms require 2 loops to sort the array. The time complexity of Bubble sort & Insertion sort is O(n) for Best case but is O(n^2) as worst case which again requires 2 loops. Is there a way to sort an array in a single loop?

Barrett

I'm not sure what you mean by "one loop" vs. "two loops". You mean you want to sort without nested loops? – Obstetric

The only thing that comes to mind is counting or bin sort, but those require that all of the values be within a predefined range. – Champlin

Look for Merge Sort or Quick Sort (recursive methods) – Lemuelah

Answer 1

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.

Diplegia

Sure it's possible. The quantum bogosort algorithm is O(n)! – Obstetric

@MrSmith42 That's bogosort. Not quantum bogosort. – Obstetric

@Tripp Kinetics: Ok but you cannot implement it on a usual computer because you need all these universes. So for all now existing computers the lower bound Ω(n log n) is still valid. – Hectogram

@Hectogram The universes exist already. The hard part is destroying this universe if the array isn't sorted. Besides, algorithms are a concept independent of computers. – Obstetric

@TrippKinetics Not really. Algorithm complexity is intrinsically tied to the machine model the algorithm is supposed to run on. Would you say there are polynomial algorithms for all NP problems? But for a non-deterministic Turing machine this is just true. But no one says that. Even if bogosort could be solved by a "traditional" quantum computer, it would be in BQP, not P (necessarily)... and I think we got this joke just too far :) – Diplegia

@TrippKinetics, there's absolutely no need to destroy the universes where the data isn't sorted. Someone will be in the one where they are sorted :-) – Rosenquist

Answer 2

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

Bipetalous

Answer 3

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.

Hungry

Answer 4

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

Orator

Comment (inside!) your code (know [Doxygen](www.doxygen.org)?), use a symbolic constant for the number of as elements, and a telling name instead of flag. – Boon

People should mind that this is a specific array that can be sorted by one iteration of bubble sort. – Heliotaxis

Answer 5

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.

Juback

Answer 6

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)

Roasting

Answer 7

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.

Neville

This (known as a pigeonhole sort) is the only true example of a single loop sort that operates in O(n) time. Like any other sorting example, a loop is required to display the results, but only after the sorting is complete. – Semple

According ot Wiki, Pigeonhole sort is a mathematical concept rather than a programming array process, although pigeonhole sorting of arrays is very common. I used this solution to sort 10 million points in less than 1-2 seconds, its very easy to program and has near maximum efficiency for num instructions, it is literally 12 lines of code. – Neville

Answer 8

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

Emalee

Answer 9

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

    }

Velvetvelveteen

Answer 10

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

Auster

It could be helpful if you added some context to your answer. – Mouthful

This is essentially bubble sort in what language? Could be perl or shell script without context, people have a hard time understanding. – Somatotype

Answer 11

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

}

Fokker

I have edited your question. But a tip for next time would be that if you're posting a code then use the given alignment option for better understanding. – Indemnify

What is the addition to all the other suggestions starting the index at 0 and resetting it to -1? (If and when you edit the question, please fix the formatting of the code block. I found it least cumbersome to just enclose code with lines containing ~~~, the first one mentioning the language as need be.) – Boon

Answer 12

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

Fetid

Answer 13

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

Rowe

Voted down for not mentioning the language and presenting a redundant conditional statement in deviant syntax. – Boon

Answer 14

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]

Outdistance

Welcome to Stack Overflow! Please don't answer just with source code. Try to provide a nice description about how your solution works. See: How do I write a good answer?. Thanks – Vinous

Answer 15

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]

Clova

Answer 16

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

?>

Auster

Answer 17

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;

    }

Uncinate

Output for {3, 2, 1}: [2, 1, 3]. – Boon

Answer 18

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

Abscond

This saves two tokens compared to starting the loop index at 0. – Boon

Answer 19

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

Unhopedfor

Answer 20

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

Erogenous

Answer 21

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

Manoff

Answer 22

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

Accompaniment

Answer 23

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)

Transparent

not working with same number comes in the arr – Ventriloquism

Answer 24

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

Kelleher

Answer 25

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

Intuitive

Answer 26

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

Schertz

We just need to take care of 2 things which handled by variable k 1.Reset your flag once you reach to end of array. 2.continue to swap until you find large element present before smaller one. – Schertz

Most of the answers below are effectively using 2 loops since they reset the loop counter within the so called "single" loop. – Incomputable

Answer 27

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

Argillaceous

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Rapt

Answer 28

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

Vallecula

@Vallecula I tried it and it doesn't seem to sort at all. What am I doing wrong? – Cabaret

The idea of sorting is very simple, to place values in an array with an index equal to the value of the array. At the output, we get an ordered associative array. – Vallecula