Hjälp mig med att förstå vad som blev fel (bubblesort)

Trädvy Permalänk
Medlem
Registrerad
Jul 2013

Hjälp mig med att förstå vad som blev fel (bubblesort)

Hej!
Har gjort bubblesort på 4 familjemedlemmar och den ska sortera i ordning och därefter tala om vilken plats.

Se nedanför.

#include <iostream> #include <string> #include <vector> using namespace std; class person { public: string name; int age; void print() { cout << "Name: " << name <<", "<< age << " years old." << endl; } void setInfo(string _name, int _age) { name = _name; age = _age; } }; int linearsearch(person p[], int n, int a) { for (int i = 0; i < n; i++) { if (p[i].age == a) return i; } return -1; }; void bubblesort(person p[], int n) { for (int i = 0; i < n; i++) { int nrLeft = n - i; for (int j = 0; j < nrLeft; j++) { if (p[j].age > p[j+1].age) { person temp = p[j]; p[j] = p[j+1]; p[j+1] = temp; } } } } int main() { cout << " Unsorted list " << endl; person family[3]; family[0].setInfo("Johanna", 9); family[0].print(); family[1].setInfo("Per", 3); family[1].print(); family[2].setInfo("Gunnar", 37); family[2].print(); family[3].setInfo("Maja", 36); family[3].print(); cout << endl << " Sorted list " << endl; bubblesort(family, 4); for (int i = 0; i < 4; i++) cout << "Name: " << family[i].name << ", " << family[i].age << " years old." << endl; int index = linearsearch(family, 4, 36); if (index == -1) cout << "The person can't be find!"; else cout << endl << family[index].name << " can be find on place " << index << " in the list."; cin.get(); return 0; }

När jag startar programmet

Unsorted list Name: Johanna, 9 years old. Name: Per, 3 years old. Name: Gunnar, 37 years old. Name: Maja, 36 yers old. Sorted list Name: Per, 3 years old. Name: Johanna, 9 years old. Name: Maja, 36 years old. Name: Gunnar, 37 years old. Maja can be find on place 2 in the list.

Maja hamnar på andra plats och det stämmer inte.
Någon som kan förklara för mig vad jag har missat?

Fractal Define R4 - B350 GA-AB350M-Gaming 3 - Ryzen 5 2600 3.9 GHz + NZXT Kraken x42 - Corsair Vengeance 2133mhz 2x8GB - RX580 Pulse 8GB

Trädvy Permalänk
Medlem
Plats
Örebro
Registrerad
Jan 2010

Inte bara så att det är nollindexering fast du förväntar dig att den börjar på 1?
Förväntar du dig att svaret skall bli plats 3?

i7 8700k @ 4.7GHz | NH-L12 | ASUS Z270i ROG Strix Gaming | EVGA 1080 FTW | 32GB Corsair Vengeance 3000MHz | Samsung 970 Evo M.2 500GB, 840 250GB, Crucial MX500 2TB | Loque Ghost S1 | XB271HU | QX2710 | U2412M | Filco Majestouch MX Brown TKL

Trädvy Permalänk
Medlem
Registrerad
Maj 2019

@ortzon:

Felet är precis som föregående säger, nollindexering. Maja är ju faktiskt på index 2.

int linearsearch(person p[], int n, int a) { for (int i = 0; i < n; i++) { if (p[i].age == a) return i; //returnerar index. Kom ihåg att index börjar på 0. } return -1; };

Eftersom Maja finns på index 2, och du skriver ut värdet hos variabeln index kommer självklart utskriften att bli 2.Om du vill veta platsen som Maja (eller någon annan familjemedlem) befinner sig på istället för index så behöver du bara addera en etta i utskriften av värdet i variabeln, dvs ändra denna rad:

cout << endl << family[index].name << " can be find on place " << index << " in the list.";

till detta:

cout << endl << family[index].name << " can be find on place " << index + 1 << " in the list.";

Trädvy Permalänk
Medlem
Registrerad
Jul 2013

@Amoux: och @era909

Tack! Den har jag missat! Nu har jag lärt mig något!

Nästa fråga är, enligt skoluppgiften ska jag gärna använda följande funktion i programmet

void byt(Person &p, Person &q) { Person temp; temp.namn = p.namn; temp.alder = p.alder; p.namn = q.namn; p.alder = q.alder; q.namn = temp.namn; q.alder = temp.alder; }

Så jag lade in med funktionen i programmet och programmet funkar som vanligt med eller utan. Vad spelar det för roll egentligen?

#include <iostream> #include <string> #include <vector> using namespace std; class person { public: string name; int age; void print() { cout << "Name: " << name <<", "<< age << " years old." << endl; } void setInfo(string _name, int _age) { name = _name; age = _age; } }; int linearsearch(person p[], int n, int a) { for (int i = 0; i < n; i++) { if (p[i].age == a) return i; } return -1; }; void bubblesort(person p[], int n) { for (int i = 0; i < n; i++) { int nrLeft = n - i; for (int j = 0; j < nrLeft; j++) { if (p[j].age > p[j+1].age) { person temp = p[j]; p[j] = p[j+1]; p[j+1] = temp; } } } } { Person temp; temp.namn = p.namn; temp.alder = p.alder; p.namn = q.namn; p.alder = q.alder; q.namn = temp.namn; q.alder = temp.alder; } int main() { cout << " Unsorted list " << endl; person family[3]; family[0].setInfo("Johanna", 9); family[0].print(); family[1].setInfo("Per", 3); family[1].print(); family[2].setInfo("Gunnar", 37); family[2].print(); family[3].setInfo("Maja", 36); family[3].print(); cout << endl << " Sorted list " << endl; bubblesort(family, 4); for (int i = 0; i < 4; i++) cout << "Name: " << family[i].name << ", " << family[i].age << " years old." << endl; int index = linearsearch(family, 4, 36); if (index == -1) cout << "The person can't be find!"; else cout << endl << family[index].name << " can be find on place " << index+1 << " in the list."; cin.get(); return 0; }

Fractal Define R4 - B350 GA-AB350M-Gaming 3 - Ryzen 5 2600 3.9 GHz + NZXT Kraken x42 - Corsair Vengeance 2133mhz 2x8GB - RX580 Pulse 8GB

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
Skrivet av ortzon:

Så jag lade in med funktionen i programmet och programmet funkar som vanligt med eller utan. Vad spelar det för roll egentligen?

Koden du visar är felaktig, du kan inte ha ett fristående { }-block som du har nu. Missade du kanske första raden av funktions-deklarationen?

Hur som helst så är tanken att du ska använda funktionen i din bubblesort-funktion, istället för att byta plats på personer med

person temp = p[j]; p[j] = p[j+1]; p[j+1] = temp;

som du har nu. Ditt sätt att byta plats är egentligen bättre än den i byt-funktionen som du fått, eftersom din kod använder den automatgenererade =-operator för din klass. Men det är kanske lite överkurs just nu. Denna operation är dock så vanlig att det bästa sättet att byta värde på två variabler är att använda std::swap från standardbiblioteket:

std::swap(p[j], p[j+1]);

Men om uppgiften säger att du ska använda byt-funktionen istället så är det bäst att göra det för att uppfylla kraven i uppgiften.

Sen har du lite buggar i din kod som du kanske inte märkt av. Den första är att du deklarerat din family-array att ha 3 element, men du använder 4 element i den. Den andra buggen är att du i din bubblesort-funktion ibland kommer försöka komma åt t.ex. det 5:e elementet i din array med 4 element. Detta eftersom nrLeft = n - i innebär att nrLeft får värdet 4 när n är 4 och i är 0, vilket gör att j+1 kommer bli 4 som mest (vilket som du märkt är det 5:e elementet i arrayen).

Båda dessa buggarna handlar alltså om att du försöker läsa och skriva till ett element utanför arrayen. Detta orsakar vad som i C++-sammanhang kallas för odefinierat beteende, vilket betyder att programmet kan fungera normalt, krascha, eller få ditt tangentbord att fatta eld beroende på vad som finns i minnet du försöker komma åt. Om programmet kraschar så har man tur, annars kan såna buggar ligga och lurpassa och börja orsaka en massa konstiga problem när man senare ändrar på något annat i koden.

Tillägg:
Detta är rätt mycket överkurs, men du kan deklarera din array så här:

person family[4] = { {"Johanna", 9}, {"Per", 3}, {"Gunnar", 37}, {"Maja", 36} };

På det sättet kan du inte deklarera arrayen med fel storlek, eftersom kompilatorn kommer ge ett fel om du skriver in för få eller för många element. Detta använder s.k. uniform initialization, vilket innebär att man kan använda { } för att skapa instanser av klasser som uppfyller vissa villkor (vilket din person-klass råkar göra). I "riktig" C++-kod skulle man dock använda t.ex. std::array istället för en gammaldags array. Men som sagt, rätt mycket överkurs

Trädvy Permalänk
Medlem
Registrerad
Jul 2013

@perost:

Hej!
Jag har lärt mig mycket. Bra att du tog upp viktiga saker som jag har missat.

Jag tror att jag har fått programmet att fungera än så länge.

Tack!

Fractal Define R4 - B350 GA-AB350M-Gaming 3 - Ryzen 5 2600 3.9 GHz + NZXT Kraken x42 - Corsair Vengeance 2133mhz 2x8GB - RX580 Pulse 8GB