Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

Strings sortieren - geeigneter Sortieralgorithmus?

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC.
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
ALWIM



Anmeldungsdatum: 08.08.2006
Beiträge: 934
Wohnort: Niederbayern

BeitragVerfasst am: 08.07.2017, 01:15    Titel: Strings sortieren - geeigneter Sortieralgorithmus? Antworten mit Zitat

Wie sortiere ich Strings am schnellsten? Ich habe 12 Strings die gleichzeitig sortiert werden sollen. Jeder der 12 Strings hat ca. 3000 Werte. Die 12 Strings werden 3-4 mal sortiert. Welcher Algorithmus eignet sich da am besten fürs sortieren?

String sieht wie folgt aus:
Code:
Namen(i, j)


Die gefundenen Sortieralgorithmen brauchen entweder zu lang, oder sind nicht für Strings geeignet.

Mein Gedankengang:
Code:
FOR i = 1 TO 3000
   FOR j = 1 TO 30
      SWAP Namen(j,1),Namen(j+1,1)
      SWAP Namen(j,2),Namen(j+1,2)
      SWAP Namen(j,3),Namen(j+1,3)
      ...
   NEXT
NEXT

obiger Code braucht zu lange! Wenn ich jetzt 10 Minuten zum sortieren brauche, ist das auch nicht grad Sinn und Zweck der Sache!

Hat jemand eine Idee?

Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Sebastian
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 5870
Wohnort: Deutschland

BeitragVerfasst am: 08.07.2017, 01:38    Titel: Antworten mit Zitat

Hi ALWIM!

Für so eine geringe Datenmenge sollte bei einigermaßen aktueller Hardware selbst ein BubbleSort allenfalls Sekunden brauchen. lächeln

Was du beschreibst, ist ein zweidimensionales Array, also quasi eine Tabelle mit Zeilen und Spalten. Vermutlich möchtest du, dass Zeilen als Ganzes sortiert werden nach einer bestimmten Spalte, richtig?

Dein vorgeschlagener Algorithmus wird dazu nicht funktionieren: Der betrachtet den Inhalt der Spalten gar nicht, d.h. ob "Zitrone" vor "Apfel" steht oder umgekehrt. Sondern du vertauscht immer nur ein Element mit dem jeweils nächsten, egal, ob die Reihenfolge passt oder nicht. Und das 3000x hintereinander immer wieder von vorne.

Viele Grüße!
Sebastian
_________________
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
Sebastian
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 5870
Wohnort: Deutschland

BeitragVerfasst am: 08.07.2017, 02:10    Titel: 2-dimensionales Array mit BubbleSort sortieren Antworten mit Zitat

Hi ALWIM,

hier mal ein einfaches Beispiel zum Nachverfolgen. Das 2-dimensionale Array wird nach der ersten Spalte (Name) sortiert.
Code:
Dim Tabelle(1 To 5, 1 To 4) As String

Tabelle(1,1) = "Thorben"
Tabelle(1,2) = "Ufologe"
Tabelle(1,3) = "Bonn"
Tabelle(1,4) = "35"

Tabelle(2,1) = "Mandy"
Tabelle(2,2) = "Spiritistin"
Tabelle(2,3) = "Erfurt"
Tabelle(2,4) = "42"

Tabelle(3,1) = "Siggi"
Tabelle(3,2) = "Guru"
Tabelle(3,3) = "Rosenheim"
Tabelle(3,4) = "72"

Tabelle(4,1) = "Walburga"
Tabelle(4,2) = "Schlagersaengerin"
Tabelle(4,3) = "Duisburg"
Tabelle(4,4) = "58"

Tabelle(5,1) = "Aalfred"
Tabelle(5,2) = "Krabbenpuler"
Tabelle(5,3) = "Kiel"
Tabelle(5,4) = "29"

Print "Name                  | Beruf                  | Wohnort          | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
    Print Using "\                   \ | \                    \ | \              \ | \    \"; _
                 Tabelle(i,1);            Tabelle(i,2);           Tabelle(i,3);      Tabelle(i,4)
Next i

Print
Print "Jetzt wird sortiert!"
Print
' BubbleSort
For j As Integer = UBound(Tabelle,1) To LBound(Tabelle,1)+1 Step -1
    For i As Integer = LBound(Tabelle,1) To j-1
        If( Tabelle(i,1) > Tabelle(i+1,1) ) Then
            For spalte As Integer = LBound(Tabelle,2) To UBound(Tabelle,2)
                Swap Tabelle(i,spalte), Tabelle(i+1, spalte)
            Next spalte
        End If
    Next i
Next j

Print "Name                  | Beruf                  | Wohnort          | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
    Print Using "\                   \ | \                    \ | \              \ | \    \"; _
                 Tabelle(i,1);            Tabelle(i,2);           Tabelle(i,3);      Tabelle(i,4)
Next i

GetKey
End


Und so sähe das für 3000 Datensätze aus. Auf meinem mittlerweile über 7 Jahre alten PC dauert das Sortieren mit BubbleSort übrigens 0,27 Sekunden... zwinkern
Code:
Dim Tabelle(1 To 3000, 1 To 4) As String

' Zufallseingaben generieren
Randomize Timer
Dim Zufallsname As String
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
    For j As Integer = 1 To 3
        Zufallsname = ""
        For zeichen As Integer = 1 To (5 + Int(RND*15))
            If( zeichen = 1 ) Then
                Zufallsname += Chr(65+Int(RND*26))
            Else
                Zufallsname += Chr(97+Int(RND*26))
            End If
        Next zeichen
        Tabelle(i,j) = Zufallsname
    Next j
    Tabelle(i,4) = Ltrim(Str(18+Int(RND*80)))  'Zufaelliges Alter
Next i

' Zufallsdaten anzeigen
Print "Name                  | Beruf                  | Wohnort          | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
    Print Using "\                   \ | \                    \ | \              \ | \    \"; _
                 Tabelle(i,1);            Tabelle(i,2);           Tabelle(i,3);      Tabelle(i,4)
Next i

Print

Print Ltrim(Str(UBound(Tabelle,1) - LBound(Tabelle,1) + 1)) + " zufaellige Datensaetze generiert."
Print "Bitte beliebige Taste druecken zum Sortieren und fuer Zeitmessung!"
Print
Print
GetKey

Dim Startzeit As Double
Dim Endzeit As Double

Startzeit = TIMER

' Sortieren mit BubbleSort
For j As Integer = UBound(Tabelle,1) To LBound(Tabelle,1)+1 Step -1
    For i As Integer = LBound(Tabelle,1) To j-1
        If( Tabelle(i,1) > Tabelle(i+1,1) ) Then
            For spalte As Integer = LBound(Tabelle,2) To UBound(Tabelle,2)
                Swap Tabelle(i,spalte), Tabelle(i+1, spalte)
            Next spalte
        End If
    Next i
Next j

Endzeit = TIMER

' Wie lange hat's gedauert?
Print
Print "Das Sortieren hat "; Ltrim(Str(Endzeit-Startzeit)); " Sekunden gedauert."
Print
Print "Beliebige Taste druecken, um sortierte Ergebnisse anzeigen zu lassen."
Print
GetKey
Print

' Sortierte Ergebnisse anzeigen
Print "Name                  | Beruf                  | Wohnort          | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
    Print Using "\                   \ | \                    \ | \              \ | \    \"; _
                 Tabelle(i,1);            Tabelle(i,2);           Tabelle(i,3);      Tabelle(i,4)
Next i

GetKey
End


Das Langsamste ist übrigens die Ausgabe der 3000 Zeilen auf dem Bildschirm. Das Sortieren ist Sekundenbruchteilen erledigt.

Viele Grüße!
Sebastian
_________________
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
ALWIM



Anmeldungsdatum: 08.08.2006
Beiträge: 934
Wohnort: Niederbayern

BeitragVerfasst am: 09.07.2017, 21:03    Titel: Antworten mit Zitat

Sebastian hat Folgendes geschrieben:
Hi ALWIM!

Für so eine geringe Datenmenge sollte bei einigermaßen aktueller Hardware selbst ein BubbleSort allenfalls Sekunden brauchen. lächeln

Was du beschreibst, ist ein zweidimensionales Array, also quasi eine Tabelle mit Zeilen und Spalten. Vermutlich möchtest du, dass Zeilen als Ganzes sortiert werden nach einer bestimmten Spalte, richtig?

Dein vorgeschlagener Algorithmus wird dazu nicht funktionieren: Der betrachtet den Inhalt der Spalten gar nicht, d.h. ob "Zitrone" vor "Apfel" steht oder umgekehrt. Sondern du vertauscht immer nur ein Element mit dem jeweils nächsten, egal, ob die Reihenfolge passt oder nicht. Und das 3000x hintereinander immer wieder von vorne.

Viele Grüße!
Sebastian
Die Sortierung funktioniert nun! Ich war bei meiner Idee schon am richtigen Weg. Hatte ihn nur nicht optimiert! Das was ich im Quellcode drin hatte, funktionierte auch, nur war das ganze etwas zu langsam! Jetzt ist die Sortierung schneller. Vielen herzlichen Dank für die Aufklärung!

Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2447
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 10.07.2017, 17:50    Titel: Antworten mit Zitat

Falls ein schöner Code ein Thema ist: Warum nicht mit TYPE eine Klasse erstellen mit den Tabellenfeldern als Attribute, danach einen eigenen "operator<" fürs Sortieren implementieren? Hier sonst ein Bespiel:
Code:
Type Person
   namen As String * 25
   beruf As String * 25
   wohnort As String * 20
   alter As Integer
   
   Declare Function toString()As String
End Type

Function Person.toString() As String
   Return namen + Space(25 - Len(namen + "")) + beruf + Space(25 - Len(beruf + "")) + wohnort + _
   Space(26 - Len(wohnort + "") - Len(Str(alter))) + Str(alter)
End Function

Operator>(p1 As Person, p2 As Person)As Integer
   ' Hier als Beispiel Wohnort als 1. Kriterium, danach der Name as Unterkriterium
   If p1.wohnort = p2.wohnort Then
      Return p1.namen > p2.namen
   Else
      Return p1.wohnort > p2.wohnort
   EndIf
End Operator

Sub Sortieren(p() As Person)
   Dim i As Integer, j As Integer
   For i = LBound(p) To UBound(p) - 1
      For j = i + 1 To UBound(p)
         If p(i) > p(j) Then
            Swap p(i), p(j)
         EndIf
      Next j
   Next i
End Sub

Dim p(...) As Person => {("Thorben", "Ufologe", "Bonn", 35), _
("Mandy", "Spiritistin", "Erfurt", 42), ("Siggi", "Guru", "Rosenheim", 72), _
("Walburga", !"Schlagers\132ngerin", "Duisburg", 58), ("Aalfred", "Krabbenpuler", "Kiel", 29), _
("Hannes", "Besenbinder", "Rosenheim", 55), ("Anton", "Billettentwerter", "Erfurt", 28)}

Dim i As Integer

ScreenRes 640, 480, 4
Width 80, 30

Print "Vor der Sortierung"
For i = LBound(p) To UBound(p)
   Print p(i).toString
Next i

Sortieren p()

Print
Print "Nach der Sortierung"
For i = LBound(p) To UBound(p)
   Print p(i).toString
Next i

Sleep

_________________
Teste die PC-Sicherheit mit www.sec-check.net
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
ALWIM



Anmeldungsdatum: 08.08.2006
Beiträge: 934
Wohnort: Niederbayern

BeitragVerfasst am: 11.07.2017, 20:12    Titel: Antworten mit Zitat

dreael hat Folgendes geschrieben:
Falls ein schöner Code ein Thema ist: Warum nicht mit TYPE eine Klasse erstellen mit den Tabellenfeldern als Attribute, danach einen eigenen "operator<" fürs Sortieren implementieren? Hier sonst ein Bespiel:
Code:
Type Person
   namen As String * 25
   beruf As String * 25
   wohnort As String * 20
   alter As Integer
   
   Declare Function toString()As String
End Type

Function Person.toString() As String
   Return namen + Space(25 - Len(namen + "")) + beruf + Space(25 - Len(beruf + "")) + wohnort + _
   Space(26 - Len(wohnort + "") - Len(Str(alter))) + Str(alter)
End Function

Operator>(p1 As Person, p2 As Person)As Integer
   ' Hier als Beispiel Wohnort als 1. Kriterium, danach der Name as Unterkriterium
   If p1.wohnort = p2.wohnort Then
      Return p1.namen > p2.namen
   Else
      Return p1.wohnort > p2.wohnort
   EndIf
End Operator

Sub Sortieren(p() As Person)
   Dim i As Integer, j As Integer
   For i = LBound(p) To UBound(p) - 1
      For j = i + 1 To UBound(p)
         If p(i) > p(j) Then
            Swap p(i), p(j)
         EndIf
      Next j
   Next i
End Sub

Dim p(...) As Person => {("Thorben", "Ufologe", "Bonn", 35), _
("Mandy", "Spiritistin", "Erfurt", 42), ("Siggi", "Guru", "Rosenheim", 72), _
("Walburga", !"Schlagers\132ngerin", "Duisburg", 58), ("Aalfred", "Krabbenpuler", "Kiel", 29), _
("Hannes", "Besenbinder", "Rosenheim", 55), ("Anton", "Billettentwerter", "Erfurt", 28)}

Dim i As Integer

ScreenRes 640, 480, 4
Width 80, 30

Print "Vor der Sortierung"
For i = LBound(p) To UBound(p)
   Print p(i).toString
Next i

Sortieren p()

Print
Print "Nach der Sortierung"
For i = LBound(p) To UBound(p)
   Print p(i).toString
Next i

Sleep
Schöner Code muss es nicht unbedingt sein. Es muss nur funktionieren! Und das tut es.

Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
St_W



Anmeldungsdatum: 22.07.2007
Beiträge: 887
Wohnort: Austria

BeitragVerfasst am: 11.07.2017, 21:14    Titel: Antworten mit Zitat

ALWIM hat Folgendes geschrieben:
Schöner Code muss es nicht unbedingt sein. Es muss nur funktionieren!
Also diese Einstellung würde ich nochmal überdenken verwundert
Es gibt eigentlich so gut wie keinen Grund unsauberen Code sauberem Code vorzuziehen, umgekehrt gibt es aber viele Gründe guten (schönen) Code zu schreiben.

Sünden in der Vergangenheit holen einen meist irgendwann wieder ein. Spätestens dann wirst du dir wünschen es gleich ordentlich gemacht zu haben.
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken)
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4148
Wohnort: ~/

BeitragVerfasst am: 12.07.2017, 16:40    Titel: Antworten mit Zitat

Und der große Vorteil an "schönem Code mit TYPE" ist, dass bei einem neuen Anwendungsbereich nur noch der Operator > korrekt angepasst werden muss, und schon funktioniert die Sortier-Routine für einen komplett anderen Datentyp.

(Bei mir ist dann nur das Problem, dass ich immer irgendwelche komischen Extrawünsche habe, wie das parallele Sortieren zweier Listen, wo sich aus Performance-Gründen das Zusammenkopieren zu einem UDT nicht lohnt, weshalb ich mein QuickSort letztendlich doch immer wieder neu anpasse lachen aber auch da ist das mit "schönen Code" sehr viel einfacher als bei "Code, der einfach nur funktioniert".)
_________________
Meine Großeltern waren als junge Menschen sehr modern - sie hatten schon damals in der Badewanne Email.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Sebastian
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 5870
Wohnort: Deutschland

BeitragVerfasst am: 13.07.2017, 15:49    Titel: TYPE Antworten mit Zitat

dreael, die Verwendung von UDTs ("TYPE") schlagen wir ALWIM quasi schon seit Jahren vor, aber mit wenig Erfolg. zwinkern Siehe z. B. https://forum.qbasic.at/viewtopic.php?p=108375#108375 oder https://forum.qbasic.at/viewtopic.php?p=108468#108468
_________________
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
ALWIM



Anmeldungsdatum: 08.08.2006
Beiträge: 934
Wohnort: Niederbayern

BeitragVerfasst am: 15.07.2017, 23:24    Titel: Re: TYPE Antworten mit Zitat

Sebastian hat Folgendes geschrieben:
dreael, die Verwendung von UDTs ("TYPE") schlagen wir ALWIM quasi schon seit Jahren vor, aber mit wenig Erfolg. zwinkern Siehe z. B. https://forum.qbasic.at/viewtopic.php?p=108375#108375 oder https://forum.qbasic.at/viewtopic.php?p=108468#108468
Auch wenn UDTs besser sind, so programmiere ich halt nicht! zwinkern Es geht ja anders auch, wie man sieht. Mein Programm funktioniert ja! Erfolgreich getestet bei einem Turnier.

Zitat:
Sünden in der Vergangenheit holen einen meist irgendwann wieder ein. Spätestens dann wirst du dir wünschen es gleich ordentlich gemacht zu haben.
Das habe ich bei meinem Programm schon gemerkt! Aber da hätte mir ein UDT auch nicht geholfen.

Zitat:
Also diese Einstellung würde ich nochmal überdenken
Werde ich vielleich mal tun. Aber im Moment, komme ich so damit klar!

Trotzdem vielen herzlichen Dank für die Hilfe!

Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2447
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 16.07.2017, 19:01    Titel: Re: TYPE Antworten mit Zitat

ALWIM hat Folgendes geschrieben:
Auch wenn UDTs besser sind, so programmiere ich halt nicht! ;) Es geht ja anders auch, wie man sieht. Mein Programm funktioniert ja! Erfolgreich getestet bei einem Turnier.

Das allesentscheidende Stichwort: Wartbarkeit!

Software Engineering ist nun einmal ein komplexer Prozess (aktuell lese ich auch wieder gerade ein iX-Sonderheft rund ums Thema agile Softwareentwicklung z.B. mit Scrum).

In der professionellen IT-Welt generiert nun einmal ein schlecht geschriebener Code sog. technische Schulden. Heisst ganz praktisch gesprochen: Steht ein Änderungswunsch im Raum, so rächt sich ein schlecht geschriebener Code später entsprechend als erheblicher (zeitlicher und finanzieller) Mehraufwand, weil im Extremfall ein komplettes Neuschreiben (Refactoring) nötig ist.

Fähige Softwarefirmen wenden deshalb beispielsweise den Code Review an, d.h. ein bewusst unvoreingenommener Software-Entwickler versucht den Code seines Kollegen zu verstehen und nachvollziehen. Ist dies nicht (mit vernünftigem Aufwand) möglich, dann sollte sich der ursprüngliche Entwickler ernsthaft einmal mit den Grundprinzipien von Clean Code auseinandersetzen.

Empfehlun von mir: Selbst im Hobbybereich ist es sinnvoll, sich mit der letztgenannten Thematik auch einmal etwas auseinanderzusetzen.
_________________
Teste die PC-Sicherheit mit www.sec-check.net
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 774
Wohnort: Ruhrpott

BeitragVerfasst am: 17.07.2017, 10:18    Titel: Antworten mit Zitat

dreael hat Folgendes geschrieben:
Fähige Softwarefirmen wenden deshalb beispielsweise den Code Review an, d.h. ein bewusst unvoreingenommener Software-Entwickler versucht den Code seines Kollegen zu verstehen und nachvollziehen. Ist dies nicht (mit vernünftigem Aufwand) möglich, dann sollte sich der ursprüngliche Entwickler ernsthaft einmal mit den Grundprinzipien von Clean Code auseinandersetzen.
Das könnten auch einige C - Programmierer gebrauchen, die ihren vollständig unkommentierten Quellcode auf 50 oder 60 undurchschaubar voneinander abhängige Minidateien verteilen. durchgeknallt (Wäre vielleicht mal ein lohnendes Projekt: Ein FB-Programm, das solche Abhängigkeiten übersichtlich in einer Baumstruktur darstellt...)

Und was ALWIM betrifft: Wenn man das Programmieren im Spaghetti - Stil gewohnt ist (und damit bisher ganz gut zurechtkam), erfordert die Einsicht in die Vorteile von UDTs -wie ich aus eigener Erfahrung weiss- einen gewissen Leidensdruck. Wenn man zum ersten Mal in einem selbstgeschriebenen Programm vollkommen den Überblick verloren hat, dann ist es soweit. Haben wir also noch etwas Geduld, das wird schon! grinsen

Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC. Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

 Impressum :: Datenschutz