Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Sortowanie "quicksort" / rekurencja.

Ostatnio zmodyfikowano 2017-07-31 14:16
Autor Wiadomość
kamix1000
Temat założony przez niniejszego użytkownika
[C++] Sortowanie "quicksort" / rekurencja.
» 2017-07-29 23:43:45
C/C++
#include <iostream>

using namespace std;

void quicksort( int * tablica, int lewy, int prawy )
{
    cout << "Lewy: " << lewy << endl;
    cout << "Prawy: " << prawy << endl;
   
    int v = tablica[( lewy + prawy ) / 2 ];
    cout << "v: " << v << endl;
    int i, j, x;
    i = lewy;
    j = prawy;
    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--;
            for( int i = 0; i < 7; i++ ) cout << tablica[ i ] << endl;
           
            cout << endl;
        }
    } while( i <= j );
   
    cout << "j po sortowaniu: " << j << endl;
    cout << "Lewy po sortowaniu: " << lewy << endl;
    cout << "i po sortowaniu: " << i << endl;
    cout << "Prawy po sortowaniu: " << prawy << endl << endl << endl;
   
    if( j > lewy ) quicksort( tablica, lewy, j );
   
    if( i < prawy ) quicksort( tablica, i, prawy );
   
}

int main()
{
    int t[ 7 ];
   
    t[ 0 ] = 25;
    t[ 1 ] = 90;
    t[ 2 ] = 102;
    t[ 3 ] = 70;
    t[ 4 ] = 15;
    t[ 5 ] = 250;
    t[ 6 ] = 200;
   
    quicksort( t, 0, 6 );
   
    return 0;
}

Ideę tego sortowania rozumiem, natomiast nie rozumiem jednego etapu:
Po pewnym czasie, mam w programie wypisane:
"j" po sortowaniu: 0, "Lewy" po sortowaniu: 1, "i" po sortowaniu: 2, "Prawy" po sortowaniu: 2".
Następnie są dwa if'y i żaden z nich się nie spełnia (tzn. ani "j" nie jest większe od "lewy", ani "i" nie jest mniejsze od "prawy"). Pomimo tego program nie kończy swego działania, tylko w dalszym ciągu sortuje... Program ustawia sobie do zmiennych następujące dane: "Lewy=3", "Prawy=6" i dalej sortuje... Dlaczego tak się dzieje?
Ponadto gdy zmienię drugiego if na else if, wtedy program kończy swoje działanie w wyżej opisanym momencie i to jest dla mnie zrozumiałe.
Z góry dziękuję za odpowiedź :)
P-163708
pekfos
» 2017-07-31 14:16:04
else if sprawia, że tylko jedno z tych dwóch wywołań rekurencyjnych się wykona. Bez tego w twojej opisanej sytuacji funkcja się kończy, wykonanie wraca wyżej i wchodzi w te drugie wywołanie rekurencyjne.
P-163727
« 1 »
  Strona 1 z 1