algorytmy Kaśka: Czy jest ktoś tutaj kto zna się na algorytmach. Mam takie zadanko i nie do końca wiem jak je zrobić. Liczę na waszą pomoc za którą serdecznie dziękuję. "Zaproponuj wykonanie algorytmu mergesort tak by wykonać ten algorytm w tablicy bez wychodzenia poza nią."

Blee: W jakim języku ma być ? Masz jakikolwiek pomysł jak to zrobić ?

Krzysiu: tablica ma mieć jeden wymiar czy może być dwuwymiarowa?

Kaśka: To ma być po prostu zrobione. Jakiś przykład czy coś w tym stylu. Mam zrobić to na tablicy. Miałam z tego dopiero jedne zajęcia więc za bardzo pomysłów nie mam

Kaśka: Krzysiu raczej jeden

Blee: aha ... ma być "po prostu zrobione" −−− no i wszystko jasne

Krzysiu: ja w swoim programie zrobiłem dwuwymiarową xd

Blee: Miałaś jakieś języki programowania? Chociaż schemat blokowy był? Jakie to zajęcia? Na jakim kierunku?

Kaśka: haha

Kaśka: W liceum miałam programowanie w C++, na studiach C. Jest to przedmiot algorytmy i struktury danych na kierunku matematyka finansowo−ubezpieczeniowa

Blee: Patrząc na przedmiot −−− zapewne schemat blokowy będzie prowadzącego interesował ... a co było na tych zajęciach? W jaki sposób zapisywał algorytmy?

Kaśka: Przerobione mieliśmy po jednym przykładzie z każdego sortowania jak na razie. A na następne zajęcia kazał przygotować takie rzeczy

jc: Oj, obawiam się, że bez straty szybkości to niemożliwe. Dobrze mieć przynajmniej połowę tablicy dodatkowo. Widziałem kiedyś algorytm sortowania przez sklejanie pracujący w miejscu. Teoretycznie miał chyba złożoność n (ln n)², ale nie wiem czemu działał szybciej.

Blee: No i w jaki sposób ZAPISAŁ te sortowania? W jakimś języku (C, C++)? Schematem blokowym? Słownie? Pokazał na pacynkach?

Kaśka: No nic to dziękuję za szczere chęci Wam. Jesteście kochani

Kaśka: pokazał tablice. I ją posortował

Blee: Kasiu −−− algorytm możemy podać ... nie będą zapewne najbardziej eleganckie algorytmy, a na pewno nie będą one najefektywniejsze ... ale będą tylko nadal nie wiemy (od Ciebie nie mogę tego wyciągnąć) W JAKIEJ FORMIE ma ów algorytm być przedstawiony.

Blee: no dobra ... czyli de facto masz po prostu zaprezentować JAK DZIAŁA TEN ALGORYTM i nic ponad to

Kaśka: Na przykładzie można to zrobić?

jc: Znalazłem /* sortowanie przez sklejanie w miejscu, czas = n (ln n)² */ #include<stdio.h> void sklej(int *p, int *s, int *k) { if( p<s && s<k ) { int *r, *q, *i, *j; for( r=s, q=s; p<r && q<k && *(r−1)>*q; r−−, q++); for( i=r, j=s; i<s; i++, j++) { int t=*i; *i=*j; *j=t; } sklej(p,r,s); sklej(s,q,k); } } void sortuj(int *p, int *k) { if( p<k−1 ) { int *s; s=p+(k−p)/2; sortuj(p,s); sortuj(s,k); sklej(p,s,k); } } int main() { int i; int t[20]={2,5,7,1,9,2,0,2,12,4,13,9,11,45,54,8,9,10,2,10}; for( i=0; i<20; i++) printf("%3d", t[i]); printf("\n"); sortuj(t,t+20); for( i=0; i<20; i++) printf("%3d", t[i]); printf("\n"); return 0; }