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?

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.

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