Quick sort (szybkie wyszukiwanie)

pytanie zadane 24 stycznia 2018 w C i C++ przez Elijah Romashchenko Nowicjusz (220 p.)
edycja 24 stycznia 2018 przez Elijah Romashchenko

Dzień dobry, dla Szybkiego wyszukiwania potrzebna parzysta ilość liczb? I jak w tedy kiedy jest nie parzysta ilość, dzielić na pół taką tablice?(jeżeli można z jakimś kodem przykładowym lub pseudo-kodem) Dziękuję z góry!

komentarz 24 stycznia 2018 przez 10kw10 Pasjonat (22,880 p.)

Raczej chodzilo ci o quick sort

komentarz 24 stycznia 2018 przez Elijah Romashchenko Nowicjusz (220 p.)

Dokładnie. Poprostu chciłem wykorzystać quick sort jako wyszukiwanie małych liczb i duzych liczb dla podanej tabeli (n) i pużniej już samym sort-em wyszukać i poruwnywać max pomiędzy małych - min pomiędzy dużych.

komentarz 24 stycznia 2018 przez 10kw10 Pasjonat (22,880 p.)

Sort = sortowac, skoro chcesz znalezc min i max z podanej tabeli to raczej nie potrzebny ci algorytm sortowania.

komentarz 24 stycznia 2018 przez Elijah Romashchenko Nowicjusz (220 p.)

Dobrze chyba trzeba cały problem wytłumaczyć. Mam tablicę n-elementową, muszę znaleźć punk podziału tej tablicy, i żeby min wartość tej podzielonej tabeli (punktem podziału) niech będzie po prawej stronie, równało się max wartości prawej pod-tablice. Czyli np. {1343 | 5864}. Punk podziału w tej tabeli jest 3(z indeksem k=3, liczymy od 0), Max lewej pod-tablicy = min prawej.

A co jeżeli będzie nie parzysta ilość liczb.???

1 odpowiedź

odpowiedź 24 stycznia 2018 przez k222 Nałogowiec (30,150 p.)

Wyznaczając punkt podziału masz coś typu:


void QuickSort( int tab[], int left, int right )
{
    int i = left;
    int j = right;
    int x = tab[( left + right ) / 2 ];
...
}

skoro left i right są liczbami typu int to całe wyrażenie (left + right ) / 2 zwróci int - co w przypadku dzielenia wiąże się po prostu z ucięciem tego co jest po przecinku - np. (1+8) / 2 = 4 , dlatego zawsze otrzymamy liczbę całkowitą i nie ma żadnego problemu z parzystością / nieparzystością liczby sortowanych zmiennych

komentarz 24 stycznia 2018 przez Elijah Romashchenko Nowicjusz (220 p.)

Aha, czyli można powiedzieć że komputer wprawie automatycznie dzieli tą tablicę?

komentarz 24 stycznia 2018 przez k222 Nałogowiec (30,150 p.)

Nie zrozumiałem twojego zdania, ale tu masz prosty programik który ilustruje jak to działa - możesz sobie powpisywać liczby dodatnie ujemne, ułamki i zobaczysz co ci wyjdzie:

#include <iostream>

using namespace std;

int main()
{
    double a,b;

    while(cin>>a>>b)
    cout<<a/b<<"     "<<(int)a/(int)b<<endl;


    return 0;
}

(jakby co to (int) jest rzutowaniem na int'a - czyli po prostu utnie to co jest po przecinku - np. (int)123.456 = 123), w pierwszym wyrażeniu masz dwa double więc wynik będzie typu double - z przecinkiem, w drugim masz dwa inty