ZX Spectrum > PROGRAMOWANIE
Sortowanie tablicy
ZbyniuR:
Jeśli w podanym przez ciebie przykładzie DIM(100,10) ta dziesiątka to odpowiednik długości słowa to nie jest to potrzebne. Jedno-wymiarowa tablica a w zasadzie to lista ci wystarczy. A jeśli to tekst to nazwa zmiennej przed nawiasem potrzebuje dolarka.
Z różnych metod polecam metodę przez wybieranie proste. Jest równie krótka jak bąbelkowa, a znacznie od niej szybsza. Wprawdzie metody Shell i Quick są jeszcze szybsze ale dopiero gdy tablica ma kilkaset pozycji, a obie mają niemal 3 razy dłuższy program.
Wygląda to mniej więcej tak:
10 DIM a$(100)
20 FOR n=x TO 2 STEP-1:p$="":FOR m=1 TO n:IF a$(m)>p$ THEN p$=a$(m):p=m
30 NEXT m:t$=a$(n):a$(n)=a$(p):a$(p)=t$:NEXT n
To jest wersja na Amstrada, i mam nadzieję że na Spectrum nie trzeba nic zmieniać. Jakby co to ktoś bystrzejszy poprawi. :)
A jak chcesz sobie namieszać w głowie innymi metodami sortowania to w czasopiśmie Komputer 7/88 na stronie 17 jest o tym niezły artykuł. Jego skany można znaleźć na archive.org albo na atarionline.pl w dziale czasopisma. :)
Nawiasem mówiąc na czym ma polegać ta metoda "bąbelkowa poprawiona" w tym artykule to nie wiem, bo jest dłuższa i wolniejsza od tej "niepoprawionej". :D
PS.: Wątpię aby Basic posortował taką tablicę w sekundę.
PS2.: Szkoda że ten GIF jest taki szybki, można oczopląsu dostać, mogłyby sie kolorki zmieniać w tych które skończyły, łatwiej byłoby je zauważyć.
smok.wawelski:
Właściwie nie potrzebujesz sortowania tylko przepisanie jednej tablicy do drugiej na podstawie 1 litery każdego rekordu w 1 tablicy.
Zaczynasz od "a" (zakładam, że wszystko jest z małej litery) i wybierasz wszystkie rekordy z 1 tablicy zaczynające się na tę literę i umieszczasz w tablicy drugiej.
Stworzysz w ten sposób drugą tablicę w maksymalnie 100 x 24 operacjach. Jeśli przepiszesz 100 rekordów zanim dojdziesz do "z" to możesz zakończyć szukanie (np. pierwsza tablica ma słowa maksymalnie do "c").
PS. Sam jestem ciekaw ile czasu będzie potrzebne do posortowania 100 rekordów, postaram się napisać ten program w BASICu i wkleję rozwiązanie.
Phonex:
Nie ma szans na posortowanie 100-elementowej tablicy w Basicu w 2 sekundy. Pewnie udało by się w asemblerze.
Sortowanie bąbelkowe z flagą (z flagą wykonuje mniej przebiegów - przestaje gdy nie było zamian):
--- Kod: ---10 FOR l=100 TO 1 STEP -1
20 LET flag=0
30 FOR k=1 TO l-1
40 IF a$(k,1)>a$(k+1,1) THEN LET p$=a$(k): LET a$(k)=a$(k+1): KET a$(k+1)=p$: LET flag=1
50 NEXT k
60 IF flag THEN NEXT l
--- Koniec kodu ---
Czas: 2min 22sek
Sortowanie z wyborem - mniej zamian niż w bąbelkowym: tylko jedna na przebieg
--- Kod: ---10 FOR l=1 TO 99
20 LET min=l
30 FOR k=l+1 TO 100
40 IF a$(k,1)<a$(min,1) THEN LET min=k
50 NEXT k
60 LET p$=a$(l): LET a$(l)=a$(min): LET a$(min)=p$
70 NEXT l
--- Koniec kodu ---
Czas: 1min 30sek, prawie dwa razy szybciej
A sortowanie z wyborem w wersji ZbyniuR: porównywanie do łańcucha p$, a nie elementu tablicy
--- Kod: ---10 FOR l=1 TO 99
20 LET min=l: LET p$=a$(min)
30 FOR k=l+1 TO 100
40 IF a$(k,1)<p$ THEN LET min=k: LET p$=a$(min)
50 NEXT k
60 LET a$(min)=a$(l): LET a$(l)=p$
70 NEXT l
--- Koniec kodu ---
Czas: 1min 14sek, jeszcze trochę szybciej.
--- Cytat: smok.wawelski w 2023.04.14, 12:00:03 ---Właściwie nie potrzebujesz sortowania tylko przepisanie jednej tablicy do drugiej na podstawie 1 litery każdego rekordu w 1 tablicy.
...
--- Koniec cytatu ---
To jest odmiana sortowania z wyborem, tylko jest jedno kopiowanie a nie dwa. Myślę, że nie wyjdzie poniżej minuty...
matofesi:
--- Cytat: tdu w 2023.04.13, 19:20:29 ---a czas wykonania nie powinien byc zbyt długi, sekunda, dwie...
--- Koniec cytatu ---
Nie żeby coś, ale 100 tekstów po 10 znaków w BASICu?... Na Spectrum?... "sekunda, dwie"? ;)
Bubble sort na losowo wygenerowanych 100 stringach sortuje trochę ponad dwie minuty. Żeby było zabawniej ten sam algorytm ograniczony warunkiem do pierwszego znaku robi to samo 20 sekund dłużej - porównanie pierwszych znaków dwóch zmiennych wymaga dodatkowych nakładu na obcięcie tych znaków.
Nie wiem na ile inne algorytmy zrobią to szybciej albo na ile da się zoptymalizować, ale mam wrażenie, że bez ASMa to możesz zapomnieć o kilkusekundowych czasach.
tdu:
Wystarczyłaby tablica posortowanych indeksów, może to dałoby się szybciej.
Nawigacja
[#] Następna strona
Idź do wersji pełnej