Valamert kifagy a quicksort implementaciom. Mi lehet a problema?
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAXDIM = 100;
int x[MAXDIM];
int feloszt(int bal, int jobb){
int strazsa = x[bal];
int i = bal - 1;
int j = jobb + 1;
do {
do{
j--;
}while(x[j] >= strazsa);
do {
i++;
}while(x[i] < strazsa);
if(i <= j)
swap(x[i], x[j]);
}while(i <= j);
return j;
}
void quicksort(int bal, int jobb){
if(bal < jobb){
int m = feloszt(bal, jobb);
quicksort(bal, m-1);
quicksort(m+1, jobb);
}
}
int main(){
for(int i = 0; i < 10; i++){
x[i] = 1 + rand() % 20;
cout << x[i] << " ";
}
quicksort(0, 9);
cout << endl << endl;
for(int i = 0; i < 10; i++)
cout << x[i] << " ";
return 0;
}
válasza: válasza: válasza: válasza:Stack overflow ... végtelen rekurzió!
Vagy a feltételek hibásak, és/vagy memóriaszeméttel dolgozol, mert a MAXDIM-et csak a tömb létrehozásakor használod és csak 10-ig töltötted fel a tömböt.
Ne használj globális változókat, ez így olvashatatlan! Tessék rendesen paraméterezni!
válasza:Először nézzük meg a Quicksort algoritmust:
Látható, hogy a Wikipédián megemlített pszeudókód egy kicsit eltér, de alapjában véve "majdnem jó"...
A "quicksort" eljárás jó, viszont a "feloszt" már mutat némi érdekességet. Amit te "strazsa"-nak nevezel, az az eredeti algoritmusban "pivot"-ra van keresztelve és annak kezdőértéke máris eltérést mutat.
(nem "strazsa[bal]", hanem strazsa[jobb], hiszen a "lo" balnak, a "hi" jobbnak felel meg, így az eredeti szerint A[hi])
...próbáld meg a 3 while helyett 1 for-al megoldani, ahogy a Wikipédia írja!
válasza:Hopp, most látom csak, hogy te nem is a Lomuto-féle felosztást akartad csinálni, hanem a Hoare-félét...
(ha lentebb gördült a Wikipédiás oldalon, egymás alatt van a kettő...)
Ha összehasonlítod a te implementációddal, máris kiderül a hiba oka!
válasza:További 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!