Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2012-sort2 [2012/02/27 19:40] 127.0.0.1 edycja zewnętrzna |
pl:dydaktyka:asd:cwiczenia:2012-sort2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| ====== Sortowanie 2 ====== | ====== Sortowanie 2 ====== | ||
| - | **Termin zajęć:** 22/23.03.2011 | + | **Termin zajęć:** 27/28.03.2012 |
| **Do przygotowania** | **Do przygotowania** | ||
| - Na czym polega strategia dziel i zwyciężaj | - 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: | + | - Zaimplementuj funkcję o następującym nagłówku:<code cpp>void merge(int [] A, int p, int q, int r)</code>Funkcja 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]// | * 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}} | * 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? | * 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 | + | - Zaimplementuj funkcję <code cpp>int partition(int [] A, int p, int r)(</code>Funkcja powinna wykonywać kolejno następujące operacje |
| * Przypisz zmiennej //x// ostatni element tablicy //A//. | * 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}} | * 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}} | ||
| + | |||
