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
[Algorytmy] Sortowanie tablicy
-
- Użytkownik
- Posty: 4
- Rejestracja: 22 lip 2010, o 03:09
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
[Algorytmy] Sortowanie tablicy
Ostatnio zmieniony 18 lut 2013, o 10:39 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania. Całe wyrażenia matematyczne umieszczaj w tagach
-
- Użytkownik
- Posty: 106
- Rejestracja: 17 gru 2012, o 23:56
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 7 razy
- Pomógł: 31 razy
[Algorytmy] Sortowanie tablicy
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++
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++
-
- Użytkownik
- Posty: 145
- Rejestracja: 16 lis 2007, o 09:06
- Płeć: Mężczyzna
- Lokalizacja: Gniezno
- Podziękował: 2 razy
- Pomógł: 27 razy
[Algorytmy] Sortowanie tablicy
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..
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..
-
- Użytkownik
- Posty: 55
- Rejestracja: 4 maja 2011, o 13:37
- Płeć: Mężczyzna
- Podziękował: 2 razy
- Pomógł: 14 razy
[Algorytmy] Sortowanie tablicy
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.
-
- Użytkownik
- Posty: 4
- Rejestracja: 22 lip 2010, o 03:09
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 3 razy
[Algorytmy] Sortowanie tablicy
Ha, i właśnie czegoś takiego jak algorytm selekcji szukałem Wielkie dzięki.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Sortowanie tablicy
Co rozumiesz przez "stabilnie" w kontekście tego zadania?arcan pisze:Rekurencyjnie, jeśli stabilne to mergesort,
Co ma oznaczać taka dziwna równość z \(\displaystyle{ O}\) po lewej stronie?arcan pisze:Złośoność \(\displaystyle{ O(n)=n \log n}\)