[[
✎ pl:dydaktyka:asd:cwiczenia:2011-sort2
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Sortowanie 2 ====== **Termin zajęć:** 22/23.03.2011 **Do przygotowania** - Na czym polega strategia dziel i zwyciężaj - Zaimplementuj funkcję o następującym nagłówku:<code cpp>void merge(int [] A, int p, int q, int r)</code>Metoda powinna wykonywać kolejno następujące operacje: * Dzielić tablicę //A// na dwie podtablice (//Left// i //Right//) zawierające odpowiednio elementy //[p ... q]// oraz //[q+1 ... r]// * Przepisywać dane do tablicy A w taki sposób, aby były one posortowane rosnąco, wybierając z tablic //Left// i //Right// odpowiednie elementy (patrz obrazek poniżej) \\ {{:pl:dydaktyka:asd:cwiczenia:mergesort.gif|Merge}} * Jaki warunek musi być spełniony, aby taka metoda poprawnie sortowała dane? - Zaimplementuj metodę <code cpp>int partition(int [] A, int p, int r)(</code>Metoda powinna wykonywać kolejno następujące operacje * Przypisz zmiennej //x// ostatni element tablicy //A//. * Następnie sortuje względem tego elementu, tak aby elementy mniejsze od niego znalazły się na początku tablicy, a większe od niego na końcu tablicy. Element //x// ma na samym końcu rozdzielać te dwa zbiory (patrz rysunek poniżej - pokazane są na nim kolejne kroki w jakich następuje wstępne sortowanie zbioru danych). Zwrócony zostaje indeks tego elementu. \\ {{:pl:dydaktyka:asd:cwiczenia:partition.jpg|Partition}}
pl/dydaktyka/asd/cwiczenia/2011-sort2.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry