Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

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

1
Skriv svar
Permalänk
Medlem
●

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?

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

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?

Visa signatur

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 | U2719D | Filco Majestouch 2 MX Brown TKL

Redigera
Citera flera Citera
Permalänk
Medlem
●

@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.";
Redigera
Citera flera Citera
Permalänk
Medlem
●

@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;
}
Redigera
Citera flera Citera
Permalänk
Medlem ★
●
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?

Gå till inlägget

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

Senast redigerat
Redigera
Citera flera Citera
Permalänk
Medlem
●

@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!

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara