[Algorytmy] Counting sort - modyfikacja

Singrad
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 2 lut 2011, o 18:39
Płeć: Mężczyzna
Lokalizacja: 170

[Algorytmy] Counting sort - modyfikacja

Post autor: Singrad » 6 lip 2011, o 02:46

Z jednej strony ciekawostka, z drugiej - utrapienie ostatnich dni.

Counting-Sort(A, C, k)

Kod: Zaznacz cały

 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?
Ostatnio zmieniony 6 lip 2011, o 14:47 przez Afish, łącznie zmieniany 3 razy.
Powód: Poprawka nazwy tematu

Awatar użytkownika
mcbob
Użytkownik
Użytkownik
Posty: 479
Rejestracja: 15 gru 2008, o 19:02
Płeć: Mężczyzna
Lokalizacja: Poland
Pomógł: 69 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: mcbob » 6 lip 2011, o 04:31

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.

Kod: Zaznacz cały

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])

Singrad
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 2 lut 2011, o 18:39
Płeć: Mężczyzna
Lokalizacja: 170

[Algorytmy] Counting sort - modyfikacja

Post autor: Singrad » 6 lip 2011, o 08:47

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ć.

Awatar użytkownika
mcbob
Użytkownik
Użytkownik
Posty: 479
Rejestracja: 15 gru 2008, o 19:02
Płeć: Mężczyzna
Lokalizacja: Poland
Pomógł: 69 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: mcbob » 6 lip 2011, o 12:20

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.

@edit

Kod: Zaznacz cały

    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.

Awatar użytkownika
argv
Użytkownik
Użytkownik
Posty: 569
Rejestracja: 27 maja 2009, o 01:27
Płeć: Mężczyzna
Podziękował: 51 razy
Pomógł: 66 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: argv » 6 lip 2011, o 13:03

Ukryta treść:    
Edit: miała być modyfikacja tylko ostatniej pętli więc wycofuję się z powyższego

Awatar użytkownika
mcbob
Użytkownik
Użytkownik
Posty: 479
Rejestracja: 15 gru 2008, o 19:02
Płeć: Mężczyzna
Lokalizacja: Poland
Pomógł: 69 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: mcbob » 6 lip 2011, o 14:02

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ś

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: Afish » 6 lip 2011, o 14:42

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]

Singrad
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 2 lut 2011, o 18:39
Płeć: Mężczyzna
Lokalizacja: 170

[Algorytmy] Counting sort - modyfikacja

Post autor: Singrad » 6 lip 2011, o 19:36

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ł.

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: Afish » 7 lip 2011, o 16:05

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.

Singrad
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 2 lut 2011, o 18:39
Płeć: Mężczyzna
Lokalizacja: 170

[Algorytmy] Counting sort - modyfikacja

Post autor: Singrad » 7 lip 2011, o 19:38

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

Awatar użytkownika
mcbob
Użytkownik
Użytkownik
Posty: 479
Rejestracja: 15 gru 2008, o 19:02
Płeć: Mężczyzna
Lokalizacja: Poland
Pomógł: 69 razy

[Algorytmy] Counting sort - modyfikacja

Post autor: mcbob » 7 lip 2011, o 19:41

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ść.

ODPOWIEDZ