How to sort an array in a single loop?

algorithm sorting quicksort insertion-sort heapsort
Aishwarya R picture Aishwarya R · Aug 12, 2015 · Viewed 32.8k times · Source

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

Juan Lopes picture Juan Lopes · Aug 12, 2015

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.

Related questions

Quicksort with Python

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code? I do not know how to concatenate the three arrays and printing them. def sort(array=[12,4,5,6,7,3,1,15]): less = [] …

Read More
Why is quicksort better than mergesort?

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

Read More
Quicksort: Choosing the pivot

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? …

Read More