[C++] Sortowanie "quicksort" / rekurencja.
Ostatnio zmodyfikowano 2017-07-31 14:16
kamix1000 Temat założony przez niniejszego użytkownika |
[C++] Sortowanie "quicksort" / rekurencja. » 2017-07-29 23:43:45 #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ź :) |
|
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. |
|
« 1 » |