Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
for i <- 1 to k
C[i] <- 0
for j <- 1 to lenght[A]
C[A[j]] <- C[A[j]] + 1
for i <- 2 to k
C[i] <- C[i] + C[i-1]
for j <- lenght[A] downto 1
B[C[A[j]]] <- A[j]
C[A[j]] <- C[A[j]] - 1
Gdzie oczywiście A - tablica nieuporządkowana, C - tablica zliczająca elementy tablicy A, k - ilość elementów tablicy C ( zakres liczb tablicy A ) i wreszcie B - tablica wyjściowa, uporządkowana...
Mianowicie problem jest taki - zmodyfikować TYLKO ostatnią pętle, aby zliczanie zaczynało się od początku tablicy A (for j <- 1 to lenght[A] ), tak, aby stabilność została zachowana... Za cholere nie wiem, z której strony to ugryźć... ktoś chętny?
[Algorytmy] Counting sort - modyfikacja
: 6 lip 2011, o 04:31
autor: mcbob
Jest dosyć późna pora więc mogłem coś pomylić/przekombinować ale wydaje mi się że ten sposób powinien działać.
To jest kod który należy umieścić w ostatniej pętli.
if(C[A[j]]) > 0
z = 1
if(A[j] != 1) z = abs(C(A[j]-1))+1
for tmp <- z to C(A[j])
B[tmp] <- A[j]
C(A[j])=-C(A[j])
[Algorytmy] Counting sort - modyfikacja
: 6 lip 2011, o 08:47
autor: Singrad
Aaa, rozumiem ideę, ale chyba nie do końca o to chodzi... jakbyśmy mieli np tablicę A(1....n): [2, 1, 3, 3, 4, 8]
to przy poprawnym działaniu element A[3] wypełnia nam 3cią i 4tą komórkę B ( B[3] = A[3], B[3] = A[4] ), i co prawda później A[4] nadpisuje ten poprzedni, ale... czy taka operacja jest, no nie wiem - "dozwolona"? (stabilność )
A kod chyba się czasem wywala, ale to już sprawdzę jak wróce do życia
Dzięki wielkie mcbob.
btw. dla ułatwienia załóżmy, że istnieją tylko liczby całkowite z zakresu [1;10], mogące się powtarzać.
[Algorytmy] Counting sort - modyfikacja
: 6 lip 2011, o 12:20
autor: mcbob
Masz rację. Jednak wtedy już spałem. Będziemy wpisywać do B w odpowiedniej kolejności ale będziemy wpisywać ten sam element z A. To nie o to chodziło. Ale problem ciekawy i jak znajdę dziś chwilę to nad nim pomyślę.
@edit
Chyba mam pomysł jak to poprawić. Wywalić tą zagnieżdżoną pętle for. A zamiast tego wystarczy że pierwszy element wstawimy do B w odpowiednie miejsce, a potem jak w tablicy asocjacyjnej zwykły algorytm rozwiązywania kolizji. Tzn. jak trafimy na następną wartość to robimy petle while po elementach z B aż znajdziemy wolna komórkę. Przemyślę to jeszcze i napiszę kod.
z = 1
if(A[j] != 1) z = C(A[j]-1)+1
while(B[z] > 0) z++
B[z] <- A[j]
Tylko po pierwsze założyłem że tablica B jest wyzerowana na starcie, a liczby do niej wstawiane większe od zera. Po drugie rośnie nam złożoność tego counting sorta.
Jak wiemy wciąż jest poprawnie ale nie stabilnie. Ale szybki look w google i znajdujemy że:
In particular, the modified algorithm still places the elements with value k in position c[k - 1] + 1 through c[k], but in reverse order of their appearance in A[1 . . n].
Tak więc teraz przełazimy przez posortowaną tablicę i wyznaczamy początek i koniec ciągu takich samych wartości dla każdej z nich i odwracamy tablicę na tych pozycjach.
Edit: miała być modyfikacja tylko ostatniej pętli więc wycofuję się z powyższego
[Algorytmy] Counting sort - modyfikacja
: 6 lip 2011, o 14:02
autor: mcbob
Tak ten sposób działa i też o nim na początku pomyślałem. Tylko to przechodzenie na końcu to wg mnie oddzielna pętla nie wiem czy nam wolno przy tych ograniczeniach że modyfikujemy tylko tą jedną pętlę.
@edit
Nie zauważyłem że edytowałeś
[Algorytmy] Counting sort - modyfikacja
: 6 lip 2011, o 14:42
autor: Afish
Singrad pisze:zmodyfikować TYLKO ostatnią pętle, aby zliczanie zaczynało się od początku tablicy A (for j <- 1 to lenght[A] ), tak, aby stabilność została zachowana...
Przenumerować, czyli odwoływać się do A[length[A] - j] zamiast do A[j]
[Algorytmy] Counting sort - modyfikacja
: 6 lip 2011, o 19:36
autor: Singrad
Afish, wtedy na dobrą sprawę mielibyśmy to samo, kwestia taka, żeby rzeczywiście zaczynał od A[1], a nie od A[lenght[A]] jak domyślnie. Jak sprawdzałem to rozwiązanie mcbob'a, rzeczywiście niezłe, swoją drogą chylę czoła, ja bym na takie coś nie wpadł.
[Algorytmy] Counting sort - modyfikacja
: 7 lip 2011, o 16:05
autor: Afish
Da się to zrobić bez podbicia złożoności. Zamiast wstawiać w miejsce wyznaczone przez C[A[j]] wstawiamy pod C[A[j]-1] + 1, a następnie inkrementujemy C[A[j]-1] (w zależności od sposobu indeksowania tablicy numer miejsca, do którego wstawiamy może się różnić o 1). Problem występuje jedynie w przypadku najmniejszego elementu, bo wtedy C[A[j]-1] może nie istnieć, ale wtedy bierzemy C[length(A)] i jeżeli jest równe length(A), to wstawiamy w pierwszą komórkę tablicy i odpowiednio aktualizujemy C[length(A)], a w przeciwnym wypadku wstawiamy tak, jak dla pozostałych elementów.
[Algorytmy] Counting sort - modyfikacja
: 7 lip 2011, o 19:38
autor: Singrad
No jasne, indeks poprzedniego elementu plus jeden to pierwszy indeks liczby którą zamierzam wstawić... logiczne i proste. Hmm... dzięki wielkie, teraz już mogę spać spokojnie
[Algorytmy] Counting sort - modyfikacja
: 7 lip 2011, o 19:41
autor: mcbob
Racja. Nie myślałem już nad tym zadaniem wczoraj, ale jak widać prosta modyfikacja mojego rozwiązania rzeczywiście przywraca liniową złożoność.