Witam. Mam za zadanie poprawić błędy w funkcji q_sort, ale mój problem jest w tym, że nie rozumiem nawet na jakiej zasadzie powinna działać ta funkcja, przez co nie potrafię też zlokalizować błędów. W internecie są inne implementacje, a jak oglądam animacje to też mi nie pomagają. Próbowałem rozpisać sobie to krok po kroku i również nic to nie dało. Czy mógłby mi ktoś w zrozumiały sposób wyjaśnić jak powinna działać ta funkcja? :(
# include "q_sort.h"
int divide( double v[], int f, int l ); // zajmiemy się tym za chwilę
void qsort_rec( double v[], int first, int last ) {
// wygodniej jest zapisać tę funkcję rekurencyjną
// posługując się indeksem początku i końca wektora
if( first < last ) {
int m= divide( v, first, last );
qsort_rec( v, first, m-1 );
qsort_rec( v, m+1, last );
}
}
void q_sort( double v[], int n ) { // to jest tylko opakowanie, aby wywołanie
// wyglądało tak samo, jak insort
qsort_rec( v, 0, n-1 );
}
Głównie chodzi mi o funkcję divide.
int divide( double v[], int f, int l ) {
double tmp; // zmienna tymczasowa do zmiany elementów
int s= f; // dzielimy ze względu na pierwszy element
f++; // opuść pierwszy element
while( f < l ) {
while( f < l && v[f] < v[s] ) // przeskocz < v[s]
f++;
while( f < l && v[l] >= v[s] ) // przeskocz >= v[s]
l--;
if( f < l ) { // zamień v[f] i v[l], gdy są różne
tmp= v[f];
v[f]= v[l];
v[l]= tmp;
}
}
// zamieniamy element v[s] z v[f]
// aby v[s] znalazł się pomiędzy
// mniejszymi i nie-większymi od niego
tmp = v[s];
v[s] = v[f];
v[f] = tmp;
return f;
}
Dodatkowo nie pomaga mi powyższy komentarz, " zamieniamy element v[s] z v[f] // aby v[s] znalazł się pomiędzy // mniejszymi i nie-większymi od niego" :(