Potrzebuje algorytmu, który scali stablinie, w miejscu, dwie posortowane tablice w złożoności O(nlogn). Ktoś, coś?
0
0
Ale co to znaczy w miejscu w takiej sytuacji? Że w pierwszej tablicy będą elementy np 1...x a w drugiej x...y ?
A nie może być w O(n)? Bo ja bym porównywał głowy, robił SWAP żeby mniejszy był w pierwszej tablicy i przesuwał indeks pierwszej tablicy o 1 (bo aktualna głowa do porównań jest o 1 miejsce do tyłu). Robimy tak aż się pierwsza tablica nie skończy i voila.
0
@Shalom : tak, w miejscu znaczy tutaj dokładnie to. Możemy przyjąć, że mamy jedną tablicę T[0..n], natomiast jej części T[0..k], T[k+1..n] są posortowane.
Poza tym - nie do końca chyba rozumiem. Co robimy z drugą głową? Jeśli przesuwamy tylko pierwszą, to nie ma to szans zadziałać.
0
O rly? Zapewniam ze ma. Bo mniejszy element zawsze przerzucamy do pierwszej tablicy przy SWAP. Nie kombinuj tylko zaklep i sprawdź, to jest 5 linijek...
0
http://ideone.com/8q0Pdu
no chyba, że źle zrozumiałem.
0
Źle masz bracket w ifie. Słabo mi...
0
Okej, przyznaje, choć nie wiem jak to się stało.
http://ideone.com/8q0Pdu
poprawione, nadal jednak algorytm jest błędny.
0
Teraz lepiej. Teraz widzę że chciałem to za bardzo ułatwić. Ten SWAP nie jest ok bo powoduje że porównujemy że sobą liczby z tego samego ciągu. Zamiast tego trzeba taką liczbę zapisać w jednej osobnej zmiennej. Tzn jeśli wrzucamy do pierwszego ciągu liczbę z drugiego to liczba z tego miejsca musi być zapisana na boku i używana do porównań. I oczywiście porównania muszą teraz iść do końca całej tablicy.