Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Witam

Z mojej strony ostatnia zagadka ;]

Zagadka:
Mamy tablice int'ów o rozmiarze n.
O elementach w tablicy wiemy tylko tyle, że w tablicy są zapisane po sobie dwa ciągi rosnących liczb, to znaczy:
fragment od indeksu 1 do j jest posortowany
fragment od indeksu j+1 do n jest posortowany

... gdzie j jest jakimś indeksem z przedziału (1, n).

Celem zagadki jest znalezienie algorytmu, który scali te dwa ciągi, działającego w czasie O(n) i potrzebującego jedynie O(1) dodatkowej pamięci.

Czyli wynikiem działania algorytmu, ma być tablica z już posortowanymi elementami.

--------------------------------

Od razu mówię, że sam rozwiązania nie znalazłem. Kiedyś, po latach, przypomniała mi się ta zagadka i dość szybko wygooglałem odpowiedni algorytm. Znaleziony przeze mnie (w internecie) algorytm okazał się nietrywialny ;]

A o zagadce tej postanowiłem napisać, bo zagadka, z pozoru, wydaje się krótka i prosta, a jak się okazało, wcale taką nie jest :)

Poza tym, w ekstremalnych zastosowaniach, warto mieć świadomość, że takiego scalenia jesteśmy w stanie dokonać *bez* dodatkowej pamięci (tablicy) o tym samym rozmiarze.

Pozdrawiam, Adam Woźniak

PS. Jeśli ktoś ciekaw jest rozwiązania, to za kilka dni dam adresy do opisu algorytmu.Adam Woźniak edytował(a) ten post dnia 20.05.10 o godzinie 22:41

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Nic nie googlałem, słowo :)

void magic_merge(int *tab, int size) {

  int *a, *b;

  

  if (size < 2) // nic do roboty

    return;

  

  a = tab; // pierwszy element tab

  b = tab+size-1; // ostatni element tab

  

  //ustawiamy a na ostatni element posortowanego pierwszego ciagu

  while (a<b && *a<=*(a+1)) a++;

  

  if (a == b) // całość jest już posortowana

    return;



  //póki nie wrócimy z a na początek  

  while (a>=tab) { 

  

    //póki wartości w b są większe od tych w a,

    //to jasne, ze będą na końcu

    while (*a <= *b && a<b) b--;

    

    //póki wartości w a są większe od tych w b

    //to znaczy ze to one są największe w całym ciąg od tab do b

    while (*a >= *b && a>=tab) { 

      SWAP(*a,*b);

      a--; b--;

    }

  }

}

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Karol Nowacki:
Nic nie googlałem, słowo :)

void magic_merge(int *tab, int size) {

  int *a, *b;

  

  if (size < 2) // nic do roboty[/quote]>     return;[quote]  

  a = tab; // pierwszy element tab

  b = tab+size-1; // ostatni element tab

  

  //ustawiamy a na ostatni element posortowanego pierwszego ciagu

  while (a<b && *a<=*(a+1)) a++;[/quote]>   [quote]  if (a == b) // całość jest już posortowana

    return;



  //póki nie wrócimy z a na początek  

  while (a>=tab) { 

  

    //póki wartości w b są większe od tych w a,

    //to jasne, ze będą na końcu

    while (*a <= *b && a<b) b--;[/quote]>     [quote]    //póki wartości w a są większe od tych w b

    //to znaczy ze to one są największe w całym ciąg od tab do b

    while (*a >= *b && a>=tab) { 

      SWAP(*a,*b);

      a--; b--;

    }

  }

}

Twój algorytm nie działa, "słowo" ;]

Tak patrząc na sucho, kod działa dla wszystkich tablic o rozmiarze nie większym niż 2, ale to trochę za mało ;)

Z tego co widzę, to Twój kod dla tablicy:
{5 11 12} {1 2}

... da wynik w rodzaju:
5 1 2 11 12

... czyli niepoprawny, bo tablica ta nie jest posortowana.

Tak jak już wspomniałem, rozwiązanie tej, wydawać się mogło krótkiej zagadki, jest dalece nietrywialny. Ten mój post to nie jest zagadka (bo to byłoby zdecydowanie zbyt trudne), ale ciekawostka algorytmiczna, dla tych co się algorytmiką trochę interesują.

Pozdrawiam, Adam Woźniak

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Wygląda na nietrywialne. Walczyłem sam paręnaście minut, ale się poddałem... ale ciekawe :)

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Adam Michalski:
Wygląda na nietrywialne. Walczyłem sam paręnaście minut, ale się poddałem... ale ciekawe :)

Sam z tym kiedyś walczyłem zdecydowanie więcej niż kilkanaście minut ;] Poległem ;]

To wszystko przez wykładowcę, który kiedyś na wykładzie wspomniał, że taki algorytm istnieje, ale niestety samego algorytmu nie podał ;>

Podkreślę, że ten algorytm ma realne zastosowania: np. jeśli chcemy posortować (sporą) tablicę algorytmem mergesort i jednocześnie nie chcemy alokować dodatkowej tablicy tymczasowej, wtedy dyskutowany tu algorytm miałby zastosowanie.

Tak jak obiecałem, za jakiś czas dam link do opisu (pewnie jednego z wielu) algorytmu, rozwiązującego ten problem, ale dam jeszcze chwilę ewentualnym amatorom łamania sobie głowy na takich zagwozdkach.

Pozdrawiam, Adam Woźniak

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

25 minut :), ale powinno zadziałać, choć nie sprawdzałem. Cały dowcip w pętli z dwoma indeksami, z których tylko jeden jest inkrementowany w danym przebiegu pętli.

void internal_merge(int *arr, int n)

{

  if (n < 2)

    return; // nothing to do :)



// so merge

  int i1; // index for vector 1

  int i2; // index for vector 2

  for (i1 = i2 = 0; (i1 < n) && (i2 < n);)

    if (arr[i1] > arr[i2])

    {

      // item in vector 2 is lower than item in vector 1, so swap these items

      int t = arr[i2];

      arr[i2] = arr[i1];

      arr[i1] = t;



      i1++;

    }

    else

      i2++;



  return;  

}

Oczywiście pętlę można zrealizować na 100 różnych sposobów ;), ale to tak naprawdę nie ma znaczenia. Można też lecieć na wskaźnikach zamiast na indeksach - ja wybrałem indeksy, bo porównywanie wskaźników działa źle w niektórych systemach operacyjnych. Dalej: gdyby zmienna tymczasowa t była problemem, można zamieniać elementy tablicy "w miejscu", znanym sposobem - ale specjalnie tego nie zrobiłem, żeby nie zaciemniać rozwiązania.Piotr G. edytował(a) ten post dnia 21.05.10 o godzinie 23:22

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Piotr G.:
25 minut :), ale powinno zadziałać, choć nie sprawdzałem.

Powinno działać, ale na moje oko to nie jest czas O(n).

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Jest pomiędzy O(n) a O(2n), czyli jest rzędu O(n).
Można dla porządku zmienić warunek w pętli na taki:

  for (i1 = i2 = 0; (i1 <= i2) && (i2 < n);)

i wtedy będzie bardziej to widać, choć ilość przebiegów pętli nie ulegnie tak naprawdę zmianie.
Ale mi się taki warunek mniej podoba :)

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Piotr G.:
25 minut :), ale powinno zadziałać, choć nie sprawdzałem.

Sprawdziłem - nie działa ;)

Kontr przykład:
Dla wejścia:
[1, 101, 102, 103, 104] [3, 4]
Wyjście jest takie samo :), czyli:
[1, 101, 102, 103, 104, 3, 4]

Oczywiście pętlę można zrealizować na 100 różnych sposobów ;), ale to tak naprawdę nie ma znaczenia.

Szczegóły implementacyjne nie mają tu żadnego znaczenia. Chodzi o czytelny kod i, przede wszystkim, złożoność czasową i pamięciową.

@Piotr P.
Widać gołym okiem, że złożoność czasowa algorytmu Piotrka G. to O(n).

[..] Dalej: gdyby zmienna tymczasowa t była problemem, można zamieniać elementy tablicy "w miejscu", znanym sposobem - ale specjalnie tego nie zrobiłem, żeby nie zaciemniać rozwiązania.

Tu chodzi o algorytm, a nie jakieś drobiazgi, jak zamieniamy wartości w dwóch komórkach tablicy. Come on ;]

btw:
Mam wrażenie, że zamiast:
int i1; // index for vector 1
int i2; // index for vector 2

... chciałeś zapisać:
int i1 = 0; // index for vector 1
int i2 = j; // index for vector 2

... ale to szczegół i myślę, że to Twoja literówka.

Pozdrawiam, Adam WoźniakAdam Woźniak edytował(a) ten post dnia 22.05.10 o godzinie 00:26

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Adam Woźniak:

>

Sprawdziłem - nie działa ;)

Zabiłeś mnie...

Wygląda na to, że jednak j jest potrzebne.
A więc wersja 2, z jawnym wyznaczaniem j i z usuniętymi naleciałościami z C# (deklaracja zmiennych w środku ciała funkcji):

void internal_merge(int *arr, int n)

{

  int j; // begin of vector 2

  int i1, i2; // indexes for vector 1 and vector 2



  if (n < 2)

    return; // nothing to do :)



// calculate j

  for (j = 1; j < n; j++)

    if (arr[j] < arr[j - 1])

      break;



  if (j >= n - 1)

    return; // only one vector, so arr is already sorted



// Now we have:

// vector 1: arr[0]...arr[j-1]

// vector 2: arr[j]...arr[n-1] 



// so merge

  for (i1 = 0, i2 = j; (i1 < j) && (i2 < n);)

    if (arr[i1] > arr[i2])

    {

      // item in vector 2 is lower than item in vector 1, so swap them

      int t = arr[i2];

      arr[i2] = arr[i1];

      arr[i1] = t;

      i1++;

    }

    else

      i2++;



  return;  

}

Ale cały czas mam wrażenie, że da się to zrobić na jednej pętli...Piotr G. edytował(a) ten post dnia 22.05.10 o godzinie 00:52

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Piotr G.:

Adam Woźniak:

>

Sprawdziłem - nie działa ;)

Zabiłeś mnie...

Zabiłem od razu... ;]
Po prostu copy+paste do IDE i jazda.

Wygląda na to, że jednak j jest potrzebne.

Tyle, że ja puszczając Twój kod uwzględniłem, że i2 powinno być zainicjalizowane na j.
W Twoim poprawionym kodzie, głowna pętla wciąż wygląda tak samo, więc cały algorytm tak jak nie działał wcześniej, tak i nie działa teraz.

Innymi słowy dla tego samego przykładu:
[1, 101, 102, 103, 104] [3, 4]

... kod wciąż nie działa.

A więc wersja 2, z jawnym wyznaczaniem j i z usuniętymi naleciałościami z C# (dekladracja zmiennych w środku ciała funkcji):

Kwestia gustów ;]
Ja np. lubię deklaracje w środku ciała funkcji i "nienawidzę" silenia się na wyciąganie deklaracji wszelkich zmiennych na samą górę rzeczonej funkcji ;]

Ale cały czas mam wrażenie, że da się to zrobić na jednej pętli...

No ja mam wrażenie, ze Twój obecny algorytm jest w jednej pętli.
Mniejsza o szczegóły: istotne jest to, że działa w czasie O(n) i ... jest niepoprawny ;P

Pozdrawiam, Adam Woźniak

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Adam Woźniak:
Ja np. lubię deklaracje w środku ciała funkcji i "nienawidzę" silenia się na wyciąganie deklaracji wszelkich zmiennych na samą górę rzeczonej funkcji ;]

No tak, ale to już nie ANSI C :)

Ale cały czas mam wrażenie, że da się to zrobić na jednej pętli...

No ja mam wrażenie, ze Twój obecny algorytm jest w jednej pętli.

Chodziło mi o to, że wcale nie jestem pewny, czy jawne wyznaczenie j jest konieczne.

Mniejsza o szczegóły: istotne jest to, że działa w czasie O(n) i ... jest niepoprawny ;P

Kurde, o tej porze każesz mi jeszcze myśleć?
Dobra, daj mi 10 minut... :)

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Piotr G.:

Adam Woźniak:
Ja np. lubię deklaracje w środku ciała funkcji i "nienawidzę" silenia się na wyciąganie deklaracji wszelkich zmiennych na samą górę rzeczonej funkcji ;]

No tak, ale to już nie ANSI C :)

ANSI C to historia ;]

Ale cały czas mam wrażenie, że da się to zrobić na jednej pętli...

No ja mam wrażenie, ze Twój obecny algorytm jest w jednej pętli.

Chodziło mi o to, że wcale nie jestem pewny, czy jawne wyznaczenie j jest konieczne.

Aaa... Chodzi Tobie o "j".
"j" też nie ma tu większego znaczenia :) Spokojnie można założyć, ze j jest jednym z argumentów funkcji, która nalezy tu zaimplementować ;)

Mniejsza o szczegóły: istotne jest to, że działa w czasie O(n) i ... jest niepoprawny ;P

Kurde, o tej porze każesz mi jeszcze myśleć?

Ja nic nie każę ;] Jeśli już to jest to taka trochę prowokacja ;]

Dobra, daj mi 10 minut... :)

Mogę dać Tobie (i innym) nawet 10 dni ;P
Widać, dałeś się złapać (nie Ty jeden), na pozorną prostotę tego problemu ;) Też, kiedy kiedyś nad tym dumałem, zagadka wydawała mi się w miarę prosta ;)
Ale widzę, że podobnie jak ja swego czasu, nie dopuszczasz do siebie, że zadanie jest na prawdę nietrywialne ;P

Pozdrowienia, Adam Woźniak

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Już widzę, że jest nietrywialne :(

Mimo wszystko nie podawaj linka do przykładowego rozwiązania przed poniedziałkiem, ok?

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Piotr G.:
Już widzę, że jest nietrywialne :(

A nie mówiłem? ;]

Mimo wszystko nie podawaj linka do przykładowego rozwiązania przed poniedziałkiem, ok?

Nie ma problemu - mnie się nigdzie nie spieszy.

Ale poważnie: rozwiązanie, które kiedyś znalazłem w internecie, jest mocno nietrywialne :)

Pozdrawiam, Adam Woźniak

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

ok po głębszy przemyśleniu stwierdzam FAJNE :)

void magic_merge(int *tab, int size) {

  int *a, *b, *c;



  a = c = tab;

  b = tab+size-1;





  while (a<b && *a<=*(a+1))

    a++;



  while (c < tab+size && b>c) {



//    printf(" T = ");printtab(tab, size);



    if (a>c && *a>*b) {

      SWAP(*c,*a);

      c++; a--; continue;

    }



    if (*b > *c)

      SWAP(*c,*b);



    if (b<(tab+size-1) && *b < *(b+1))

      b++;

    if (*b < *(b-1))

      b--;



    c++;

  }



  a = tab; b = tab+size-1;

  while (a < b) {

    SWAP(*a,*b);

    ++a;--b;

  }



}

Dla powyższych przypadków testowych i kilku innych działa :) ale nie daję gwarancji :)

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Karol Nowacki:
ok po głębszy przemyśleniu stwierdzam FAJNE :)

[...]

Dla powyższych przypadków testowych i kilku innych działa :) ale nie daję gwarancji :)

Ha - na podzial na 3 części tablicy wpadłem, tylko implementacja robiła się trochę zagmatwana, ale porównywanie od końca rzeczywiście działa. Gratuluje - dla bardziej złożonych przypadków też mi zadziałało :)

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Karol Nowacki:
ok po głębszy przemyśleniu stwierdzam FAJNE :)

void magic_merge(int *tab, int size) {

  int *a, *b, *c;



  a = c = tab;

  b = tab+size-1;





  while (a<b && *a<=*(a+1))[/quote]>     a++;[quote]

  while (c < tab+size && b>c) {



//    printf(" T = ");printtab(tab, size);



    if (a>c && *a>*b) {

      SWAP(*c,*a);

      c++; a--; continue;

    }



    if (*b > *c)

      SWAP(*c,*b);



    if (b<(tab+size-1) && *b < *(b+1))[/quote]>       b++;[quote]    if (*b < *(b-1))[/quote]>       b--;[quote]

    c++;

  }



  a = tab; b = tab+size-1;

  while (a < b) {[/quote]>     SWAP(*a,*b);[quote]    ++a;--b;

  }



}

Dla powyższych przypadków testowych i kilku innych działa :) ale nie daję gwarancji :)

Ode mnie:
To żonglowanie wskaźnikami (zamiast indeksami) dla mnie jest mało czytelne. Myślę, że używanie indeksów (zamiast wskaźników) jest bardziej czytelne.
W tym zapisie nie rozumiem tego algorytmu ;] Dałbyś może więcej komentarzy w kodzie, albo słowami opisał co się w tym algorytmie dzieje. Wtedy będę mógł przygotować przypadek, dla którego ten kod nie działa ;)

btw:
Puszczałeś ten kod? :) Bo widząc funkcje SWAP mam wrażenie, że to jedynie pseudokod, a nie kod do uruchomienia jako kod w C.

Pozdrawiam, Adam Woźniak

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Ja tego nie mogę pojąć. Ok może ja jestem dziwny i może mój perfekcjonizm jest bez sensu, ale to co tu się dzieje mnie przeraża. Was to nie przeraża?

Kiedyś wziąłem udział w konkursie programistycznym. Taki typowy konkurs algorytmiczny, zdaje się, że tytuł brzmiał "Pogromcy Algorytmów". (Jak ktoś jest ciekaw, to są gdzieś jeszcze ślady tego w internecie i zdaje się że zadania zostały opracowane w jednej z książeczek z zadaniami z olimpiad informatycznych, więc można sobie postudiować). Jako, co najwyżej, programista hobbysta byłem kompletnie zielony, nie miałem za grosz przygotowania z algorytmiki i oczywiście nie zaszedłem za daleko. Zrobiłem kilka pierwszych zadań i się poddałem. Ale te kilka pierwszych zadań zrobiłem na 100%. Nawet by mi do głowy nie przyszło, żeby wysyłać rozwiązanie, które może mieć szansę, co najwyżej, na kilka punktów. Przecież to nie jest rozwiązanie. Masa ludzi przyjęła taktykę, aby wysłać cokolwiek, byle zdobyć jakieś punkty. W porządku, w konkursie ze zautomatyzowanymi testami jest to może jakaś tam taktyka i mogę to zrozumieć.

Ale tu? Rzucacie w pana Adama jakimś kawałkiem nie przetestowanego i nabazgrolonego na kolanie kodu, na zasadzie - masz sprawdź czy mi się udało? Programiści? To wy nie wiecie sami, czy wam się udało? Może jeszcze zaczniecie lotniska budować i wraki samolotów przystrajać, a nuż dary z nieba zlecą?Maciej Hehl edytował(a) ten post dnia 22.05.10 o godzinie 20:59

Temat: [zagadka] scalenie w czasie O(n) i dodatkowej pamięci O(1)

Maciej Hehl:
Ja tego nie mogę pojąć. Ok może ja jestem dziwny i może mój perfekcjonizm jest bez sensu, ale to co tu się dzieje mnie przeraża. Was to nie przeraża?

No troszkę wskżników jest i kilka sztuczek, ale właśnie, aby nie zaciemniać algorytmu użył pewnie makra swap (można sobie na poczekaniu coś takiego napisać). Idea jest taka, że dzielisz tablicę na 3 części
1) w którą wstawiasz 2) ta która jest do dołączenia i 3) taki bufor.
Ja np. chciałem zrobić bufor pomiędzy 1) i drugą częścią tablicy, ale w pewnyym momencie robi się rzeźnia, jesli chodzi o czytelność kodu właśnie i za dużo wrunków. Kolega podszedł do problemu w ten sposób, że bufor robi na końcu, w zamian za to odwraca sortowanie (stąd na samym końcu masz odwrócenie tabeli)