Sorteer een lijst efficiënt die alleen 0 en 1 bevat zonder een ingebouwde python-sorteerfunctie te gebruiken?

Er zijn veel verschillende algemene sorteeralgoritmen die kunnen worden gebruikt. In dit geval is de belangrijkste overweging echter dat alle te sorteren elementen tot de set behoren (0,1).

Zoals andere respondenten hebben geantwoord, is er een triviale implementatie.

def radix_sort(a):
    slist = [[],[]]
    for elem in a:
        slist[elem].append(elem)
    return slist[0] + slist[1]

print radix_sort([0,0,1,0,1,1,0])

Er moet worden opgemerkt dat dit een specifieke implementatie is van de Radix-sortering . En dit kan eenvoudig worden uitgebreid als de elementen van de lijst die moet worden gesorteerd tot een gedefinieerde beperkte reeks behoren.

def radix_sort(a, elems):
    slist = {}
    for elem in elems:
        slist[elem] = []
    for elem in a:
        slist[elem].append(elem)
    nslist = []
    for elem in elems:
        nslist += slist[elem]
    return nslist

print radix_sort([2,0,0,1,3,0,1,1,0],[0,1,2,3])

Geen sorteer() of sorteer() of tel() functie. Op)

Deze is O (n) (je kunt niet minder krijgen):

old = [0,0,1,0,1,1,0]
zeroes = old.count(0) #you gotta count them somehow!
new = [0]*zeroes + [1]*(len(old) - zeroes)

Omdat er geen Python-loops zijn, kan dit hoe sneller je kunt krijgen in pure Python ...

def sort_arr_with_zero_one ():

  main_list = [0,0,1,0,1,1,0]
  zero_list = []
  one_list = []
  for i in main_list:
    if i:
        one_list.append(i)
    else:
        zero_list.append(i)

  return zero_list + one_list

Ik zou dit proberen:

b = [0,0,1,0,1,1,0]

def odd_sort(a):
  zeroes = a.count(0)

  return [0 for i in xrange(zeroes)] + [1 for i in xrange(len(a) - zeroes)]

U kunt de lijst met twee aanwijzers lopen, één vanaf het begin ( i ) en vanaf het einde ( j ) en de waarden één voor één vergelijken en zo nodig verwisselen :

def sort_binary_values(l):
    i, j = 0, len(l)-1
    while i < j:
        # skip 0 values from the begin
        while i < j and l[i] == 0:
            i = i+1
        if i >= j: break
        # skip 1 values from the end
        while i < j and l[j] == 1:
            j = j-1
        if i >= j: break
        # since all in sequence values have been skipped and i and j did not reach each other
        # we encountered a pair that is out of order and needs to be swapped
        l[i], l[j] = l[j], l[i]
        j = j-1
        i = i+1
    return l

Ik vind het antwoord van JBernado leuk, maar zal een andere monsterlijke optie inslaan (hoewel ik er nog geen profilering op heb gezet - het is niet bijzonder uitbreidbaar omdat het afhankelijk is van de volgorde van een woordenboek-hash, maar werkt voor 0 en 1):

from itertools import chain, repeat
from collections import Counter

list(chain.from_iterable(map(repeat, *zip(*Counter(bits).items()))))

Of - iets minder ingewikkelde ...

from itertools import repeat, chain, islice, ifilter
from operator import not_

list(islice(chain(ifilter(not_, bits), repeat(1)), len(bits)))

Dit zou alles op C-niveau moeten houden - dus het zou redelijk optimaal moeten zijn.

U hebt slechts twee waarden, dus u weet van tevoren de exacte structuur van de uitvoer: deze wordt verdeeld in twee regio's van verschillende lengtes.

Het enige dat u moet weten, is hoe lang de originele reeks is en hoeveel er in zitten.

old = [0,0,1,0,1,1,0]
ones = sum(1 for b in old if b)
new = [0]*(len(old)-ones) + [1]*ones