Próbuję napisać program w c++ sortujący listy (z użyciem szablonu <vector>) metodą quicksort, ale nie zwykłym(gdyż nie jest stabilny), lecz wersją z trójpodziałem(tzw. ternary-split quicksort) i niestety to chyba ponad moje siły... Czy ktoś byłby łaskaw mi pomóc? Szukałam, ale większość algorytmów to dosyć skomplikowane wersje i (wstyd przyznać) niewiele z nich rozumiem, a do tego zazwyczaj dotyczą tablic... Zadanie mam do szkoły i przydałoby się w miarę szybko je wykonać, ale przy okazji chętnie bym coś zrozumiała;) (moja nauczycielka ma nawet problem z uruchomieniem komputera, więc niewiele zyskuję z zajęć...). Z góry dziękuję!
Tablica niczym w dostępie do danych się nie różni od tablicy oprócz tego, że masz jeszcze iteratory.
To w takim razie coś takiego przejdzie:
void quicksort (vector<int> a[],int l,int r){
int i=l-1,j=r,p=l-1,q=r,k;
vector<int> v = a[r];
if(r<=l) return;
for(;;){
while(a[++i]<v);
while(v<a[--j]) if(j==l) break;
if(i>=j) break;
swap(a[i],a[j]);
if(a[i]==v){
p++;
swap(a[p],a[i]);
}
if(v==a[j]){
q--;
swap(a[j],a[q]);
}
}
swap(a[i],a[r]);
j=i-1;
i=i+1;
for(k=l;k<p;k++,j--) swap(a[k],a[j]);
for(k=r-1;k>q;k--,i++) swap(a[i],a[k]);
quicksort(a,l,j);
quicksort(a,i,r);
}
?
Bo póki co po wywołaniu:
quicksort(&Lista,0,d);
Program się kompiluje, ale po uruchomieniu się przerywa i zamyka...
Co to ma być vector<int> a[]? Sortujesz tablicę wektorów? Jeśli nie to czemu nie używasz referencji?
No tak, pomyłka przy pisaniu... Miało być tak:
void quicksort(vector<int> & a, int l, int r)
{
if (l >= r) return;
int i=l-1,j=r,p=l-1,q=r;
while(true){
while(a[++i] <a[r]) ;
while(a[r]<a[--j]) if(j= =l) break;
if(i>=j) break;
swap(a[i],a[j]);
if(a[i]==a[r]) swap(a[++p],a[i]);
if(a[j]==a[r]) swap(a[--q],a[j]);
}
swap(a[i],a[r]);
j=i-1;
i=i+1;
for(int k=l;k<=p;k++) swap(a[k],a[j++]);
for(int k=r-l;k>=q;k--) swap(a[k],a[i++]);
quicksort(a,l,j);
quicksort(a,i,r);
}
ale tak czy siak niezbyt to działa...