• 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
88 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 Nałogowiec (48,860 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ź 51 wizyt
pytanie zadane 21 maja w C i C++ przez dudduss76 Początkujący (260 p.)
0 głosów
1 odpowiedź 83 wizyt
pytanie zadane 4 listopada 2018 w C i C++ przez Aleksander Początkujący (360 p.)
0 głosów
1 odpowiedź 70 wizyt
pytanie zadane 24 października 2018 w C i C++ przez KamQiX Obywatel (1,860 p.)
Porady nie od parady
Możesz ukryć, zamknąć lub zmodyfikować swoje pytanie, za pomocą przycisków znajdujących się pod nim. Nie krępuj się poprawić pochopnie opublikowanego pytania czy zamknąć go po uzyskaniu satysfakcjonującej odpowiedzi. Umożliwi to zachowanie porządku na forum.Przyciski pytania

64,021 zapytań

110,395 odpowiedzi

231,160 komentarzy

47,800 pasjonatów

Przeglądających: 262
Pasjonatów: 6 Gości: 256

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.

...