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

Nie rozumiem qsorta.

VPS Starter Arubacloud
0 głosów
149 wizyt
pytanie zadane 8 listopada 2018 w C i C++ przez wihajster Początkujący (460 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 Szeryf (91,420 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ź 585 wizyt
pytanie zadane 21 maja 2019 w C i C++ przez dudduss76 Początkujący (280 p.)
0 głosów
1 odpowiedź 269 wizyt
pytanie zadane 11 grudnia 2020 w C i C++ przez komboboost0 Użytkownik (570 p.)
0 głosów
1 odpowiedź 251 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...