Re: help how to sort a list in order of 'n' in python without using inbuilt functions??

From	Jussi Piitulainen <jpiitula@ling.helsinki.fi>
Newsgroups	comp.lang.python
Subject	Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
Date	2013-05-25 17:59 +0300
Organization	University of Helsinki
Message-ID	<qot8v3314x9.fsf@ruuvi.it.helsinki.fi> (permalink)
References	<e31fbc7c-1bc0-4f9a-9f1d-68f963a9ec39@googlegroups.com> <78192328-b31b-49d9-9cd6-ec742c092a29@googlegroups.com> <roy-CAE16C.09295725052013@news.panix.com>

Show all headers | View raw

Roy Smith writes:

> In article <78192328-b31b-49d9-9cd6-ec742c092a29@googlegroups.com>,
>  lokeshkoppaka@gmail.com wrote:
> 
> > On Friday, May 24, 2013 1:34:51 PM UTC+5:30, lokesh...@gmail.com wrote:
> > > i need to write a code which can sort the list in order of 'n'
> > > without use builtin functions
> > > 
> > > can anyone help me how to do?
> > 
> >  Note:
> > the list only contains 0's,1's,2's
> > need to sort them in order of 'n'
> 
> What do you mean by "need to sort them in order of 'n'".  Are you
> saying that you need to sort them into numerical order?  Or that you
> need to running time of the algorithm to be O(n)?
> 
> I'm assuming the later, in which case this is starting to sound like
> a classic interview question.
> 
> Assuming you can accept an unstable sort, there's an easy solution.
> I'm not aware of any solution if you require a stable sort.  Perhaps
> that's enough of a hint?

Surely it's assumed that each element of the input list can be
classified as 0, 1, or 2 in O(1) time. If O(n) auxiliary space can be
allocated in O(n) time, just put the 0's in their own list in the
order they are encountered, 1's in their own list in the order they
are encountered, 2's in their own list in the order they are
encountered, then put the 0's back into the input list in the order
they are encountered in their auxiliary list, followed by the 1's,
followed by the 2's. Stable and O(n), no?

Even ( [ x for x in input if x.key == 0 ] +
       [ x for x in input if x.key == 1 ] +
       [ x for x in input if x.key == 2 ] ).
I suppose a list comprehension is not technically a function any more
than a loop is.

(Neither stability nor O(1) space has been required yet, I think.)

Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

help how to sort a list in order of 'n' in python without using inbuilt functions?? lokeshkoppaka@gmail.com - 2013-05-24 01:04 -0700
  Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-24 18:12 +1000
  Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Dave Angel <davea@davea.name> - 2013-05-24 08:33 -0400
  RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-24 16:06 +0300
  Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? lokeshkoppaka@gmail.com - 2013-05-24 22:15 -0700
    Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 15:24 +1000
      Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? lokeshkoppaka@gmail.com - 2013-05-24 22:39 -0700
        Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 15:43 +1000
        Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-25 05:57 +0000
          Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? lokeshkoppaka@gmail.com - 2013-05-24 23:05 -0700
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 16:12 +1000
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 10:53 +0300
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 18:28 +1000
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 11:43 +0300
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 18:47 +1000
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 11:54 +0300
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 19:01 +1000
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 12:10 +0300
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-25 19:14 +1000
              Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-25 14:28 +0000
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Fábio Santos <fabiosantosart@gmail.com> - 2013-05-25 15:46 +0100
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-05-25 16:03 +0100
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-26 01:41 +1000
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-26 03:09 +0000
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-26 14:02 +1000
                RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 20:12 +0300
                RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 20:17 +0300
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-26 03:23 +1000
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-26 03:38 +0000
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Dan Sommers <dan@tombstonezero.net> - 2013-05-26 04:06 +0000
                Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Chris Angelico <rosuav@gmail.com> - 2013-05-26 14:28 +1000
                RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 20:34 +0300
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 12:30 +0300
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2013-05-25 13:01 +0100
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Roy Smith <roy@panix.com> - 2013-05-25 10:03 -0400
              Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Dave Angel <davea@davea.name> - 2013-05-25 10:27 -0400
            Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-25 14:30 +0000
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 20:07 +0300
            RE: help how to sort a list in order of 'n' in python without using inbuilt functions?? Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 20:45 +0300
    Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? rusi <rustompmody@gmail.com> - 2013-05-24 22:43 -0700
    Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Roy Smith <roy@panix.com> - 2013-05-25 09:29 -0400
      Re: help how to sort a list in order of 'n' in python without using inbuilt functions?? Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-05-25 17:59 +0300

csiph-web