Program Do Sortowania

[hojrak6]

Witam

 

Mam taki problem. Musze napisac program ktory sortuje na 5 roznych sposobow tablice 10tys - 250tys elementowa.

 

Zrobilem sobie najpierw okienko w ktorym generuje losowo 250 tys i wlasnie wypisanie w tym okienku( samo wypisanie bez sortowania) trwa mniej wiecej 5 minut na richedicie lub 2 minuty na StringGridzie. Niewiem jak to przyspieszyc. Sortoweania jeszce nie napisalem bo narazie musze jakos sie z tym uporac.

 

Na Richedicie zrobilem to tak;

for i:0 to 250000 do   tab[i]:= Random(1000);Richedit1.text := Richedit1.text + inttostr (tab[i]);

A nna stringridzie:

for i:=0 to 250000 do	for x:= 0 to 100 do		for y:=0 to 2000 do Begin			   tab[i]:= Random(1000);			  stringgrid1.cells[x,y] := tab[i];

 

 

Strasznie dlugo sie wypelniaja te okienka, co robie zle??

 

Z gory dziekuje za pomoc.

Pozdrawiam

[Jastrząb]

Jezeli ma byc to tez widoczne dla uzytkownika a program ma byc graficzny to zamiast richedita uzywaj memo mysle ze bedzie to szybsze niz stringgrid ale nie spodziewaj sie ze wypelnisz to w pare sekund

[hojrak6]

Witam

 

Mysle ze w memo a richedicie nie bedzie roznicy. Problem polegal na tym ze do richedita sklejalem w zlej petli.

Zrobilem tak ze do innej petli wstawilem dodatkowa zmienna gdzie sklejalm do niej calosc i po za petelkami dalem richedit= zmienna; teraz 250tysiecy wypisuje sie w sekundke moze dwie.

 

Teraz mam problem jak zrobic zegar zeby porownac te sortowania. Wiem ze gdzies tu na forum kiedys to bylo ale niemoge sie doszukac cos :(

 

Chce tez wrzucic Progressbara ale niewiem jak sie za to zabrac. Jutro zaczne na ten temat przeszukiwac google, narazie zelezy mi na tym zegarze bo to potrzebuje do zadania a progressbar to taki dodatek sobie bedzie.

 

Co prawda jeszcze nie udalo mi sie posortowac babelkowo 250tys bo nie wytrzymuje do konca :) za dlugo to trwa. Jak juz bede mial zegar to wtedy pozwole mu dokonczyc.

 

Pozdrawiam

Edytowane 16 Marca 2006 przez hojrak6

[Jastrząb]

jezeli chodzi o zegar to uzyj timera z odpowiednim intervalem, a sortowalbym przy uzyciu algorytmu opartego na metodzie dziel i zwyciezaj

[hojrak6]

Witram

 

Ponizej jest sortowanie przez zliczanie. Niewiem dlaczego ale nie dziala mi to za dobrze.

Dla malej liczby elementow nie dziala w ogole, poprostu sie przepisuje tablica wejsciowa. Dla wysokiej liczby elementow sortuje dobrze lecz np. na poczatku jest zbyt wiele 0 lub na koncu sie wysypuje i przepisuje jak leci bez sortowania.

 

procedure TForm1.Button5Click(Sender: TObject);var i,c:integer;k:integer;pomoc: array [0..250000] of integer;	a: string;beginfor i:=1 to ilosc_el do pomoc[i]:=0;for i:=1 to ilosc_el do inc(pomoc[tab_sort[i]]); c:=1;for i:=0 to ilosc_el do		begin		for k:=1 to pomoc[i] do				begin				tab_sort[c]:=i;				inc(c);				end;		end;for i:=1 to ilosc_el do a:= a + inttostr(tab_sort[i])+ '  ';richedit5.Text:=a;end;

 

A co do zegara to jhak go urzyc ?? na poczatku algorytmu robie timer1.enable:= true; a na koncu co trzeba zrobic zeby wyplul do labela1.caption czas trwania ?

Edytowane 17 Marca 2006 przez hojrak6

[Jastrząb]

nie mam teraz zbytnio czasu na szczegoly ale takie szybkie pytania

co to jest ilosc_el

 

a z timerme to zorb tak ze ustaw interval na 500

pod przycisk daj uruchomienie procedury sortujacej, oraz uruchomienie timera

w prcedurze sortujacej daj jakas zmienna boolean ktora informuje o tym ze sortowanie sie skonczylo

a w ontimer

if koniec then Timer.Active:= false; //koniec to zmienna informujaca o koncu sortowania

 

aha w ontimer musisz dac jeszcze zmienna integer ktora zlizca wystapienie tej procedury i na koniec mnozysz ilosc wystapien przez interval, dzielisz przez 1000 i masz czas w sekundach

 

ps

dlugo nic nie pialem to moga byc bledy a pisalem to z glowy

[hojrak6]

Witam

 

 

Stoper juz zrobilem. Znalazlem w ksiazce helionu " Praktyczny kurs Delphi" jak to zrobic.

 

Co do zmiennej ilosc_el to poprostu ilosc elementow tablicy ktora wprowadzam przez komponent EDIT.

 

czuli poprostu tab_sort: [1 .. ilosc_el] of integer;

 

Ogolnie juz mnie wkurza to sortowanie przez zliczanie, niewiem czmu duzo elementow sortuje a malo nie.

Jeszce totalnie neiwiem jak sie zabrac za sortowanie stogowe (przez kopcowanie).

 

Dzieki za odpowiedzi

Pozdrawiam

Edytowane 17 Marca 2006 przez hojrak6

[Jastrząb]

na szybko napialem funkcje, wiec moze zawierac bledy. Nie mam jej jak przetestowac bo narazie nie dysonuje srodowiskiem. Wszytsko pisane z glowy.

 

function sortuj(var tabliczka : array of integer):boolean;	//tabliczka to tablica do wysortowaniavar  temp : array of integer;  i, k : integer;  pozycja : integer;begin  pozycja:= 0;  SetLength(temp, 1);  for i:= Low(tabliczka) to High(tabliczka) do	//sporzadzenie pomocniczej tablicy  begin	if Length(temp) < tabliczka[i]+1 then	begin	  SetLength(temp, tabliczka[i]+1);	  tabliczka[i] := 1;	end	else	Inc(temp[tabliczka[i]]);  end;  for i :=0 to High(temp) do			//wysortowanie  begin	if temp[i] > 0 then	for k:= 1 to temp[i] do	begin	  tabliczka[Low(tabliczka) + pozycja] := temp[i];	  Inc(pozycja);	end;  end;  if pozycja+1 = length(tabliczka) then		//True jezeli sie wszystko wysortowalo	Result:=True  else	Resul:=False;end;

Edytowane 18 Marca 2006 przez Jastrząb

[hojrak6]

Cos nie dziala tylko niewiem co. Wyskakuje error ze niema dostepu to jakiegos adresu pamieci.

[Jastrząb]

a w ktorej linijce jest blad?

Blad moze byc w pobraniu zmiennej przez funckej bo juz nie jestm pewny jak przekazywalo sie tablice w delphi

 

---edit---

nie jestem pewny ale tablica ktora przekazujesz musi byc zmienna globalna, a jak nie to pokaz cale zrodlo

 

---edit2---

poprawilem kod gdyz mial pare bledow, przekopij go jeszzce raz

Edytowane 18 Marca 2006 przez Jastrząb

[hojrak6]

Tzn. program sie kompiluje dobrze ale podczas dzialania programu jak klikne na przycisk od sortowania to wyskakuje ten error.

 

Jak zrobie z menu Run/Step over

 

to wskazuje ta linie for i :=0 to High(temp) do

[Jastrząb]

a teraz?

[hojrak6]

nadal cos nie tak.

Teraz sie cos sortuje ale niewiem skad te liczby, sam zobacz:

 

Do posortowania:

 

149 129 610 28 2 582 723 371 226 404 134 907 223 465 258 799 940 899 499 512 728 332

 

Po sortowaniu:

 

5 5 5 5 5 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252 252

 

EDIT:

 

Niemoge rowniez sobie poradzic z generacji liczb tak aby liczby rosly a pozniej malaly. Tak zwane zbocze czyli dla 20 elementow tablica wtgladala:

 

1,2,3,4,...10 20,19,18...11

 

dla 50

 

1,2,3,4..25,50,49,48....26

 

wydaje mi sie ze ponizszy algorytm jest dobry ale 2 czesc czyli zbocze opadajace pokazuje na wszystkich miejscach 1 liczbe czyli zamiast 20,19,18 jest 10,10,10 a w drugim przykladzie 25,25,25, zawsze 50% podanej liczby elementow.

 

Begin	   for i:=0 to (ilosc_el div 2) do	   Tab[i]:=i;	   for j:=(ilosc_el div 2)+1 to ilosc_el do	   begin			for k:= ilosc_el downto ilosc_el div 2 do			Tab[j]:=k;	   end;	 end;

Edytowane 18 Marca 2006 przez hojrak6

[Jastrząb]

sciagne sobie Delphi Personal to sprawdze ten algorytm co dalem, lecz niestety przy moim laczu zdaze chyba dopiero na poniedzialek/wtorek. Ponizej zamieszczam kod do genereacji ciag rowniez pisany z glowy

 

for i:=0 to (ilosc_el div 2) do	   Tab[i]:=i;	   Tab[ilosc_el] := (ilosc_el div 2)+1;	   for j:=ilosc_el-1 downto (ilosc_el div 2)+1 do	   Tab[j]:=Tab[j+1]+1;

Edytowane 18 Marca 2006 przez Jastrząb

[hojrak6]

Mozesz jeszce oblukac to: znowu cos nie chce dzialac.

Procedure quicksort(Lewy, Prawy: integer); Var	i,j: integer;	podzial, x:integer;begin  i:=Lewy;  j:=Prawy;  podzial:= tab_sort[(Lewy + Prawy)div 2];  Repeat	  while tab_sort[i] < podzial do		Inc(i);	  while podzial< tab_sort[j] do		Dec(j);	if i<= j then	Begin	  x:=Tab_sort[i];	  tab_sort[i]:=tab[j];	  tab_sort[j]:= x;	  Inc(i);	  Dec(j);	End;  Until(i>j);  if (lewy < j)  then quicksort(lewy,j);  if (i < prawy) then quicksort(i, prawy);end;procedure TForm1.Button8Click(Sender: TObject);var i: integer;	a: string;BEGINquicksort(1,ilosc_el);for i:=0 to ilosc_el do   a:=a + inttostr(tab_sort[i]) + ' ';Richedit7.Text:= a;END;

 

Juz poprawilem, ponizszy kod dziala:

 

procedure QuickSort(Lewy, Prawy : integer);var  i, j : integer;  podzial, x : integer;begin  i := Lewy;  j := Prawy;  podzial := tab_sort[(Lewy+Prawy) div 2];  repeat	while tab_sort[i] < podzial do	  Inc(i);	while podzial < tab_sort[j] do	  Dec(j);	if i <= j then	begin	  x := tab_sort[i];	  tab_sort[i] := tab_sort[j];	  tab_sort[j] := x;	  Inc(i);	  Dec(j);	end;  until (i > j);  if Lewy < j then QuickSort(Lewy, j);  if i < Prawy then QuickSort(i, Prawy);end;procedure TForm1.Button8Click(Sender: TObject);var i: integer;	a: string;BEGINquicksort(1,ilosc_el);for i:=0 to ilosc_el do   a:=a + inttostr(tab_sort[i]) + ' ';Richedit7.Text:= a;END;

Edytowane 19 Marca 2006 przez hojrak6

[Jastrząb]

napisz w czym problem, nie mam teraz zbytnio czasu, jedyne co zaowazylem to to ze mozesz zaoszczedzic troche pamieci stosujac przekazanie paremetru do procedury przez adres

Procedure quicksort(var Lewy, Prawy: integer);

[hojrak6]

Witam

 

Mam takie pytanko, aby powyzszy kod quick sorta zmienic na quick sorta przez element losowy to wystarczy tylko zmienic podzial:= tab_sort[(Lewy + Prawy)div 2]; na Podzial:= tab_sort(random(lewy + prawy))?? bo dziala mi to dla tablicy do 5tys puzniej posortowanie trwa wieki. Musze posortowac tym tablice 250tys, a gdy ja zapuscilem to po 2 godzinach nadal program sortowal.

Edytowane 21 Marca 2006 przez hojrak6

[Jastrząb]

Witam

 

Mam takie pytanko, aby powyzszy kod quick sorta zmienic na quick sorta przez element losowy to wystarczy tylko zmienic podzial:= tab_sort[(Lewy + Prawy)div 2]; na Podzial:= tab_sort(random(lewy + prawy))?? bo dziala mi to dla tablicy do 5tys puzniej posortowanie trwa wieki. Musze posortowac tym tablice 250tys, a gdy ja zapuscilem to po 2 godzinach nadal program sortowal.

jezeli dasz random(lewy+prawy) to zosatnie wylosowana liczba z zakresu od 0 do (lewy+prawy-1), wiec jezeli lewy wynosi 5 to moze trafic na liczbe x ktora nie spelnia warunku lewy<x<prawy

 

btw

jezeli stosujesz funkcje random to w programie musisz takze zastosowac procedure randomize (najlepiej ja dac w onCreate formy)

[hojrak6]

No a wlasnie o to chyba chodzi zeby np liczba elementow w tablicy byla 5 i przykladowo sortowalo sie wedlug 4 elementu, bo jezeli bedzie spelniony warunek o ktorym mowisz to przeciez bedzie znowu srodkowy element. Chyba ze ja cos zle rozumiem.

[Jastrząb]

jezeli bedie tak ze:

lewy = 5

prawy = 11

to

(lewy+prawy)/2 <> random(lewy+prawy)

poniewaz

w pierwszym wypadku wynikeim bedzie 8 a w drugim jakas liczba od 0 do 15 wlacznie

[hojrak6]

Moglbys mi pomuc z tym elementem losowym, bo niewiem jak sie za to zabrac. Mi sie caly czas wydaje ze to random dobrze losuje element losowy. Kumpel pisze to w c. On tez tak zmienil i mu sortuje to w 6 s. a mi po 2 godzinach niechce sortowac. Mi Tablice 5 tysiecy sotuje 65 sekund, a jemu tablice 250tys w 6 sekund.

[Jastrząb]

powinno byc chyba tak:

random(prawy-lewy+1)+lewy;