Mi a hiba ezzel a program részel?
template<class T>
void QuickSort<T>::qsort(T*a,int bal,int jobb)
{
int Piv_index;
if(bal<jobb)
{
Piv_index=particional(a,bal,jobb);
qsort(a,bal,Piv_index-1);
qsort(a,Piv_index,jobb);}
}
template<class T>
int QuickSort<T>::particional(T* a,int bal, int jobb)
{
T pivot=a[bal];
T balra,jobbra;
jobbra=a[jobb];
while(pivot<jobbra)
{
if(jobb<bal)break;
--jobb;
jobbra=a[jobb];
}
balra=a[bal];
a[bal]=jobbra;
while(pivot>balra)
{ if(jobb<=bal)break;
bal++;
balra=a[bal];
}
a[jobb]=balra;
a[balra]=pivot;
return bal;
}
Hali
Ha jól látom c++?
Esetleg ha megmondod, hogy mit ír ki a fordító. Miben fordítod? Mit akar csinálni?
Build started: Project: hazi3, Configuration: Debug Win32 ------
fo.cpp
c:\documents and settings\jonathán\asztal\vorosliba\hazi3\hazi3\fo.cpp(2): warning C4067: unexpected tokens following preprocessor directive - expected a newline
hazi3.vcxproj -> C:\Documents and Settings\Jonathán\Asztal\vorosliba\hazi3\Debug\hazi3.exe
========== Build: 1 succeeded, 0 failed, 0 up-to-date, 0 skipped ==========
Végtelen ciklus alakul ki, aminek a végén stack túlcsordulás lesz. Pl. legyen az első elem 5, az utolsó pedig 4, a középsők nem érdekesek. Ekkor a particional() így alakul:
pivot = 5;
jobbra = 4;
while (5 < 4) egyszer sem fut le // egyforma értéknél se futna!
balra = 5;
a[bal] = 4;
while (5 > 5) egyszer sem fut le
a[jobb] = 5;
a[bal] = 5; // eltűnt teljesen a 4-es érték!
return bal;
és ezek után a rekurzív hívás ugyanezekkel a bal,jobb indexekkel fog futni. Mivel az első és utolsó érték most már egyforma, és az első while ciklus egyforma értékeknél sem fut le, a rekurzió addig fut, amíg a gép bírja stack-kel.
Ha elkezded debug-olni, ez rögtön kiderül.
Egyébként a particional() rutin csak távolról hasonlít arra, amilyennek egy quick sort partícionálásnak lennie kellene. A jobb megvalósításhoz ötletet vehetsz pl. a wikipédiából:
Keresd a "Helyben rendező változat" fejezetet.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!