Differences

This shows you the differences between two versions of the page.

Link to this comparison view

exempel_och_uppgifter [2017-09-01 14:54]
exempel_och_uppgifter [2022-07-18 13:20] (current)
Line 1: Line 1:
 +===== Sortering =====
 +
 +==== Insättningssortering ====
 +Gå igenom det osorterade objektet och sätt eftersom in motsvarande värden på rätt plats i ett från början tomt sorterat objekt.
 +
 +Ex.\\
 +{{insattning.jpg|}}
 +
 +==== Urvalssortering ====
 +Välj elementen i rätt ordning från det osorterade objektet och sätt in dem eftersom i ett från början tomt objekt.
 +
 +Ex.\\
 +{{urval.jpg|}}
 +
 +==== Utbytessortering ====
 +Element som ligger inbördes fel i det osorterade objektet får byta plats så att det så småningom blir ett sorterat objekt. Det finns flera metoder för hur detta kan ske. Ett exempel är **bubbelsortering**. Objektet gås igenom i flera svep tills det är sorterat. I varje svep byter man plats på två element efter varandra ifall de står i fel ordning. Som mest behövs det ett svep mindre än antal element i objektet.
 +
 +Ex.\\
 +{{utbyte.jpg|}}
 +
 +
 +===== Sökning =====
 +
 +==== Sökning i sorterat objekt ====
 +En fördel med sökning i ett sorterat objekt är att när man nått fram till den position där det sökta värdet borde ha varit, utan att finna det, så behöver man inte söka vidare.
 +
 +==== Binärsökning ====
 +I ett sorterat objekt med index räknar man ut det index som ligger mitt emellan två andra index. Ifall elementet med det indexet inte är det sökta så väljer man den halva där sökt värde bör finnas. Sedan halverar man intervallen successivt tills man hittat värdet eller kommit till ett delintervall med längd 1 utan att hitta värdet.
 +
 +===== Uppgifter =====
 +
 +I alla uppgifterna ska huvudprogrammet läsa in data in från filen //[[http://www3.park.se/~daniel/talfil.txt|talfil]]// till ett fält med storlek 1000. Funktionerna bör dock kunna fungera även för fält av annan storlek. Alla sorterade objekt ska också vara fält, d.v.s. inga STL-klasser får användas.
 +
 +==== Uppgift 1 ====
 +Gör en funktion som söker efter ett visst tal i det osorterade fältet och skriver ut positionen för alla förekomster av talet. Ange även hur många jämförelser som utförs under sökningen.\\
 +Exempel på resultat:\\
 +Tal 782 finns på positionerna 0 och 914.\\
 +Tal 157 finns på positionerna 109, 225 och 976.\\
 +Tal 5 finns inte med.
 +
 +==== Uppgift 2 ====
 +Gör en funktion som sorterar fältet med **insättningssortering** och returnerar det sorterade fältet. Programmet ska även skriva de sorterade värdena till en ny fil.
 +
 +==== Uppgift 3 ====
 +Gör en funktion som sorterar fältet med **urvalssortering** och returnerar det sorterade fältet. Programmet ska även skriva de sorterade värdena till en ny fil.
 +
 +==== Uppgift 4 ====
 +Gör en funktion som sorterar fältet med **utbytessortering (bubbelsortering)** och returnerar det sorterade fältet. Programmet ska även skriva de sorterade värdena till en ny fil.
 +
 +==== Uppgift 5 ====
 +Gör en funktion som går igenom ett sorterat fält och söker efter ett visst tal och returnerar antal förekomster av talet. Sökningen avslutas när alla förekomster av talet hittats eller när man, utan att hitta det talet, nått fram till den position där det borde ha funnits. Ange även hur många jämförelser som utförs under sökningen.
 +
 +==== Uppgift 6 ====
 +Gör en funktion som använder binärsökning för att söka efter ett tal och returnerar ifall talet finns med eller inte. Ange även hur många jämförelser som utförs under sökningen.