Sist endret: 23.09.2016  
 

Praksisoppgave - Pipesortering

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 18.09.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
pipesorting.py, pipesorting_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
pipesorting.py Funksjonene sort(A) og find(A, lower, upper)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 12 140
12 70

Pipesortering

Det er ikke nødvendig å lese historien for å løse oppgaven.

Etter å ha reddet Tellus fra å få spredd sine atomer utover hele solsystemet, tok Algemannen og Kobra seg en langhelg. Da de kom på jobb igjen på tirsdag, var de uthvilte, og klare for å gjøre en ny innsats for menneskeheten.

Når Kobra kommer inn i arbeidsværelset, sitter Algemannen og ser på mobilen sin. Han har dype rynker i pannen.
- Jeg har nettop fått en SMS fra dr. Gewalt. Han har blitt forkjølet.
- Å, nei! Vi har et kjempeproblem!
- Ta det lungt, det finnes alltid farer som superhelter kan redde verden fra, sier Algemannen inspirert. Det er kommer alltids et vulkanutbrudd eller en komét.
- Enn hvis det ikke gjør det? Enn om vi blir sittende her og tvinne tommeltotter hele uken? Enn om vi dør av kjedsomhet, eller begynner å skrive assembler?

Algemannen må finne på noe for å sysselsette sin hyperaktive hjelper. Han har en stor samling av tobakkspiper, som ligger i et forferdelig rot i en skuff.
- Kobra, kan ikke du sortere pipene mine, slik at jeg lettere finner frem i dem? Jeg har alltid et svare strev med å finne en som er passe stor for anledningen.
- Sortering? Jo, det er lett! Jeg sorterer sokkene mine hver dag.

Algemannens piper

Oppgave

Når du skal implementere en algoritme, ønsker du ofte å gjøre litt forarbeid, slik at du skal kunne behandle dataene mer effektivt. Sortering er en teknikk du ofte bruker for senere å kunne søke raskere. Du skal nå implementere en fritt valgt sorteringsalgoritme. Lag en funksjon sort_list som tar en liste (et array) av heltall som parameter, og returnerer listen sortert i stigende rekkefølge.

Etter at du har sortert dataene dine, skal du utføre søk i dem. Lag en funksjon find som tar en liste av heltall, en nedre og en øvre grense som parametre. Denne funksjonen skal finne et intervall som er minst like stort som de oppgitte grensene representerer. Hvis vi f.eks. har tallene [0,2,4,6,8], nedre og øvre grense (2, 7), skal du returnere tallene [2,8]. Hvis oppgitt nedre eller øvre grense er utenfor verdiområdet til lista må du returnere det beste du klarer med verdiene i lista. Hvis du får oppgitt nedre og øvre grense (10, 14) og lista [11,12,13] skal du altså returnere [11, 13].

Skriv ut tallene med mellomrom på en linje. For å søke i sorterte data kan man bruke binærsøk (beskrevet f.eks. her). Binærsøk er avhengig av at tallene dine er lagret i et array for å være effektivt. I et array kan vilkårlige elementer hentes ut i konstant tid, mens i f.eks. en lenket liste, er oppslagstiden avhengig av størrelsen på lista.

Hvis du vil kan du bruke rammeverket under. Inndata til programmet er en liste av tall som skal sorteres, og en nedre og en øvre grense, separert med linjeskift. Ingen tall i inputen vil være mindre enn 0 eller større enn 1000000.

Det er ikke tillatt å bruke den innebygde list.sort(). Det er også juks å bruke modulen heapq og lignende. Moral: Alt som har med selve sorteringen og søk å gjøre må du gjøre selv. Det er ikke lov til å bruke innebygde funksjoner til å implementere sortering eller søk, som for eksempel bisect.

Rammeverk

#!/usr/bin/python3

from sys import stdin


def sort_list(A):
    # NOTICE: The sorted list must be returned.
    # SKRIV DIN KODE HER


def find(A, lower, upper):
    # NOTICE: The result must be returned.
    # SKRIV DIN KODE HER


def main():
    input_list = []
    for x in stdin.readline().split():
        input_list.append(int(x))

    sorted_list = sort_list(input_list)

    for line in stdin:
        word = line.split()
        minimum = int(word[0])
        maximum = int(word[1])
        result = find(sorted_list, minimum, maximum)
        print(str(result[0]) + " " + str(result[1]))


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Rammeverket i denne oppgaven gir folgende variabler. - 'input_list' er en liste med tall mellom 0 og 1 000 000. - 'list_sorted' er en liste med de samme tallene som i 'input_list', men i sortert rekkefolge. - 'minimum' er et tall som representerer nedre grense for intervallet som skal finnes - 'maximum' er et tall som representerer ovre grense for intervallet som skal finnes Variabelen 'sorted_list' blir satt ved at 'input_list' blir sendt som argument til funksjonen 'sort(A)', og det er opp til deg aa implementere denne funksjonen. Husk aa returnere den sorterte lista! Funksjonen 'find(A, lower, upper)' tar inn hhv. 'sorted_list', 'minimum' og 'maximum', dvs A representerer den sorterte lista.

Input-eksempel

12 90 5 18 140 130 143 70
17 135
12 45

Tilhørende output

12 140
12 70

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.