Matematyka.pl

Hej,
wiecie może w jaki sposób poprzestawiać elementy tablicy liczb całkowitych o wielkości \(\displaystyle{ 2 \cdot n}\) w taki sposób, by każdy element o indeksie \(\displaystyle{ n + 1}\) i wiekszym był wiekszy lub równy od dowolnego elementu którego indeks należy do przedziału \(\displaystyle{ [1, n]}\).

Domyślam się, że algorytm ze złożonoscią kwadratową mógłby wyglądać tak, że n razy znajdowałbym element najwiekszy. Szukam jednak czegoś mniej kosztownego.

Z góry dzięki za pomoc

Rekurencyjnie, jeśli stabilne to mergesort, a jeśli nie stabilne to quicksort. Po poslku to sortowanie przez scalanie i sortowanie szybkie. Te drugie wydaje się szybsze dla bardziej 'losowych' liczb.
Złośoność \(\displaystyle{ O(n)=n \log n}\)
Otrzymaną tablice 2n dzielisz na dwa i ta druga połówka to rozwiązanie problemu. Jak chcesz to mogę ci napisać mergesort w c++

W sumie fakt pasuje każdy algorytm sortowania z mniejszą złożonością, chociaż w sumie pewnikiem można byłoby je zmodyfikować aby nie sortowały tego co mają w lewej połówce.

Albo podzielić tablice na dwie na początku posortować dwie niezależnie np. hepsortem i wymienić elementy większe z prawej na mniejsze z lewej..

Wystarczy znaleźć \(\displaystyle{ n}\)-ty co do wielkości element tablicy (w \(\displaystyle{ O(n)}\): , a następnie przelecieć przez tablicę i podzielić ją na dwie części względem tego elementu.

Ha, i właśnie czegoś takiego jak algorytm selekcji szukałem Wielkie dzięki.

Tak się podniecacie tym quicksortem chociaż ma on złożoność \(\displaystyle{ O\left( n^2\right)}\)

arcan pisze:Rekurencyjnie, jeśli stabilne to mergesort,

Co rozumiesz przez "stabilnie" w kontekście tego zadania?

arcan pisze:Złośoność \(\displaystyle{ O(n)=n \log n}\)

Co ma oznaczać taka dziwna równość z \(\displaystyle{ O}\) po lewej stronie?