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

Tomasz Kaczanowski:

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

Obawiam się, że takiego makra SWAP nie da się napisać, bo w kodzie wywołanie wygląda tak:
SWAP(*c,*a);

... czyli do makra trafiają dwa int'y, a celem makra jest zamienienie dwóch elementów w tablicy (czyli powinno wywołanie wyglądać tak: SWAP(c,a)).

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)

Zanim nie zobaczę kodu Karola (lub kogokolwiek innego) z komentarzami, co się w kodzie dzieje i co każda ze zmiennych przechowuje, nie podejmuję się odcyfrowania tego kodu.

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

Dzięki za pomoc w rozszyfrowywaniu kodu (to nie sarkazm, pomoc zawsze cenię), ale zupełnie nie o to mi chodziło.

Fakt że kodu tego typu nie czyta się lekko, jak lektury do poduszki, ale myślę że bym sobie poradził. Może nie w 3 minuty, ale jestem w stanie takie rzeczy rozszyfrować.

Chodziło mi o to, że za grosz nie rozumiem ludzkiej postawy, jak prezentowana w tym wątku.

A wracając do kodu, to proszę, oto kontrprzykład

int tab[] = {1, 3, 5, 7, 9, 11, 13, 2, 4, 6, 8, 10};

Nie twierdzę, że to minimalny kontrprzykład. Nie skończyłem analizować kodu i nie rozumiem go jeszcze do końca, ale przypadkiem na taki trafiłem sprawdzając parę rzeczy.

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

Maciej Hehl:
A wracając do kodu, to proszę, oto kontrprzykład

int tab[] = {1, 3, 5, 7, 9, 11, 13, 2, 4, 6, 8, 10};

Nie twierdzę, że to minimalny kontrprzykład. Nie skończyłem analizować kodu i nie rozumiem go jeszcze do końca, ale przypadkiem na taki trafiłem sprawdzając parę rzeczy.

rzeczywiście z tego co widzę nie działa, kwestia jest zapewne tego, że kontrola nad wskaźnikiem a po kilku iteracjach się kończy i o ile strefa wokół b jest kontrolowana, to ta pomiędzy a i kroczącym c nie.

mała zamiana

zamiast ostatniego c++ moim zdaniem należałoby wstawić:

if (*c < *(c-1))

{

      c++;

}

else

{

    	a++;

        c--;

}  

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

Adam Woźniak:

Tomasz Kaczanowski:

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

Obawiam się, że takiego makra SWAP nie da się napisać, bo w kodzie wywołanie wygląda tak:
SWAP(*c,*a);

Trochę sztuka dla sztuki, ale da się:

#define SWAP(a, b)  a ^= b; b ^= a; a ^= b; 

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

Obawiam się, że takiego makra SWAP nie da się napisać, bo w kodzie wywołanie wygląda tak:
SWAP(*c,*a);

Trochę sztuka dla sztuki, ale da się:

#define SWAP(a, b)  a ^= b; b ^= a; a ^= b; 

Chyba masz rację, a mi się pochrzaniło.
Od lat nie pisałem makr w C i zapomniałem o różnicach pomiędzy makrami, a wywołaniami metod.

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

No, zeby to marko bylo w pelni poprawne, trzeba by pododawac troche nawiasow jeszcze, ale i tak makra sa slabe, bo trzeba uwazac na efekty uboczne...

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

Adam Michalski:
No, zeby to marko bylo w pelni poprawne, trzeba by pododawac troche nawiasow jeszcze, ale i tak makra sa slabe, bo trzeba uwazac na efekty uboczne...

To już zupełnie tak zwana "insza inszość", no i nie jest to makro zbyt uniwersalne, nie w każdym przypadku zadziała poprawnie, dlatego napisałem "sztuka dla sztuki"

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

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

Pozdrawiam, Adam Woźniak

Adam, mysle ze czas podac rozwiazanie... co sadzisz? :)Adam Michalski edytował(a) ten post dnia 24.05.10 o godzinie 11:29

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

Adam Michalski:

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

Pozdrawiam, Adam Woźniak

Adam, mysle ze czas podac rozwiazanie... co sadzisz? :)

Tak, obiecałem, że do poniedziałku się wstrzymam, więc juz czas ;]

Lubię ten problem (zagadkę), bo wydaj się (na początku) dosyć łatwa, a okazuje się w końcu bardzo trudna :)

Jak wspominałem, udało mi się znaleźć w Internecie rozwiązanie tego problemu:
Practical In-Place Merging
BING-CHAO HUANG and MICHAEL A. LANGSTON
http://www.cs.utk.edu/~langston/courses/cs594-fall2003...

Jak widać w opisie, algorytm jest całkiem skomplikowany, acz bardzo sprytny :)
Zainteresowanych zapraszam do lektury (15 minut minimum :) ).

Pozdrawiam, Adam Woźniak