0200 Sorteringsalgoritmer

För E till C räcker det att du kan implementerar en av nedanstående sorteringsalgoritmer. Du väljer själv vilken. För B till A behöver du kunna implementera samtliga sortingsalgoritmer.

Demonstration av sorteringsalgoritmer

Gör ett nytt projekt som heter sorteringsalgoritmer.

klassen MinaTal

Egenskap

Objektvariabeln numbers är en vektor, som kan innehålla heltal.

Konstruktor

Vektorn numbers skapas och ges fem platser. Ge de fem elementen slumpvärden, tvåsiffriga heltal. Utskrifterna blir snyggare om det är tvåsiffriga heltal. Använd klassen Random för att skapa slumptal.

Metoden - print()

Utskriften ska bli som nedan.

23, 45, 12, 56, 67,

Använd en while-slinga.

Metoden - makeRandomNumbers()

Metoden fyller vektorn med tvåsiffriga slumptal. Använd en while-slinga. Anropa metoden i konstruktorn.

Metoden swap_2_4

Metoden byter plats på talen i vektorn som har index 2 och 4.

//given vektor

//0, 1, 2, 3, 4 (index)

//6, 7, 8, 9, 5 (element)

swap_2_4();

//ger vektorn, ändrade element i fet stil

//0, 1, 2, 3, 4 (index)

//6, 7, **5**, 9, **8** (element)

Pseudokod för att byta plats på värdet i variablerna x och y:

  1. Skapa en variabel temp.
  2. Lägg x i temp.
  3. Lägg y i x.
  4. Lägg temp i y.
  5. Testa att metoden fungerar.

Metoden - swap()

Metoden ska ta två parametrar som båda är heltal. I metoden byter elementen i vektorn numbers med givna index plats. Ett exempel ges nedan.

//given vektor

//0, 1, 2, 3, 4 (index)

//6, 7, 8, 9, 5 (element)

swap(2, 4);

//ger vektorn, ändrade element i fet stil

//0, 1, 2, 3, 4 (index)

//6, 7, **5**, 9, **8** (element)

Pseudokod för att byta plats på värdet i variablerna x och y:

  1. Skapa en variabel temp.
  2. Lägg x i temp.
  3. Lägg y i x.
  4. Lägg temp i y.
  5. Testa att metoden fungerar.

Bubbelsortering (eng. Bubble sort)

För en vektor x, jämför x[0] med x[1]. Byt plats på dem om de inte är i rätt ording. Gör samma sak för nästa par i vektorn d.v.s. x[1] och x[2]. Gör samma sak för var och ett av paren i vektorn. Upprepa hela proceduren ovan lika många gånger som vektorn är lång.

Skriv en metod bubbleSort i klassen Numbers. Ett exempel på sortering följer nedan. Exemplet nedan är lite effektivare än ovanstående beskrivning. Skillnaderna är relativt små, men gör sorteringen ungefär dubbelt så snabb. För högre betyg kan du försöka att implementera den effektivare algoritmen. Skriv i så fall pseudokod först.

//Exempel: vill sortera från lägsta till högsta

0 1 2 3 4 //index

9 5 7 3 1 //tal

9 5 7 3 1 //fetmarkerade tal jämförs

5 9 7 3 1 //9 har bytt plats med 5. 9 har börjat bubbla åt höger.

5 9 7 3 1

5 7 9 3 1 //9 och 7 har bytt plats, 9 har bubblat åt höger

5 7 9 3 1

5 7 3 9 1 //9 och 3 har bytt plats, 9 har bubblat vidare åt höger

5 7 3 9 1

5 7 3 1 9 //9 byter plats med 1, 9 har bubblat hela vägen till höger

//Obs: elementet längst till höger är störst, så kommer det alltid vara. Att visa det lämnas som övning.

//börjar om från vänster

5 7 3 1 9 //5 och 7 är i rätt ordning

5 7 3 1 9

5 3 7 1 9 //7 och 3 har bytt plats

5 3 7 1 9

5 3 1 7 9 //7 och 1 har bytt plats

//nu är 7 och 9 fördigsorterade

//Börja om från vänster igen. Vi vet att det sista elementet är störst.

5 3 1 7 9

3 5 1 7 9 //5 och 3 har bytt plats

3 5 1 7 9

3 1 5 7 9 // 5 och 1 har bytt plats

//Dags att börja om från vänster igen eftersom 5, 7, 9 är sorterade.

3 1 5 7 9

1 3 5 7 9 //3 och 1 har bytt plats

//klart

//Har du tänkt på att de stora talen har bubblat åt höger.

Urvalssortering (eng. Selection sort)

För en vektor x med heltal, byt plats på x[0] och det minsta elementet. Fortsätt med att byta plats på det näst minsta elementet och x[1], o.s.v.

En alternativ beskrivning följer. För en vektor x med (n + 1) heltal, byt plats på det minsta elementet och vektorns första element x[0]. Fortsätt med att byta plats på det minsta elementet, bland index 1 - n, och x[1]. Byt plats på det minsta elementet, bland index 2 - n, och x[2]. Fortsätt på samma sätt.

Insättningssortering (eng. Insertion sort)

För en vektor x med heltal,

  1. byt plats på x[1] och x[0] om de är i fel ordning.
  2. Byt därefter plats på x[2] och x[1] om de är i fel ordning.
  3. Om x[1] och x[0] är i fel ordning byt plats på dem.
  4. Nu är x[0] <= x[1] <= x[2].
  5. Fortsätt på samma sätt och byt succesivt plats på x[3], med elementen med lägre index tills x[3] är på rätt plats.
  6. P.s.s. med x[4] ...

//Exempel, element i fet stil jämförs

0, 1, 2, 3, 4 (index)

9, 2, 5, 6, 7 (element)

9, 2, 5, 6, 7 Flytta in x[1] på rätt plats. (byt plats på 9 och 2)

2, 9, 5, 6, 7 Flytta in x[2] på rätt plats. (byt plats på 9 och 5)

2, 5, 9, 6, 7 (2 och 5 är i rätt ordning)

2, 5, 9, 6, 7 Flytta in x[3] på rätt plats. (byt plats på 9 och 6)

2, 5, 6, 9, 7 (5 och 6 är i rätt ordning)

2, 5, 6, 9, 7 Flytta in x[4] på rätt plats. (byt plats på 9 och 7)

2, 5, 6, 7, 9 (6 och 7 är i rätt ordning => klar)

Extra för höga betyg

Gör om ovanstående algoritmer så att vektorn med tal kan vara av godtycklig storlek.