Algorytm "dziel i zwyciężaj" oraz "SelectionSort"

[kamil142]

Witam.
Czy ktoś mógłby mi obajśnić następujące zadania:

Zad. 1

Zaproponuj algorytm typu „dziel i zwyciężaj” do znalezienia elementu największego w
danym ciągu n elementowym zapisanym w tablicy T.
● Opisz słowami ideę algorytmu,
● Zapisz algorytm w pseudokodzie.
● Oszacuj jego koszt.


Zad. 2
W pewnej prezentacji działania algorytmu SelectionSort (sortowanie w porządku rosnącym)
liczby zostały przedstawione jako słupki o wysokości proporcjonalnej do wartości liczby. W
każdym kroku algorytmu porównywane liczby są wyświetlane innym kolorem przez 300 ms,
tak by sposób sortowania był wyraźnie widoczny dla obserwatora.
● Ile co najmniej czasu zajmie oglądanie tej animacji, jeśli ciąg danych zawiera 100
losowo wybranych liczb.
● Ile czasu zajmie oglądanie animacji, jeśli wiemy, że dany 100 elementowy ciąg liczb
jest uporządkowany rosnąco.

Najlepiej, jakby ktoś rozwiązał podane zadania z objaśnieniem, bo podobnych zadań mam około 15 i chciałbym na podstawie rozwiązania tych robić kolejne
Z góry dziękuję za wszelkie odpowiedzi

[matshadow]

co do 2)
Selection Sort jest specyficznym algorytmem, który wykonuje stałą liczbę operacji w zależności od ilości danych do posortowania, niezależną od sposobu ułożenia (np jak w insertion sorcie).
Ilość porównań wynosi \(\displaystyle{ \frac{(n-1)(n)}{2}}\)
gdzie u nas \(\displaystyle{ n=100}\)
Zatem odp do a i b wynosi \(\displaystyle{ \frac{(n-1)(n)}{2}}\) pomnożone przez 300 ms (zakładam, że elementy zamieniane nie są porównywane, czyli program nie zatrzymuje się na 300 ms przed zamianą elementów)