sortowanie liczb w 8051 (ASM)



Masz problem? Zapytaj na forum elektroda.pl

Poprzedni Następny
Wiadomość
Spis treści
From: "BRT" <bartosz.rossa_at_nospam_gazeta.pl>
Subject: sortowanie liczb w 8051 (ASM)
Date: Tue, 6 May 2003 19:39:17 +0200


Czy ktoś realizował w 8051 sortowanie liczb?



--
Serwis Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!news.gazeta.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "BRT" <bartosz.rossa_at_nospam_gazeta.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Tue, 6 May 2003 21:12:10 +0200


chodzi o sortowanie 16 liczb 4bajtowych ze znakiem w notacji uzupelnienia 2.

Użytkownik "Michał Wojtków" <michallo4_at_nospam_wp.pl> napisał w wiadomości
news:b98u4k$300$1_at_nospam_atlantis.news.tpi.pl...
Osobiscie nie, ale robilem to na PC.
Najprostsza metoda, lecz troche wolna to metoda bombelkowa,
Polega na porównywaniu 2 zmiennych i przestawiania,
myślę za na `51 bedzie to tak samo działać- ale tu głowy nie dam
A tak z ciekawosci o ile zmiennych i jakie typu chcesz porownywac?
Pozdrawiam Michał





--
Serwis Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Wed, 7 May 2003 13:54:43 +0200


BRT wrote:

chodzi o sortowanie 16 liczb 4bajtowych ze znakiem w notacji uzupelnienia
2.

Oto moje propozycje w kolejnosci latwosci zrobienia:

zlozonosc asymptotyczna O(n^2).

babelkowego, specjalnie przystosowana do sortowania tablic.
Zlozonosc O(n^{log_2 3}), wiec ~O(n^1,58).


bo dzieki wykorzystaniu dodatkowych informacji o budowie obiektu
umozliwia "przebicie" teoretycznej granicy zlozonosci sortowania przez
porownania, co pozwala sortowac dane w czasie liniowym. Skoro
pytasz o takie podstawy, mozesz sobie nie poradzic z jego implementacja.

Sortowanie babelkowe sobie zdecydowanie odpusc, bo ono nie jest ani
najprostsze, ani najkrotsze. Insertion sort bardziej nadaje sie do
sortowania
list, a nie tablic, wiec rowniez go sobie odpusc. Polecam selection sort.

Pozdrawiam
Piotr Wyderski




========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Wed, 07 May 2003 23:43:00 +0200


On Wed, 7 May 2003 13:54:43 +0200, Piotr Wyderski wrote:
chodzi o sortowanie 16 liczb 4bajtowych ze znakiem w notacji uzupelnienia 2.

Oto moje propozycje w kolejnosci latwosci zrobienia:

- sortowanie Shella. Jest to zmodyfikowana wersja sortowania
babelkowego, specjalnie przystosowana do sortowania tablic.

Ale chyba nie na 16 danych ? Chociaz .. moze i cos da ?

Jest jeszcze jedna mozliwosc .. siec sortujaca. Zadnych petli,
kolejne porownania w kodzie. Tyle ze 16 sztuk to dosc duza
siec sie robi ..

J.



========
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.onet.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Thu, 8 May 2003 01:46:22 +0200



J.F. wrote:

Ale chyba nie na 16 danych ?

W celach testowych -- czemu nie... :-)

Chociaz .. moze i cos da ?

Komplikacje kodu da. :-) Istotnego przyspieszenia
dla tak malych danych bym nie oczekiwal.

Jest jeszcze jedna mozliwosc .. siec sortujaca. Zadnych petli,
kolejne porownania w kodzie.

Hm, ale po co rozwijac te petle? Wiekszosc czasu i tak pochlonie
32-bitowy komparator, niezaleznie od sortowania No i sortowanie
wg. jakiego pomyslu? Mergesort?

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Thu, 08 May 2003 22:14:19 +0200


On Thu, 8 May 2003 01:46:22 +0200, Piotr Wyderski wrote:
J.F. wrote:
Jest jeszcze jedna mozliwosc .. siec sortujaca. Zadnych petli,
kolejne porownania w kodzie.

Hm, ale po co rozwijac te petle? Wiekszosc czasu i tak pochlonie
32-bitowy komparator, niezaleznie od sortowania

No - niekoniecznie. A z drugiej strony glupio zakladac petle np
na 4 sztuki [przy shell]

No i sortowanie wg. jakiego pomyslu?

A, tu mozna poszukac optymalnej sieci :-)

J.


========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Fri, 9 May 2003 00:03:28 +0200



J.F. wrote:

No i sortowanie wg. jakiego pomyslu?

A, tu mozna poszukac optymalnej sieci :-)

No ale ja znam pare roznych architektur sieci sortujacych
i wszystkie one sa optymalne. :-)

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.atman.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Wed, 7 May 2003 13:36:37 +0200



BRT wrote:

Czy ktoś realizował w 8051 sortowanie liczb?

Ja nie, ale czym mialoby sie ono roznic od sortowania w crayu X MP? :-)

Pozdrawiam
Piotr Wyderski


========
Path: news-archive.icm.edu.pl!news.icm.edu.pl!fu-berlin.de!uni-berlin.de!glubsche.ukbf.fu-berlin.DE!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: Waldemar Krzok <waldemar.krzok_at_nospam_ukbf.fu-berlin.de>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Wed, 07 May 2003 15:35:03 +0200




Piotr Wyderski:
BRT wrote:


Czy ktoś realizował w 8051 sortowanie liczb?


Ja nie, ale czym mialoby sie ono roznic od sortowania w crayu X MP? :-)

w Cray XMP, ze względu na stronicowanie pamięci i pracę z przesuniętym
taktem, sortowanie stosowe na 16 stosach jest szybsze od sortowania
szybkiego. Ot taka siurpryza ;-)

Waldek


========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Wed, 7 May 2003 16:22:36 +0200


Waldemar Krzok wrote:

w Cray XMP, ze względu na stronicowanie pamięci i pracę z przesuniętym
taktem, sortowanie stosowe na 16 stosach jest szybsze od

Dobra, dokoncze mysl: "[...] na poziomie algorytmicznym?" :-)
O roznicach w sposobie implementacji sortowania na roznych
architekturach maszyn rownoleglych cos tam mi wiadomo. ;-D

sortowania szybkiego.

Sortowanie szybkie jest szybkie dlatego, ze ktos zdecydowal sie
nazwac je quick sort. Pesymistyczna zlozonosc tego algorytmu
wynosi O(n^2), teoretyczne optimum O(n lg n) osiaga tylko
w przypadku srednim. Algorytm ten jest wiec taki sobie. :-) Mozna
osiagnac teoretyczne optimum przez implementacje wyboru mediany
w czasie linowym (np. metoda tzw. magicznych piatek), ale wowczas
bedzie to algorytm o znaczeniu czysto akademickim ze wzgledu na
olbrzymi staly czynnik ukryty w notacji O(). :-) Zwykla implementacje
"zatkasz" dajac jej do posortowania ciag uporzadkowany wedlug
relacji przeciwnej do przyjetej, tzn. posortowany "od konca". Dlatego
wlasnie lubie heapsorta -- jest to algorytm asymptotycznie optymalny
i daje sie w wspanialy sposob zaimplementowac na rzeczywistej
maszynie. A do duzych liczb (a nie dowolnych obiektow, np. stringow)
nie ma chyba lepszej metody, niz radix sort; do malych -- counting sort.
Tu liczby sa duze, stad sadze, ze oryginalny pytacz nie da sobie rady
ze zrozumieniem zasady dzialania radixa -- jest nieco pokrecona. :-)
Hm, 16 liczb, tablica -- tylko selection sort, chyba, ze chcialoby sie
mu poeksperymentowac z Shellem, lecz IMO tu nie warto.

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Wed, 07 May 2003 23:42:58 +0200


On Wed, 7 May 2003 16:22:36 +0200, Piotr Wyderski wrote:
Waldemar Krzok wrote:
w Cray XMP, ze względu na stronicowanie pamięci i pracę z przesuniętym
taktem, sortowanie stosowe na 16 stosach jest szybsze od
sortowania szybkiego.

Sortowanie szybkie jest szybkie dlatego, ze ktos zdecydowal sie
nazwac je quick sort. Pesymistyczna zlozonosc tego algorytmu
wynosi O(n^2), teoretyczne optimum O(n lg n) osiaga tylko
w przypadku srednim. Algorytm ten jest wiec taki sobie. :-)
Dlatego wlasnie lubie heapsorta

Ma jedna wade - w praktyce wychodzi gorzej niz quick sort.
No i program dwa razy dluzszy :-)

Jeszcze o jednym panowie zapominacie - jak danych jest malo,
to nieoptymalne algorytmy O(n^2) okazuja sie szybsze
niz O(nlogn)

J.


========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Thu, 8 May 2003 01:40:16 +0200



J.F. wrote:

Ma jedna wade - w praktyce wychodzi gorzej niz quick sort.

To zalezy od implementacji, ale w ogolnym przypadku masz
racje. Zaleta jest taka, ze najgorszy przypadek nie rozni sie
wlasciwie od najlepszego, co daje bardzo cenna wlasciwosc,
umozliwiajaca dotrzymanie rezimu czasu rzeczywistego.
Quick sort bedzie dzialal ile chce, pomiedzy O(n), a O(n^2),
do tego dobrze wiadomo, jak skonstruowac dane wejsciowe,
by uzyskac slow sort. :-)

No i program dwa razy dluzszy :-)

Ale za to nawet sam pomysl jest prawie w asemblerze
-- przesuniecia i sumowania. :-) W quicksorcie sa jakies
"wymyslne" procedury dzielace itp., a tu tylko skakanie
po tablicy. BTW, dwa razy dluzszy? Na ile pamietam
"optycznie" quicksorta napisanego w C, to dlugosc byla
porownywalna z heapsortem.

Jeszcze o jednym panowie zapominacie - jak danych jest malo,
to nieoptymalne algorytmy O(n^2) okazuja sie szybsze
niz O(nlogn)

Nie zapominamy, wspominalem o tym w poscie do Waldka.
Ale jak sie czlowiek pyta o pomysly, to mozna mu przedstawic
kilka ciekawych alternatyw -- bedzie mial problem osla. :-)
Ja bym to zrobil selection sortem, w czasie jak najbardziej
(c/2)*n^2 + O(n).

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Thu, 08 May 2003 22:14:21 +0200


On Thu, 8 May 2003 01:40:16 +0200, Piotr Wyderski wrote:
J.F. wrote:
Ma jedna wade - w praktyce wychodzi gorzej niz quick sort.

To zalezy od implementacji, ale w ogolnym przypadku masz racje.
Zaleta jest taka, ze najgorszy przypadek nie rozni sie
wlasciwie od najlepszego, co daje bardzo cenna wlasciwosc,

No bo tam najpierw wstepnie niejako sortujemy tablice w porzadku
odwrotnym. To musi trwac dwa razy dluzej :-)

umozliwiajaca dotrzymanie rezimu czasu rzeczywistego.
Quick sort bedzie dzialal ile chce, pomiedzy O(n), a O(n^2),
do tego dobrze wiadomo, jak skonstruowac dane wejsciowe,
by uzyskac slow sort. :-)

Ze slow to pol biedy - gorzej ze przy okazji wyleci z braku pamieci na
stosie. Ale np po serii rzeczywistych pomiarow trudno spodziewac sie
tego najgorszego przypadku :-)

J.


========
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: sortowanie liczb w 8051 (ASM)
Date: Fri, 9 May 2003 01:14:11 +0200



J.F. wrote:

Ze slow to pol biedy - gorzej ze przy okazji wyleci z braku pamieci na
stosie.

Istnieje wersja ograniczajaca zuzycie stosu do O(lg n). Polega
na tym, ze najpierw sortuje sie tablice majaca mniej elementow,
a dopiero pozniej wieksza, przy wykorzystaniu mechanizmu
rekursji ogonowej -- rekursja zmienia sie na iteracje, co nie
powoduje przydzialu nowego rekordu aktywacji na stosie.

Ale np po serii rzeczywistych pomiarow trudno spodziewac sie
tego najgorszego przypadku :-)

W rzeczywistosci fragmenty ciagu sa czesto posortowane, co bardzo
pomaga quicksortowi. Ale takie podejscie to proszenie sie o wypadek .
Zapewne wiesz, kiedy taki algorytm prawie na pewno _nie_zadziala. :-)

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: Waldemar Krzok <waldemar.krzok_at_nospam_ukbf.fu-berlin.de>
Subject: Re: sortowanie liczb w 8051 (ASM) [straszny OT]
Date: Wed, 07 May 2003 16:59:14 +0200




Piotr Wyderski:

w Cray XMP, ze względu na stronicowanie pamięci i pracę z przesuniętym
taktem, sortowanie stosowe na 16 stosach jest szybsze od

Dobra, dokoncze mysl: "[...] na poziomie algorytmicznym?" :-)
O roznicach w sposobie implementacji sortowania na roznych
architekturach maszyn rownoleglych cos tam mi wiadomo. ;-D

to 16 dlatego, że CRAY XMP miał 8 lub 16 banków pamięci pracujących z
przesuniętym taktem. Częstotliwość taktowania jednego banku wynosiła (o
ile mnie sclerosis nie myli) 16ns (albo 32ns). Przesuwając takt osiągało
się częstotliwość dostępu dla "przyjemnie" rozstawionych danych 2ns.

Robiłem na CRAYu moją pracę inżynierską. Było to w efekcie całkowanie
numeryczne w przestrzeni. Program chodził ponad 2 minuty CPU. A 2 minuty
to była wtedy masa krytyczna, amerykański DoD zakazał dostępu na
maszynie w systemie "prawie"-online dla programów potrzebujących więcej
niż 120 sekund CPU (bali się rozwalenia tajnych kodów ;-)) i mój program
chodził wsadowo nocą. Wziąłem się za optymalizację i po odwróceniu kilku
pętli potrzebował 2 sekund!

Waldek


========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Michał Wojtków" <michallo4_at_nospam_wp.pl>
Subject: Odp: sortowanie liczb w 8051 (ASM)
Date: Tue, 6 May 2003 20:16:08 +0200


Osobiscie nie, ale robilem to na PC.
Najprostsza metoda, lecz troche wolna to metoda bombelkowa,
Polega na porównywaniu 2 zmiennych i przestawiania,
myślę za na `51 bedzie to tak samo działać- ale tu głowy nie dam
A tak z ciekawosci o ile zmiennych i jakie typu chcesz porownywac?
Pozdrawiam Michał



========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Wed, 07 May 2003 00:30:45 +0200


On Tue, 6 May 2003 20:16:08 +0200, Michał Wojtków wrote:
Osobiscie nie, ale robilem to na PC.
Najprostsza metoda, lecz troche wolna to metoda bombelkowa,
Polega na porównywaniu 2 zmiennych i przestawiania,
myślę za na `51 bedzie to tak samo działać- ale tu głowy nie dam
A tak z ciekawosci o ile zmiennych i jakie typu chcesz porownywac?

Pamieci tam duzo nie ma, to bedzie dzialac szybko :-)
W praktyce ciut lepiej sie sprawuje "insertion sort".

J.


========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!news.gazeta.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "BRT" <bartosz.rossa_at_nospam_gazeta.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Wed, 7 May 2003 00:56:04 +0200



Użytkownik "J.F." <jfox_at_nospam_poczta.onet.pl> napisał w wiadomości
news:468gbvsk6djkidm2k1arf1j5r05ustss28_at_nospam_4ax.com...
On Tue, 6 May 2003 20:16:08 +0200, Michał Wojtków wrote:
Osobiscie nie, ale robilem to na PC.
Najprostsza metoda, lecz troche wolna to metoda bombelkowa,
Polega na porównywaniu 2 zmiennych i przestawiania,
myślę za na `51 bedzie to tak samo działać- ale tu głowy nie dam
A tak z ciekawosci o ile zmiennych i jakie typu chcesz porownywac?

Pamieci tam duzo nie ma, to bedzie dzialac szybko :-)
W praktyce ciut lepiej sie sprawuje "insertion sort".

J.

A jesteś w stanie jakiś przykład podać na tego typu rozwiązanie?

Pozdr. BRT



--
Serwis Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Wed, 7 May 2003 13:55:39 +0200


J.F. wrote:

Pamieci tam duzo nie ma, to bedzie dzialac szybko :-)
W praktyce ciut lepiej sie sprawuje "insertion sort".

To do list, tablice lepiej selection sortem.

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Wed, 07 May 2003 23:42:59 +0200


On Wed, 7 May 2003 13:55:39 +0200, Piotr Wyderski wrote:
J.F. wrote:
Pamieci tam duzo nie ma, to bedzie dzialac szybko :-)
W praktyce ciut lepiej sie sprawuje "insertion sort".

To do list, tablice lepiej selection sortem.

No wlasnie nie, z tablicami tez sobie radzi dobrze.

J.


========
Path: news-archive.icm.edu.pl!news.rmf.pl!news.ipartners.pl!newsfeed.gazeta.pl!news.atman.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Thu, 8 May 2003 01:10:54 +0200



J.F. wrote:

No wlasnie nie, z tablicami tez sobie radzi dobrze.

W jakim sensie dobrze, tzn. ze w ogole dziala? ;-)
Insertion potrzebuje wydajnego kodu wstawiajacego
nowy element miedzy dwa istniejace elementy, o co
w przypadku tablicy cokolwiek trudno. Selection
nie ma tego problemu.

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_at_nospam_poczta.onet.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Thu, 08 May 2003 22:14:22 +0200


On Thu, 8 May 2003 01:10:54 +0200, Piotr Wyderski wrote:
J.F. wrote:
No wlasnie nie, z tablicami tez sobie radzi dobrze.

W jakim sensie dobrze, tzn. ze w ogole dziala? ;-)
Insertion potrzebuje wydajnego kodu wstawiajacego
nowy element miedzy dwa istniejace elementy, o co
w przypadku tablicy cokolwiek trudno. Selection nie ma tego problemu.

tu tez nie ma problemu.

temp=a[i] ; j=i-1 ;

while j>0 && a[j]>temp
{
a[j+1]=a[j] ;
j-- ;
}

masz od razu przeszukiwanie i wstawianie.

J.


========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai

Poprzedni Następny
Wiadomość
Spis treści
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: Odp: sortowanie liczb w 8051 (ASM)
Date: Fri, 9 May 2003 00:52:31 +0200



J.F. wrote:

temp=a[i] ; j=i-1 ;

while j>0 && a[j]>temp
{
a[j+1]=a[j] ;
j-- ;
}

Zabraklo takiej linijki:

a[j+1] = temp;

bo gubisz jeden element. :-)

tu tez nie ma problemu.

Alez jest, w tym while masz wlasnie przesuwanie elementow, aby
w razie potrzeby zrobic miejsce nowemu elementowi. W selection
sort masz tylko tyle wymian, ile rzeczywiscie potrzeba, co w przypadku
liczb 4-bajtowych na mikrokontrolerku 8-bitowym moze byc istotne.
Zaleta insertion sortu jest taka, ze w wielu przypadkach pozwala uniknac
zbednych iteracji, co moze sie przydac w srednim, "praktycznym"
przypadku. Z kolei w najgorszym wykonuje znacznie wiecej wymian,
niz potrzeba. W najgorszym przypadku selection sort potrzebuje
n^2/2 porownan i n wymian; insertion potrzebuje n^2/2 porownan
i n^2/2 wymian. W praktyce to cholera wie, co bedzie lepsze. :-)
Insertion bedzie za duzo zmienial, a selection bedzie uparcie mielil
niepotrzebne petle. Chyba tylko testy pokaza, co sie _w tym
konkretnym przypadku_ na _konkretnym procesorze_ bardziej
oplaca -- suwac elementy (drogie), czy bawic sie indeksami
(bardzo tanie, ale czasami wiecej, niz potrzeba) . :-)

masz od razu przeszukiwanie i wstawianie.

To co przedstawiles to klasyczna implementacja insertion sortu.
Wez sobie ciag posortowany "od konca" i zobacz, co sie dzieje
w selection, a co w insertion sorcie -- zobacz, co sie przesuwa.

Pozdrawiam
Piotr Wyderski



========
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai