Sortowanie 2

Termin zajęć: 22/23.03.2011

Do przygotowania

  1. Na czym polega strategia dziel i zwyciężaj
  2. Zaimplementuj funkcję o następującym nagłówku:
    void merge(int [] A, int p, int q, int r)

    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)
      Merge
    • Jaki warunek musi być spełniony, aby taka metoda poprawnie sortowała dane?
  3. Zaimplementuj metodę
    int partition(int [] A, int p, int r)(

    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.
      Partition
pl/dydaktyka/asd/cwiczenia/2011-sort2.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0