Sortowanie tablicy

[tdu]

Jak posortowac tablice tekstową DIM(100, 10), oczywiście w Basicu.
Proszę o pomoc.

Tablica zawiera100 słów o długości 10 znaków każde.

[trojacek]

Np. quick sortem:
https://pl.m.wikipedia.org/wiki/Sortowanie_szybkie

[steev]

A jeśli nie musi być bardzo szybko, a wolisz prosto, to sortowanie bąbelkowe

[steev]

BTW, jedno z moich 'oddly satisfying'... 

[tdu]

Ze są takie różne metody to wiem,
chodzi mi bardziej o jakąś przykładową implementacje w ZX Basicu

wystarczy jak posortuje alfabetycznie według pierwszego znaku

a czas wykonania nie powinien byc zbyt długi, sekunda, dwie...

[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".

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: [Zaznacz]

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
Czas: 2min 22sek

Sortowanie z wyborem - mniej zamian niż w bąbelkowym: tylko jedna na przebieg

Kod: [Zaznacz]

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
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: [Zaznacz]

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
Czas: 1min 14sek, jeszcze trochę szybciej.

Właściwie nie potrzebujesz sortowania tylko przepisanie jednej tablicy do drugiej na podstawie 1 litery każdego rekordu w 1 tablicy.
...

To jest odmiana sortowania z wyborem, tylko jest jedno kopiowanie a nie dwa. Myślę, że nie wyjdzie poniżej minuty...

[matofesi]

a czas wykonania nie powinien byc zbyt długi, sekunda, dwie...

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.

[tdu]

@smok.wawelski   też nad takim rozwiazaniem myślałem, tylko co będzie
jak w pierwszej tablicy będzie więcej stringów na tę samą literę, tutaj utknąłem,
ale może za słabo kombinowałem

@ZbyniuR   jak zadeklaruję  a$=DIM(100) to przy zapisie do tablicy zapisuje tylko pierwszy znak stringa
gdy zadeklaruję a$=DIM(100,10)  to zapisuje 10 znaków stringa,
tak mi wyszło z prób.

[matofesi]

No dobra... zrobiłem kawałek kodu, który robi brzydkiego bubble sorta w ASMie - sortowanie stu dziesięcioznakowych tekstóœ zajmuje ~sekundę.
Brzydkie, bo robi założenie, że zmienna do sortowania jest deklarowana jako pierwsza przed całą resztą bo liczy sobie adres na chama strzelając w obszar zmiennych. A do tego sam kod jest "odzwierciedleniem" wersji BASICowej.

W załączniku to co mi wyszło
- sort.bas ma w sobie dane, inicjalizację i wywołanie sortowania (oraz wyremowaną wersję sortowania w BASICu).
- sort.asm to właściwy kod sortujący - brzydki więc proszę się nie śmiać
- sort.tap to wersja do odpalenia

Skompilowana wersja się nie uruchamia sama - po RUN inicjuje tablicę, wciąga do niej dane, wyświetla READY i czeka na klawisz. Po wciśnięciu pisze SORTING i liczbę ramek odczytaną ze zmiennych systemowych po czym wykonuje kod sortujący a na koniec pisze DONE i aktualny stan liczby ramek - możemy policzyć  zgrubny czas w 1/50 sekundy. Po wciśnięciu dowolnego klawisza wyświetla posortowaną tablicę.

Cały "eksperyment" pokazuje, że nie specjalnie jest sens się szarpać BASICem - kod sortujący ma ciut ponad 100 bajtów więc nawet jakby go doszlifować żeby był "ładny" to nadal nie powinno być problemu, żeby go zmieścić gdzieś w pamięci.

I jeszcze raz - proszę się nie śmiać

[tdu]

Jak dla mnie, fajny kawalek kodu,
jak rozumiem, pobierana jest tablica z adresu
wskazywanego przez zmienną systemową z adresu 23627.

Czyli swoją tablicę muszę zadeklarować jako pierwszą, bo będzie ich kilka.
Po sortowaniu, można ją dalej obrabiać w basicu.

Ilość wierszy tablicy nie będzie stała, będzie się zmieniać w zależności od potrzeb max120, trzeba by to jakoś do kodu przekazać,
długość pojedynczego wiersza to 9 znaków,
litery będą tylko duże,
będą też liczby

[ZbyniuR]

Ludzie co wy macie z tymi bombelkami? Od zawsze wiadomo że to najwolniejsza metoda i powinno sie ją wykreślić z podręczników do programowania ze 30 lat temu. Wybierani proste jest ok dwa razy szybsze na tak krótkich tablicach, a im dłuższa tym większą ma przewagę nad bombelkami.

   Prawie ułożona tablica, np taka która po poprzednim sortowaniu dostała nową pozycję albo zmodyfikowano jedną z nich, powinna sie szybciej sortować niż taka kompletnie pomieszana.       

@tdu - Przyjmuję do wiadomości działanie DIM w Speccu.

   @Phonex -  A czy mierzyłeś kiedyś prędkość tej samej procedury z upchniętymi rozkazami na maks w linii, w porównaniu do tej która każdy rozkaz ma w osobnej linii?  Bo w CPC z pomiarów widać różnicę między czasem potrzebnym do przeskoczenia do następnego rozkazu oddzielonego dwukropkiem (co jest szybsze), niż do przeskoczenia do następnego rozkazu który jest w następnej linii. Dlatego nie przypadkiem upycham tyle rozkazów ile sie zmieści w linii.        

A wogóle to ten wątek zaczyna przypominać przysłowie, gdzie kucharek 6...

[matofesi]

@tdu Trzeba by kod przepisać tak, żeby sobie ROMem ładnie znajdował adres konkretnej zmiennej i dodać przekazywanie parametrów, choć w samych danych jest info o tym jak zmienna była zadeklarowana więc kod może sobie te informacje sam wyjąć. Do tego prawie na pewno dałoby się to zrobić tak, żeby kod był relokowalny... W weekend nie, ale po weekendzie mogę się temu przyjrzeć

@ZbyniuR Bombelki są łatwe do zrozumienia. A poza tym w BASICu przy zadanych na starcie parametrach nawet jak skrócisz czas wykonania o 90% to dalej nie mieścisz się w wymaganiach - schodzisz ze 120 do 12 sekund a miało być "sekunda, dwie". Przejście do ASMa załatwia kwestię czasu na tyle, że przyspieszenie zmianą algorytmu na bardziej skomplikowany/wydajny nie ma tu strategicznego znaczenia - sortując wg. założeń startowych kod robi to w ~sekundę.

A co do tego jak z ZX BASICU działa DIM... Tekstowy DIM z jednym parametrem deklaruje zmienną tekstową o zadanej długości - jeśli zrobisz DIM a$(5) a potem LET a$ = "123456" i PRINT a$ to w wyniku dostaniesz 12345. Jeśli zmienna tekstowa nie jest deklarowana ma rozmiar "dynamiczny". Tekstowy DIM z więcej niż jednym parametrem deklaruje tablicę tekstów o zadanej (ostatnim parametrem) długości. Nie da się zadeklarować tablicy tekstowej z dynamiczną długością tekstów.