Sort one sequence by O(n) in time and O(1) in space

[Oscar Benjamin]

Something like

mylist[:] = reorder_generator(mylist)

won't work because the generator would need to access the data
non-sequentially (it would need to read elements after they were
overwritten).

This would have O(1) space and O(n) time. It's absolutely perfect...
except that you now don't technically have a list any more:

mylist = reorder_generator(mylist)

You can iterate over it, but can't index it. But hey, it complies with
the space/time requirements!

That is very likely a practical solution for many problems involving
transposition. Doing this in Python is pretty artificial since a new
list object will likely use a lot less memory than the elements it
contains.

The practical use for such algorithms is in something like C and even
then it's often better to simply iterate in a different order. The
advantage of physically transposing the data is to improve memory
locality but this only makes sense if your transpose algorithm itself
has a good memory access pattern (which is likely impossible with O(1)
storage).


Oscar

 

[Gregory Ewing]

mylist = reorder_generator(mylist)

You can iterate over it, but can't index it. But hey, it complies with
the space/time requirements!

Rather than a generator, you could use a view object
that rearranges the indices when you access an element.
That would comply with the space/time requirements
and be indexable as well.

Actually it would do better than meet the requirements,
since in a sense it would be O(1) in both space and time!

 

[Steven D'Aprano]

[Wesley] This is not homework
And actually I am new to algorithm, so you guys can feel free to say
anything you want

In general, we cannot sort a sequence in O(n) time. O(n log n) is the
lower bound on the complexity.

Firstly, you're talking about average complexity, not best-case
complexity. The base-case can be O(N) for a sequence which is already
sorted. Worst case can be much greater, e.g. O(N**2) for Quicksort, or
unbounded for Bogosort. (That is, Bogosort is not guaranteed to sort a
sequence even after infinite time!)

Secondly, O(N*log N) applies to *comparison sorts*. Non-comparison sorts
such as radix-, counting- and bucket-sort have average case complexity of
O(N). See, for example:

http://algorithmstwo.soc.srcf.net/resources/asides/noncomparison/

http://en.wikipedia.org/wiki/Bead_sort

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Spaghetti_sort


etc.

 

[Tim Daneliuk]

In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
bound on the complexity.

Only true for sorting that involve comparison. However, sorts that use
the values of the inputs as positional keys have a lower bound
complexity (omega) of O(n) and a worst case complexity of O(n)
and are thus asymptotically optimal.

For example, given a range of integers guaranteed to be within
the range of j to k (lower to higher), one can created a bit field
to represent all possible values of j to k. Then, as values are
read in, the corresponding but is set true. You have to process
the list of n elements once to read it in, and then a second
time to read them out in order. This is a 2n operation which is O(n).

For very large ranges of j to k, this is impractical and we resort
to things like hashing functions which can perform better than
n log n sorting algorithms. But there are lots of real world
applications where inputs-as-keys works just fine, such as short
dispatch tables in operating systems where the value to be
sorted represents a process priority, for example.

 

[Tim Daneliuk]

In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
bound on the complexity.

Only true for sorting that involve comparison. However, sorts that use
the values of the inputs as positional keys have a lower bound
complexity (omega) of O(n) and a worst case complexity of O(n)
and are thus asymptotically optimal.

For example, given a range of integers guaranteed to be within
the range of j to k (lower to higher), one can created a bit field
to represent all possible values of j to k. Then, as values are
read in, the corresponding but is set true. You have to process
the list of n elements once to read it in, and then a second
time to read them out in order. This is a 2n operation which is O(n).

For very large ranges of j to k, this is impractical and we resort
to things like hashing functions which can perform better than
n log n sorting algorithms. But there are lots of real world
applications where inputs-as-keys works just fine, such as short
dispatch tables in operating systems where the value to be
sorted represents a process priority, for example.

 

[Gregory Ewing]

Secondly, O(N*log N) applies to *comparison sorts*. Non-comparison sorts
such as radix-, counting- and bucket-sort have average case complexity of
O(N).

They require additional space, though.