Sortowanie 2

Termin zajęć: 27/28.03.2012

Do przygotowania

  1. Na czym polega strategia dziel i zwyciężaj
  2. Zaimplementuj funkcję o następującym nagłówku:
    
    
    

    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]
    • 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 funkcję
    
    
    

    Funkcja 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/2012-sort2.txt · ostatnio zmienione: 2019/06/27 15:50 (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