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?

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

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

Solution 3

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

Solution 4

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.

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

View more solutions

Comments

[Tripp Kinetics]

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

[Tripp Kinetics]

@MrSmith42 That's bogosort. Not quantum bogosort.

[MrSmith42]

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

[Tripp Kinetics]

@MrSmith42 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.

[Juan Lopes]

@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 :)

[greybeard]

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.

[John Wu]

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.

[John Wu]

Bear in mind that O(n lg n) is an average, not a lower bound. The lower bound is O(n) when the input is already sorted :)

[Mathias Dolidon]

You're right, this was a bad mistake ! I'll correct my post immediately. Thank you very much !

[LifeInTheTrees]

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.

[sɐunıɔןɐqɐp]

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

[paxdiablo]

@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 :-)

[NONONONONO]

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

[chakeda]

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

[Kemin Zhou]

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

[puneet jain]

Sorry for not giving the context. The following code is in php. you can test the code on phpfiddle.org.

[baymax]

@puneetjain Edit the answer with the above comment. Comments are for reviewers not for additional info from the author. You could additional use Edit1/Edit2/ etc markers in case of unrelated info to the answer to a specific comment. Happy using SO.

[Varun Jain]

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.

[greybeard]

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

[greybeard]

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

[greybeard]

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

[greybeard]

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