[C++] Sortowanie, Klucz - Teoria
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

[C++] Sortowanie, Klucz - Teoria

AutorWiadomość
Temat założony przez niniejszego użytkownika
[C++] Sortowanie, Klucz - Teoria
» 2018-05-09 11:21:09
Witam, piszę w sprawie "niezrozumienia" definicji podanych zagadnień a mianowicie: "klucz skrajnie prawy, klucz środkowy, klucz losowy". Wytłumaczyłby ktoś mi jak mam to rozumieć?
Potrzebuję to na sprawozdanie

2. Zaimplementuj algorytm Quicksort w wersji iteracyjnej (z własną implementacją stosu).
Następnie przeprowadź pomiary czasu sortowania tablicy A-kształtnej dla różnego sposoby wyboru klucza (pivotu): "skrajnie prawego", "środkowego co do położenia", "losowo wybranego".
Utwórz wykres porównujący efektywność działania algorytmu iteracyjnego w zależności od wyboru różnego klucza (przynajmniej 15 punktów pomiarowych).

Algorytm napisałem, problemem pozostaje ustawienie klucza
P-170970
Temat założony przez niniejszego użytkownika
» 2018-05-09 11:58:39
Działanie algorytmu QuickSort

Algorytm wykorzystuje technikę "dziel i zwyciężaj". Według ustalonego schematu wybierany jest jeden element w sortowanej tablicy, który będziemy nazywać pivot. Pivot może być elementem środkowym, pierwszym, ostatnim, losowym lub wybranym według jakiegoś innego schematu dostosowanego do zbioru danych. Następnie ustawiamy elementy nie większe na lewo tej wartości, natomiast nie mniejsze na prawo. W ten sposób powstaną nam dwie części tablicy (niekoniecznie równe), gdzie w pierwszej części znajdują się elementy nie większe od drugiej. Następnie każdą z tych podtablic sortujemy osobno według tego samego schematu.

//Jednak książki to nie wszystko.
ZOSTAWIAM TEMAT DLA POTRZEBUJĄCYCH.
P-170971
« 1 »
 Strona 1 z 1