Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #65745 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 04:13 -0800
    Re: Sort one sequence by O(n) in time and O(1) in space Asaf Las <roegltd@gmail.com> - 2014-02-09 04:29 -0800
    Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-09 23:39 +1100
      Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:09 -0800
        Re: Sort one sequence by O(n) in time and O(1) in space Dave Angel <davea@davea.name> - 2014-02-09 22:00 -0500
    Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 13:41 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 14:30 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Ni Wesley <nispray@gmail.com> - 2014-02-09 22:40 +0800
    Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 10:05 -0500
      Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 23:14 +0000
        Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 19:15 -0500
        Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:26 -0800
          Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 10:20 +0000
            Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve@pearwood.info> - 2014-02-11 05:20 +0000
              Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-12 11:56 +1300
            Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
            Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
          Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-10 21:37 +1100
          Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 15:03 +0000
          Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:23 +1100
          Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 15:45 +0000
          Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:52 +1100
            Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-11 13:19 +1300
          Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 16:41 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 15:48 +0000
      Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:07 -0800
    Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 21:31 +0000

Page 1 of 2  [1] 2  Next page →

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

Hi guys,
   Here is one question related to algorithm.
Details here:

here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).

Any comments will be appreciated.
Thanks.
Wesley

[toc] | [next] | [standalone]

#65748

On Sunday, February 9, 2014 2:13:50 PM UTC+2, Wesley wrote:
> Hi guys,
>    Here is one question related to algorithm.
> Details here:
> 
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
> 
> Any comments will be appreciated.
> 
> Thanks.
> 
> Wesley

if space O(1) is needed they don't have to be merged - list alike class keeping series as members returning a[i] if i is odd and b[i] if i is even would be enough. then constructing such sequence (or class instance) will be done in O(1) as well.

/Asaf

[toc] | [prev] | [next] | [standalone]

#65749

On Sun, Feb 9, 2014 at 11:13 PM, Wesley <nispray@gmail.com> wrote:
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).

The two halves of the list are already sorted, yes? Then you don't
need a sort operation, just a zip.

def flip_list(lst):
    offset = len(lst)//2
    for i in range(offset):
        yield lst[i]
        yield lst[i+offset]

start = ['a1','a2','a3','a4','b1','b2','b3','b4']
result = list(flip_list(start))
print(result)

Alternatively, you could arrange this as some kind of swap operation,
modifying the list in place, but I think the more Pythonic way will be
to create a new list. Note that, with the function defined as I have
above, you can iterate over the flipped list without actually
coalescing it in memory. That gives effective O(1) space, and it's
definitely O(n) time as it simply iterates over the whole list once.

ChrisA

[toc] | [prev] | [next] | [standalone]

#65793

> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
> 
> 
> 
> The two halves of the list are already sorted, yes? 

[Wesley] No, not sorted yet..

[toc] | [prev] | [next] | [standalone]

#65797

 Wesley <nispray@gmail.com> Wrote in message:
> 
>> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
>> 
>> 
>> 
>> The two halves of the list are already sorted, yes? 
> 
> [Wesley] No, not sorted yet..
> -- 
> https://mail.python.org/mailman/listinfo/python-list
> 

Then supply some example lists and show the result you want. So
 far, your description is thoroughly ambiguous.

-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#65758

On 9 February 2014 12:13, Wesley <nispray@gmail.com> wrote:
> Hi guys,
>    Here is one question related to algorithm.
> Details here:
>
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).

Do you mean that you have a list and you want to rearrange the
elements in-place without creating a new list?


Oscar

[toc] | [prev] | [next] | [standalone]

#65761

Please reply to the list rather than directly to me so that other
people can see the answer to my question and offer you help.

On 9 February 2014 14:04, Ni Wesley <nispray@gmail.com> wrote:
> 2014年2月9日 下午9:41于 "Oscar Benjamin" <oscar.j.benjamin@gmail.com>写道：
>
>> On 9 February 2014 12:13, Wesley <nispray@gmail.com> wrote:
>> > Hi guys,
>> >    Here is one question related to algorithm.
>> > Details here:
>> >
>> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx
>> > always exist in pair. So, now, how to change the sequence to
>> > a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
>>
>> Do you mean that you have a list and you want to rearrange the
>> elements in-place without creating a new list?
>
> Yes

Okay so if you're going to do it with O(1) space then it's going to
have to be done with a whole bunch of swaps. Have a think with pen and
paper about how you could do a sequence of swaps that would rearrange
the order to the one that you want (it's actually a harder problem
than it looks at first glance). This is an example of what is known as
"transposition" and much information is available about algorithms for
doing this in-place:
http://en.wikipedia.org/wiki/In-place_matrix_transposition


Oscar

[toc] | [prev] | [next] | [standalone]

#65762

[Multipart message — attachments visible in raw view] — view raw

Yes, with no new list, otherwise, space won't to be O(1)

Wesley
2014年2月9日 下午10:31于 "Oscar Benjamin" <oscar.j.benjamin@gmail.com>写道：

> Please reply to the list rather than directly to me so that other
> people can see the answer to my question and offer you help.
>
> On 9 February 2014 14:04, Ni Wesley <nispray@gmail.com> wrote:
> > 2014年2月9日 下午9:41于 "Oscar Benjamin" <oscar.j.benjamin@gmail.com>写道：
> >
> >> On 9 February 2014 12:13, Wesley <nispray@gmail.com> wrote:
> >> > Hi guys,
> >> >    Here is one question related to algorithm.
> >> > Details here:
> >> >
> >> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx
> >> > always exist in pair. So, now, how to change the sequence to
> >> > a1,b1,...,an,bn, with time complexity as O(n) and space as O(1).
> >>
> >> Do you mean that you have a list and you want to rearrange the
> >> elements in-place without creating a new list?
> >
> > Yes
>
> Okay so if you're going to do it with O(1) space then it's going to
> have to be done with a whole bunch of swaps. Have a think with pen and
> paper about how you could do a sequence of swaps that would rearrange
> the order to the one that you want (it's actually a harder problem
> than it looks at first glance). This is an example of what is known as
> "transposition" and much information is available about algorithms for
> doing this in-place:
> http://en.wikipedia.org/wiki/In-place_matrix_transposition
>
>
> Oscar
>

[toc] | [prev] | [next] | [standalone]

#65764

In article <ae372652-0f1c-4d79-82db-a522eb592579@googlegroups.com>,
 Wesley <nispray@gmail.com> wrote:

> Hi guys,
>    Here is one question related to algorithm.
> Details here:
> 
> here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx always 
> exist in pair. So, now, how to change the sequence to a1,b1,...,an,bn, with 
> time complexity as O(n) and space as O(1).

Is this a homework problem?

It sounds like what you want to do is split the list into two halves, then shuffle them.  Using
itertools let's you do these operations without making copies of the data.  

Something like:

--------------------------------------------------
from itertools import islice, izip

def cut_and_shuffle(input):
    n = len(input)
    if n % 2:
        raise ValueError("input length must be even")
    split = n/2
    print "split =", split
    first_half = islice(input, 0, split)
    second_half = islice(input, split, n)
    for a, b in izip(first_half, second_half):
        yield a
        yield b

l = ['a1', 'a2', 'a3', 'a4', 'b1', 'b2', 'b3', 'b4']
print list(cut_and_shuffle(l))
--------------------------------------------------

$ python shuffle.py
split = 4
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'b4']

[toc] | [prev] | [next] | [standalone]

#65787

On Sun, 09 Feb 2014 10:05:02 -0500, Roy Smith wrote:

> Is this a homework problem?

and then (paraphrasing):

> working code that solves the problem

/headdesk


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#65789

In article <52f80bca$0$29972$c3e8da3$5496439d@news.astraweb.com>,
 Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:

> On Sun, 09 Feb 2014 10:05:02 -0500, Roy Smith wrote:
> 
> > Is this a homework problem?
> 
> and then (paraphrasing):
> 
> > working code that solves the problem
> 
> /headdesk

I gave him the benefit of the doubt.

Also, as I look at my solution, I realize it doesn't really meet the 
O(1) space requirement.  Understanding why is left as an exercise for 
the reader :-)

[toc] | [prev] | [next] | [standalone]

#65795

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

[toc] | [prev] | [next] | [standalone]

#65804

Wesley <nispray@gmail.com> wrote:
> [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.

[toc] | [prev] | [next] | [standalone]

#65884

On Mon, 10 Feb 2014 10:20:33 +0000, Sturla Molden wrote:

> Wesley <nispray@gmail.com> wrote:
>> [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.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#65962

Steven D'Aprano wrote:
> 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.

-- 
Greg

[toc] | [prev] | [next] | [standalone]

#65886

On 02/10/2014 04:20 AM, Sturla Molden wrote:
> 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     tundra@tundraware.com
PGP Key:         http://www.tundraware.com/PGP/

[toc] | [prev] | [next] | [standalone]

#65887

On 02/10/2014 04:20 AM, Sturla Molden wrote:
> 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     tundra@tundraware.com
PGP Key:         http://www.tundraware.com/PGP/

[toc] | [prev] | [next] | [standalone]

#65806

On Mon, Feb 10, 2014 at 9:20 PM, Sturla Molden <sturla.molden@gmail.com> wrote:
> Wesley <nispray@gmail.com> wrote:
>> [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.

That's assuming it really is a sort operation. The problem description
isn't entirely clear on this point, but if it's actually a zip, then
it can definitely be done in O(n).

ChrisA

[toc] | [prev] | [next] | [standalone]

#65822

Chris Angelico <rosuav@gmail.com> wrote:

> That's assuming it really is a sort operation. The problem description
> isn't entirely clear on this point, but if it's actually a zip, then
> it can definitely be done in O(n).

Ah, I didn't read it carefully enough. :-)

Granted, a zip can be done in O(n) time and O(1) memory using a generator,
which by the way is what itertools.izip does.

Sturla

[toc] | [prev] | [next] | [standalone]

#65824

On Tue, Feb 11, 2014 at 2:03 AM, Sturla Molden <sturla.molden@gmail.com> wrote:
> Chris Angelico <rosuav@gmail.com> wrote:
>
>> That's assuming it really is a sort operation. The problem description
>> isn't entirely clear on this point, but if it's actually a zip, then
>> it can definitely be done in O(n).
>
> Ah, I didn't read it carefully enough. :-)
>
> Granted, a zip can be done in O(n) time and O(1) memory using a generator,
> which by the way is what itertools.izip does.

Right. I poked around in itertools but nothing was quite what I was
after, so I ended up writing my own generator. But it's still a zip
operation, and as such, is just a variant form of iterating over the
original list. All I do is follow a pattern other than the Red King's
"Begin at the beginning, go on till you come to the end, then raise
StopIteration" (or words to that effect).

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web