Scalanie w miejscu

Michal Poziemski - 23 Kwi 2001, 07:42

Witam

Czy ktos moglby opisac mi algorytm scalania w miejscu dwoch posortowanych
tablic, uzywajac jedynie stalej liczby komorek pamieci w czasie liniowym.

Ewentualnie jakis link do strony z opisanym algorytmem.

Z gory dziekuje.

Tomasz Jaskowiec - 23 Kwi 2001, 08:42

Czy ktos moglby opisac mi algorytm scalania w miejscu dwoch posortowanych
tablic, uzywajac jedynie stalej liczby komorek pamieci w czasie liniowym.

0) tablica A ma A0 rekordow, tablica B ma B0 rekordow
1) alokujesz nowa tablice C o liczbie rekordow A0+B0
2) algorytm:

i_a:=0;
i_b:=0;
for (i=0;i<(A0+B0);i++) {
if (i_a<A0) {

if (i_b<B0) {
if (A[i_a]<=B[i_b]) {
C[i]=A[i_a];
i_a++;
} else
{
C[i]=B[i_b];
i_b++;
}

} else
{
C[i]=A[i_a];
i_a++;
}

} else
{
if (i_b<B0) {
C[i]=B[i_b];
i_b++;
}
}
}

Michal Poziemski - 23 Kwi 2001, 08:48

| Czy ktos moglby opisac mi algorytm scalania w miejscu dwoch posortowanych
| tablic, uzywajac jedynie stalej liczby komorek pamieci w czasie liniowym.

0) tablica A ma A0 rekordow, tablica B ma B0 rekordow
1) alokujesz nowa tablice C o liczbie rekordow A0+B0

Blad! Nie moge zaalokowac tablicy C. Moge uzyc jedynie stalej ilosci pamieci
dla dowolnie duzych tablic wejsciowych.

Michal Poziemski - 23 Kwi 2001, 08:51

Blad! Nie moge zaalokowac tablicy C. Moge uzyc jedynie stalej ilosci
pamieci
dla dowolnie duzych tablic wejsciowych.

Inaczej mowiac:

merge(int A[1..k], int B[1..n])
{
int c[50]; // cos takiego moge zrobic
int *c = malloc((k+n) * sizeof(int)); // czegos takiego mi nie wolno

...

}

--
Michal Poziemski

Tomasz Jaskowiec - 23 Kwi 2001, 08:54

merge(int A[1..k], int B[1..n])
{
int c[50]; // cos takiego moge zrobic
int *c = malloc((k+n) * sizeof(int)); // czegos takiego mi nie wolno

...
}

Alez to jest Mission Impossible ;-))))

gdzie chcialbys przechowac wynik ?
No chyba ze w tych dwoch tablicach wejsciowych,
tylko musisz sobie wybrac ktora bedzie pierwsza, a ktora druga.

Michal Poziemski - 23 Kwi 2001, 09:01

Alez to jest Mission Impossible ;-))))
gdzie chcialbys przechowac wynik ?
No chyba ze w tych dwoch tablicach wejsciowych,
tylko musisz sobie wybrac ktora bedzie pierwsza, a ktora druga.

No to inaczej. Mam tablice T[1..n]. Podtablice T[1..k] (k < n) i T[k+1..n]
sa posortowane niezaleznie. Teraz musze to scalic.

merge(int *T, int k, int n)
{
int c[50]; // ok

int *c = malloc( n * sizeof(int)); // nie moge tak :(

...

}

--
Michal Poziemski

Tomasz Jaskowiec - 23 Kwi 2001, 09:06

// analogicznie

z tym ze A-T[1]
B-T[k+1]
C-T[1]
A0=k
B0=n-k

// pobaw sie wskaznikami ;-)
// ... sortujesz w miejscu

i_a:=0;
i_b:=0;
for (i=0;i<(A0+B0);i++) {
if (i_a<A0) {

if (i_b<B0) {
if (A[i_a]<=B[i_b]) {
C[i]=A[i_a];
i_a++;
} else
{
C[i]=B[i_b];
i_b++;
}

} else
{
C[i]=A[i_a];
i_a++;
}

} else
{
if (i_b<B0) {
C[i]=B[i_b];
i_b++;
}
}
}

Robert Sermak - 23 Kwi 2001, 10:54

Bardzo fajny niedzialajacy program :)
Proponuje scalic np. taka tablice: T[2, 2, 2, 2, 1, 1, 1, 1] dla k=4.
To zadanie jest troche bardziej skomplikowane i przyznam sie ze nie wiem
jak to zrobic w czasie liniowym na tej samej tablicy.
pozdrawiam Robert

// analogicznie

z tym ze A-T[1]
B-T[k+1]
C-T[1]
A0=k
B0=n-k

// pobaw sie wskaznikami ;-)
// ... sortujesz w miejscu

i_a:=0;
i_b:=0;
for (i=0;i<(A0+B0);i++) {
if (i_a<A0) {

if (i_b<B0) {
if (A[i_a]<=B[i_b]) {
C[i]=A[i_a];
i_a++;
} else
{
C[i]=B[i_b];
i_b++;
}

} else
{
C[i]=A[i_a];
i_a++;
}

} else
{
if (i_b<B0) {
C[i]=B[i_b];
i_b++;
}
}
}

Mariusz Kruk - 23 Kwi 2001, 12:06

Michal Poziemski pozwoliła sobie popełnić co następuje:

Czy ktos moglby opisac mi algorytm scalania w miejscu dwoch posortowanych
tablic, uzywajac jedynie stalej liczby komorek pamieci w czasie liniowym.

Hmm... IIRC była tu kiedyś dyskusja na ten temat. I IIRC nie da się.

Pozdrawiam

Piotr Wyderski - 23 Kwi 2001, 12:18

Hmm... IIRC była tu kiedyś dyskusja na ten temat. I IIRC nie da się.

Da sie, bo to jest zadanie z Algorytmow i Struktur Danych
na drugim roku informatyki na naszym uniwerku :-) Tylko
z tego co pamietam, to algorytm byl dosc wesoly ;-)

Pozdrawiam
Piotr Wyderski

Mariusz Kruk - 23 Kwi 2001, 12:32

Piotr Wyderski pozwoliła sobie popełnić co następuje:

| Hmm... IIRC była tu kiedyś dyskusja na ten temat. I IIRC nie da się.
Da sie, bo to jest zadanie z Algorytmow i Struktur Danych
na drugim roku informatyki na naszym uniwerku :-)

Zadanie może być błędne.

Tylko z tego co pamietam, to algorytm byl dosc wesoly ;-)

I nikt nie twierdzi, że prawidłowy ;-

Pozdrawiam
PS: Oczywiście mogę się mylić.

Piotr Wyderski - 23 Kwi 2001, 12:39

Zadanie może być błędne.

Nie jest bledne.

| Tylko z tego co pamietam, to algorytm byl dosc wesoly ;-)

I nikt nie twierdzi, że prawidłowy ;-

A widziales ten algorytm ? Knuthowi wierze...
bo to chyba u niego jest rozwiazanie, BTW.

Pozdrawiam
PS: Oczywiście mogę się mylić.

Mozesz :-)

Pozdrawiam
Piotr Wyderski

Tomasz Jaskowiec - 24 Kwi 2001, 02:42

Bardzo fajny niedzialajacy program :)
Proponuje scalic np. taka tablice: T[2, 2, 2, 2, 1, 1, 1, 1] dla k=4.
To zadanie jest troche bardziej skomplikowane i przyznam sie ze nie wiem
jak to zrobic w czasie liniowym na tej samej tablicy.

zgadza sie, "zadepcze" swoje dane.

Ale dzisiaj podam rozwiazanie, juz prawie wiem jak to zrobic ;-)

Robert Sermak - 24 Kwi 2001, 05:35

| Bardzo fajny niedzialajacy program :)
| Proponuje scalic np. taka tablice: T[2, 2, 2, 2, 1, 1, 1, 1] dla k=4.
| To zadanie jest troche bardziej skomplikowane i przyznam sie ze nie wiem
| jak to zrobic w czasie liniowym na tej samej tablicy.

zgadza sie, "zadepcze" swoje dane.

Ale dzisiaj podam rozwiazanie, juz prawie wiem jak to zrobic ;-)

trzymam kciuki
pzdrv Robert

Tomasz Jaskowiec - 24 Kwi 2001, 07:27

OK juz wymyslilem ;-)

Dane wejsciowe
Tablica T[1..n]
gdzie:
podtablica A[1..k]-T[1..k]
podtablica B[1..(n-k)]-T[k+1..n]
dlugosc(T)=T0=n
dlugosc(A)=A0=k
dlugosc(B)=B0=n-k

// Sortujemy A+B-T

// piszemy sobie 2 funkcje, ktore ulatwia nam manipulowanie tymi tabelami
// sorry... bedzie w pascalu ;-)

// przyjmuje ze tabele sa indeksowane od 1 (nie od 0) !!!

procedure sortuj(var A,B:array of integer);

var
i,i_lo,i_hi:integer;
buf:integer;
pom:integer;

procedure set(pozycja,wartosc);
begin
if pozycja<=high(A) then // w tym wypadku high() zwraca
dlugosc tablicy
A[pozycja]:=wartosc else
B[pozycja-high(A)]:=wartosc;
end;

function get(pozycja):integer;
begin
if pozycja<=high(A) then
result:=A[pozycja] else
result:=B[pozycja-high(A)];
end;

begin // glowna petla sortujaca

// inicjujemy wskazniki na pozycje stosu
i_lo:=2; poczatek tablicy A po wyjeciu pierwszego elementu
i_hi:=high(A)+1; poczatek tablicy B

// na poczatek "wyjmujemy" pierwszy element, zobaczycie po co w dalszej
czesci ;-)
buf:=get(1);

// iterujemy po wszystkich elementach
tablicy T(1..n)
for i:1 to (high(A)+high(B)) do
begin
// w kazdym obiegu dbamy o to aby "w reku" trzymac maksymalny
// element z 3-ech dostepnych: buf, T[i_lo], T[i_hi]

if (i_lo<=high(A)) then // zabezpieczamy sie aby nie "wejsc" na
tablice B
if buf<get(i_lo) then
begin
pom:=buf; // zamieniamy miejscami
buf:=get(i_lo);
set(i_lo,pom);
end;

if (i_hi<=(high(A)+high(B))) then // uwaga! nie wolno wyjsc poza
tablice
// GPF od reki ;-)
if buf<get(i_hi) then
begin
pom:=buf; // zamieniamy miejscami
buf:=get(i_hi);
set(i_hi,pom);
end;

// teraz skoro juz wiemy ze elementy T[i_lo],T[i_hi] sa
// mniejsze od buf

// przypadek 1: nie oproznilismy w calosci ktorejs z tabel A lub B
if (i_lo<=high(A)) and (i_hi<=(high(A)+high(B))) then
begin
if (get(i_lo)<=get(i_hi)) then
begin
set(i,get(i_lo)); // zdejmujemy z listy T[i_lo]
inc(i_lo);
end else
begin
set(i,get(i_hi)); // zdejmujemy z listy T[i_hi]
inc(i_hi);
end;
// buf zostaje bez zmian
end else
// przypadek 2: tabela B zostala wyprozniona w calosci
if (i_lo<=high(A)) and (i_hi(high(A)+high(B))) then
begin
set(i,get(i_lo)); // przenosimy T[i_lo]-T[i]
inc(i_lo);
// buf bez zmian, bo jest wiekszy ;-)
end else
// przypadek 3: tabela A zostala wyprozniona w calosci
if (i_lohigh(A)) and (i_hi<=(high(A)+high(B))) then
begin
set(i,get(i_hi));
inc(i_hi);
// buf bez zmian bo jest wiekszy
end else
// przypadek 4: obie tabele zostaly wyproznione, a w
"lapie" mamy element maksymalny
begin
set(i,buf); // wkladamy go na koniec tabeli T[n]
end;

end;

// Voila! I nawet dziala ;-)

Michal Poziemski - 24 Kwi 2001, 10:36

A widziales ten algorytm ? Knuthowi wierze...
bo to chyba u niego jest rozwiazanie, BTW.

Dokladnie o ten algorytm (autorstwa Knutha) mi chodzi...

Michal Poziemski - 24 Kwi 2001, 10:58

OK juz wymyslilem ;-)

Spytam sie tylko bez wnikania w Twoj algorytm: jestes pewnien, ze dziala on
w czasie liniowym?

Robert Sermak - 25 Kwi 2001, 02:40

Sprawdz jeszcze raz ten algorytm. Mam dziwne wrazenie ze znowu
podales
rozwiazenie, ktore nie dziala.
pzdrv Robert

Tomasz Jaskowiec - 25 Kwi 2001, 02:50

Spytam sie tylko bez wnikania w Twoj algorytm: jestes pewnien, ze dziala
on
w czasie liniowym?

Ile petli widzisz w tym programie ? --1 (od 1...n)
Czy wskaznik petli zalezy od tego co
dzieje sie w jej wnetrzu ? --nie

Czas: O(n)

Tomasz Jaskowiec - 25 Kwi 2001, 02:53

Sprawdz jeszcze raz ten algorytm. Mam dziwne wrazenie ze znowu
podales
rozwiazenie, ktore nie dziala.

Kurde to ja jestem "niewierny" Tomasz, wiec nie rozumiem
dlaczego mi wkladasz paluchy w rany ;-))))))))

P.S.
To ze nie potrafisz wymyslic jakiegos algorytmu to
wcale nie znaczy ze on nie istnieje ;-)

Robert Sermak - 25 Kwi 2001, 03:07

| Sprawdz jeszcze raz ten algorytm. Mam dziwne wrazenie ze znowu
| podales
| rozwiazenie, ktore nie dziala.

Kurde to ja jestem "niewierny" Tomasz, wiec nie rozumiem
dlaczego mi wkladasz paluchy w rany ;-))))))))

P.S.
To ze nie potrafisz wymyslic jakiegos algorytmu to
wcale nie znaczy ze on nie istnieje ;-)

Czyli co, jednak nie dziala?

Tomasz Jaskowiec - 25 Kwi 2001, 03:38

Czyli co, jednak nie dziala?

Moj dziala, a algorytmu Knutha nie widzialem 8-(
Jak ktos zna ten drugi to ew. moze porownac,
ale obawiam sie ze bardziej krotkie i zwarte rozwiazanie nie istnieje.
To co wymyslilem wynika z logiki:

a) wyciagamy pierwszy element, aby miec wolne miejsce,
jezeli tego nie zrobimy to musielibysmy przegladac
kazda tablice w gore, aby sie upewnic ze jest nadal posortowana
---- a czas mial byc liniowy ;-)

b) staramy sie nie zaburzyc posortowania tablic, dlatego
dazymy do tego aby trzymac maksymalny element z 3-ech
w "reku"

c) podaj przyklad ktory obali jego dzialanie ;-)

Robert Sermak - 25 Kwi 2001, 04:04

| Czyli co, jednak nie dziala?

Moj dziala, a algorytmu Knutha nie widzialem 8-(
Jak ktos zna ten drugi to ew. moze porownac,
ale obawiam sie ze bardziej krotkie i zwarte rozwiazanie nie istnieje.
To co wymyslilem wynika z logiki:

a) wyciagamy pierwszy element, aby miec wolne miejsce,
jezeli tego nie zrobimy to musielibysmy przegladac
kazda tablice w gore, aby sie upewnic ze jest nadal posortowana
---- a czas mial byc liniowy ;-)

b) staramy sie nie zaburzyc posortowania tablic, dlatego
dazymy do tego aby trzymac maksymalny element z 3-ech
w "reku"

c) podaj przyklad ktory obali jego dzialanie ;-)

Tez nie widzialem Knutha, szkoda , :[

Dobra, zacznijmy.
Nie mam Pascala , bo go nie lubie, ale jakos damy sobie rade:

tablica T[22341111] dla k =4

po pierwszej iteracji T wyglada tak:

[12341111] i_lo=2 i_hi=6 i=1 (jezeli liczymy indeksy tablicy od 1)
zmienna buf=2

druga iteracja:
[11241111] ,i_lo=2 ,i_hi=7, buf =3, i=2 (juz sie zaczyna....)

trzecia iteracja:
[11131111] i_lo=2, i_hi=8, buf=4 ,i=3 (ooo.... gdzies znikla 2)

chyba nie trzeba dalej...

Tomasz Jaskowiec - 25 Kwi 2001, 04:22

[12341111] i_lo=2 i_hi=6 i=1 (jezeli liczymy indeksy tablicy od 1)
zmienna buf=2

jezeli i_hi=6 to tablica A nie jest posortowana

- koniec obalenia twojego wywodu -

Tomasz Jaskowiec - 25 Kwi 2001, 04:39

zwracam honor .... jest blad ;-))))))

Dzieki za ten egzample.... algorymt sie zadlawil az mu uszmai poszlo.
Potem pomysle jak go skorygowac..

Tomasz Jaskowiec - 25 Kwi 2001, 05:28

Dzieki za ten egzample.... algorymt sie zadlawil az mu uszmai poszlo.
Potem pomysle jak go skorygowac..

Juz wiem o co chodzi ;-)

Trzeba dac mozliwosc "przesiedlania" tabel, a dokladniej
zamiast traktowac je liniowo tak jak zrobilem, powinienem je potraktowac
jak bufory okrezne.

Ten twoj przypadek jest swoisty w kazdym calu ;-)
A mianowicie cala podtabela A powinna sie znalezc za tabela B....

Po poludniu podam rozwiaznie poprawione.

Robert Sermak - 25 Kwi 2001, 07:03

To nie jest takie proste. Bufor , o ktorym mowisz, musialby miec zmienna
dlugosc,
a to jest sprzeczne z zadaniem.
Mozna byloby w momecie wstawiania przesunac cala tablice A w prawo o tyle
miejsc
ile jest wolne w tablicy B.
czyli np:
A[1, 1, 3, 4] B[_ , _, , 1, 5] i jak teraz chcemy wstawic 1 z tablicy B
dla i =3 to przesuwamy
A o dwa miejsca w prawo. ( "_" oznacza puste miejsce) czyli:
A[1, 1, _, _] B[3, 4, 1,5] i teraz dopiero wstawiac.
Wlasciwie to teraz powiekszyl sie rozmiar tablicy A o dwa, zatem poprawny
zapis bedzie wygladal:
A[1, 1, _, _, 3, 4] B[1,5]
I teraz sprawa jest juz jasna, wstawianie nie nadpisze niczego.

Jest tylko jedno ale. Nie dalbym gwarancji ze ten algorytm ma liniowa
zlozonosc. Wydaje mi
sie tak, ale nie jestem tego na 100% pewien.

w kazdym badz razie powodzenia
pozdrawiam Robert

| Dzieki za ten egzample.... algorymt sie zadlawil az mu uszmai poszlo.
| Potem pomysle jak go skorygowac..

Juz wiem o co chodzi ;-)

Trzeba dac mozliwosc "przesiedlania" tabel, a dokladniej
zamiast traktowac je liniowo tak jak zrobilem, powinienem je potraktowac
jak bufory okrezne.

Ten twoj przypadek jest swoisty w kazdym calu ;-)
A mianowicie cala podtabela A powinna sie znalezc za tabela B....

Po poludniu podam rozwiaznie poprawione.

Tomasz Jaskowiec - 25 Kwi 2001, 07:11

To nie jest takie proste. Bufor , o ktorym mowisz, musialby miec zmienna
dlugosc,
a to jest sprzeczne z zadaniem.

nie jest sprzeczne!
bufor jest wirtualny: ma wskaznik start,end
i jest zawarty w samej tablicy ;-)
np.:
[112345678]
^ ^
start end wtedy 12345

[112345678]
^ ^
end start wtedy 567811

Mozna byloby w momecie wstawiania przesunac cala tablice A w prawo o tyle
miejsc
ile jest wolne w tablicy B.

tracisz zalozenie o liniowej zlozonosci

czyli np:
A[1, 1, 3, 4] B[_ , _, , 1, 5] i jak teraz chcemy wstawic 1 z tablicy B
dla i =3 to przesuwamy
A o dwa miejsca w prawo. ( "_" oznacza puste miejsce) czyli:
A[1, 1, _, _] B[3, 4, 1,5] i teraz dopiero wstawiac.
Wlasciwie to teraz powiekszyl sie rozmiar tablicy A o dwa, zatem poprawny
zapis bedzie wygladal:
A[1, 1, _, _, 3, 4] B[1,5]
I teraz sprawa jest juz jasna, wstawianie nie nadpisze niczego.

Jest tylko jedno ale. Nie dalbym gwarancji ze ten algorytm ma liniowa
zlozonosc. Wydaje mi
sie tak, ale nie jestem tego na 100% pewien.

no nie jest juz liniowa ;-)

ten pomysl z buforowaniem "robakow" w miejscu jest znacznie lepszy ...

Sc0rpi0 - 25 Kwi 2001, 09:26

| Bardzo fajny niedzialajacy program :)
| Proponuje scalic np. taka tablice: T[2, 2, 2, 2, 1, 1, 1, 1] dla k=4.
| To zadanie jest troche bardziej skomplikowane i przyznam sie ze nie
wiem
| jak to zrobic w czasie liniowym na tej samej tablicy.

| zgadza sie, "zadepcze" swoje dane.

| Ale dzisiaj podam rozwiazanie, juz prawie wiem jak to zrobic ;-)

trzymam kciuki
pzdrv Robert