Hemtal 4

Lönar sig sortering?

Etthundratusen signerade och numrerade Organzineslipsar säljs varje år. För varje såld slips sparas en post med numret och köparens namn i en array och vid årets slut lottas hundra slipsnålar av guld ut bland köparna. Det går till så att hundra vinstnummer slumpas fram, ett efter ett.

För varje nummer måste hela arrayen letas igenom, eftersom den är osorterad. Hur många jämförelser får man räkna med totalt? Lönar det sej att först sortera arrayen, en gång för alla, för att därefter sökningarna ska gå fortare? Finns det bättre sätt?

Lönar sig bubbelsortering

En stor sorterad vektor råkar bli lite osorterad p.g.a. fumlighet. Det är ingen större skada skedd, man vet att det bara är några element som bytt plats med ett intilliggande element. Man beslutar sig för att använda bubbelsortering (enligt koden nedan) som en lämplig metod att sortera om vektorn.

def bubblesort(vek):
    for i in range(0, len(vek) - 1):    
        for j in range(0, len(vek) - i - 1):
            if vek[j] > vek[j+1]:      
                (vek[j], vek[j+1]) = (vek[j+1], vek[j])

Det visar sig att det går väldigt långsamt i alla fall. Varför?

Rättningsmall

Står namnet överst till höger?

Den som gjort uppgiften ska skriva sitt namn och personnummer överst till höger på alla papper. Den som rättar ska skriva sitt namn och personnummer, samt "G" eller "IG" överst till vänster på första pappret.

Är det tydligt skrivet?

Går det att begripa? Är något otydligt?

Är det bra tänkt?

Går det att följa tankgången? Om det bara står en rad kod utan kommentarer så går det inte att förstå.

Är det rätt svar?

Är det rätt svar? Svaren gås igenom på övning.