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

Gör ett nytt projekt som heter sorteringsalgoritmer.

klassen Numbers

Fält

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

Konstrukor

Vektorn numbers skapas och ges fem platser. Ge de fem elementen slumpvärden, tvåsiffriga heltal. Använd klassen Random för att skapa slumptal. Du har gjort det förut i klassen Dice.

Metoden - print()

Utskriften ska bli som nedan.

23, 45, 12, 56, 67,

Använd en for-slinga.

Metoden - makeRandomNumbers()

Metoden fyller vektorn med slumptal. Använd en for-slinga. Anropa metoden i konstruktorn.

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)