Sortowanie szybkie

Napisałem algorytm sortowania szybkiego i wszystko gra ale nie rozumiem jednego, problem podam na przykładzie.

void quicksort(int *tablica, int lewy, int prawy)
{
int v=tablica[(lewy+prawy)/2];
int i,j,x;
i=lewy;
j=prawy;
do
{
while(tablica[i]<v) i++;
while(tablica[j]>v) j--; //tu się coś zbugowało, cały czas mam błąd(nie chce sie normalnie text zapisać) nie zwracajcie uwagi

    if(i<=j)          //ta linia ma za zadanie zmienić liczbę i (lewa strona) z j(prawa strona ciągu) po lewej są mniejsze, po prawej większe to dlaczego jest i<=j ?
    {                  //logicznie myśląc warunek powinien być odwrotny wtedy zmienialibyśmy liczbę z lewej strony która by była większa od liczby z prawej strony
        x=tablica[i];
        tablica[i]=tablica[j];
        tablica[j]=x;
        i++;
        j--;
    }
}while(i<=j);

if(j>lewy) quicksort(tablica,lewy, j);
if(i<prawy) quicksort(tablica, i, prawy);

}

SarveRR napisał(a):

... ta linia ma za zadanie zmienić liczbę ...
if baaaardzo rzadko coś zmienia, przeważnie (w tym przypadku też) tylko sprawdza jakaś zamiana dopiero wewnątrz.

SarveRR napisał(a):

... logicznie myśląc warunek powinien być odwrotny ...
czy widzisz pewną zbieżność: if(i<=j) a }while(i<=j); Masz racje, warunek trzeba zmienić na odwrotny, o tak: if(i>j) break; przy okazji pętle należy zmienić na while(true).

SarveRR napisał(a):

Napisałem algorytm sortowania szybkiego ...

• z pytań wynika że to jest kłamstwem.

Dlaczego nikt nie odpowiada w moim wątku?

Ok trochę przemieniłeś kod i jest on dla mnie teraz w 100% jasny, ale nie w tym problem chciałbym się dowiedzieć dlaczego sortowanie działa gdy posiada if(i<=j). Jest to dziwne, przed napisaniem programu zobaczyłem schemat algorytmu i troche się zdziwiłem widzac ten warunek ale użyłem go żeby sprawdzić czy działa i o dziwo działa. Więc chciałbym się dowiedzieć dlaczego algorytm współpracuje z takim warunkiem jak dla mnie jest to nielogiczne.

Pomyliłeś algorytm z pseudokodem.
Zasada jest prosta, większe na prawo, mniejsze na lewo tak aby mieliśmy dwie części (najlepiej połówki) w których każdy po lewej jest mniejszy od każdego po prawej.
Po czym możemy każdą częścią (może połówką) zając się osobno.

W każdym razie chciałbym się dowiedzieć czym ten kod

do
{
while(tablica[i]<v) i++;
while(tablica[j]>v) j--;
if(i>j) break;
{
x=tablica[i];
tablica[i]=tablica[j];
tablica[j]=x;
i++;
j--;
}
}while(true);

różni się od tego

do
{
while(tablica[i]<v) i++;
while(tablica[j]>v) j--;
if(i<=j)
{
x=tablica[i];
tablica[i]=tablica[j];
tablica[j]=x;
i++;
j--;
}
}while(i<=j);

obydwa działają tak samo a warunki są różne, nie do końca rozumiem logikę tego drugiego sposobu.

1. Wklejaj kod w znaczniki <``code=cpp> Ty kod <``/code>
2. Zapoznaj się z pojęciem formatowania kodu: http://4programmers.net/Forum/998482
3. Zapoznaj się z inkrementacją: http://4programmers.net/Forum/1101404
4. Nazywaj zmienne sensownie, to w większości przypadków zrobi kod zrozumiałym nawet dla ciebie samego
5. Tak powinna wyglądać ta pętla:

while(true)
  {
   while(tablica[lf]<v) ++lf;
   while(tablica[rt]>v) --rt;
   if(lf>rt) break;
   swap(tablica[lf++],tablica[rt--]);
  }