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

What is the most efficient way to sort a list, [0,0,1,0,1,1,0] whose elements are only 0 & 1, without using any builtin sort() or sorted() or count() function. O(n) or less than that

2
lijst begrip
toegevoegd de auteur Burhan Khalid, de bron

9 antwoord

>>> lst = [0,0,1,0,1,1,0]
>>> l, s = len(lst), sum(lst)
>>> result = [0] * (l - s) + [1] * s
>>> result
[0, 0, 0, 0, 1, 1, 1]
9
toegevoegd
+1 - voldoet aan de vereisten om count() niet te gebruiken
toegevoegd de auteur Burhan Khalid, de bron

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)

4
toegevoegd
Schaduw de ingebouwde functies of gegevenstypen ( id en set in uw geval) alstublieft niet af)
toegevoegd de auteur astynax, de bron

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 ...

2
toegevoegd
Oh, natuurlijk ... De PyObject_RichCompareBool controleert op identiteit en alleen dan op waarde. Dat is ook het gedrag bij het ophalen van dict .
toegevoegd de auteur JBernardo, de bron
@Blender @ asyntax Als de python-broncode wordt gecontroleerd, roept de methode .count de functie PyObject_RichCompareBool aan. Met grote lijsten met alleen nullen en lijsten met alleen enen, fluctueert de timing veel (van 0,3 tot 2 seconden), terwijl dat met sum niet het geval is. Misschien doet deze functie wat funky dingen.
toegevoegd de auteur JBernardo, de bron
@Blender dat is wat ik ging zeggen :)
toegevoegd de auteur JBernardo, de bron
Tussen haakjes, ik ben 10x kwaad (6660) ... Gewoon voor de goede orde;)
toegevoegd de auteur JBernardo, de bron
@astynax Interessant. In Python 2.x is het waar voor grote lijsten maar op Python 3.x (waar ik aan het testen was), het is niet waar waarschijnlijk vanwege het nieuwe int type dat lijkt op de oude lange type.
toegevoegd de auteur JBernardo, de bron
.count() is 15% sneller (voor mij). Gebruik de module timeit en ontdek het zelf.
toegevoegd de auteur Blender, de bron
Getest zowel deze oplossing als alle andere. Het is momenteel het snelst.
toegevoegd de auteur Blender, de bron
@astynax: ik zou voorzichtig zijn met die syntaxis. Het doet niet wat u denkt dat het doet bij het initialiseren van gegevens .
toegevoegd de auteur Blender, de bron
@Blender, data = [0,1] * 10000 , 1000 iteraties: sum (data) - 0.561300992966, data.count (0) - 0.661532878876
toegevoegd de auteur astynax, de bron
@Blender, [0,1] * 10000 = [0,1,0,1,0,1 ....] . Deze syntaxis veilig als de lijst alleen onveranderlijke objecten bevat (zoals 1 en 0 ) :)
toegevoegd de auteur astynax, de bron
@JBernardo, ik heb dit getest met Python 2.7 :)
toegevoegd de auteur astynax, de bron
count_of_ones = som (oud) :)
toegevoegd de auteur astynax, de bron

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
1
toegevoegd
Ik koos het antwoord van astynax als het antwoord omdat het meer stemmen heeft. Maar ik kon de jouwe heel gemakkelijk begrijpen dan alle anderen. En zelfs u gebruikte niet sorteren, gesorteerd of tellen. en ik denk ook zijn o (n). Dankje voor het antwoord
toegevoegd de auteur Bruce Wayne, de bron

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)]
0
toegevoegd

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
0
toegevoegd

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.

0
toegevoegd
Het is vermeldenswaard dat het eerste codeblok met elke int (ten minste in CPython waar hash (int) == int) werkt, maar de tweede is puur 0/1
toegevoegd de auteur Jon Clements, de bron

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.

0
toegevoegd

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
0
toegevoegd
Wil je echt een lijst genereren om de lengte ervan te krijgen? Het kan beter worden geschreven als sum (1 voor i in oud als i)
toegevoegd de auteur Jon Clements, de bron
@Jon Clements: Ja, dat is nog beter. Antwoord geüpdatet - bedankt.
toegevoegd de auteur martineau, de bron