Nie rozumiem qsorta.

Question

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" :(

Comments

https://stackoverflow.com/questions/39665299/understanding-quicksort

Answer 1

Po pierwsze polecam najpier zaznajomić się z tym filmem:

https://www.youtube.com/watch?v=ywWBy6J5gz8

Następnie analizować kod programu.