• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Nie rozumiem qsorta.

0 głosów
85 wizyt
pytanie zadane 8 listopada 2018 w C i C++ przez wihajster Początkujący (410 p.)

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

1 odpowiedź

+2 głosów
odpowiedź 8 listopada 2018 przez profesorek96 Nałogowiec (41,970 p.)
Po pierwsze polecam najpier zaznajomić się z tym filmem:

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

Następnie analizować kod programu.

Podobne pytania

0 głosów
1 odpowiedź 79 wizyt
pytanie zadane 4 listopada 2018 w C i C++ przez Aleksander Początkujący (280 p.)
0 głosów
1 odpowiedź 68 wizyt
pytanie zadane 24 października 2018 w C i C++ przez KamQiX Obywatel (1,860 p.)
0 głosów
2 odpowiedzi 82 wizyt
pytanie zadane 10 marca 2018 w C i C++ przez k3ybo4rd Obywatel (1,180 p.)
Porady nie od parady
Odznacz odpowiedź zieloną fajką, jeśli uważasz, że jest ona najlepsza ze wszystkich i umożliwiła ci rozwiązanie problemu.Najlepsza odpowiedź

60,207 zapytań

105,878 odpowiedzi

219,907 komentarzy

32,422 pasjonatów

Przeglądających: 223
Pasjonatów: 9 Gości: 214

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...