AdminMod.de
https://www.adminmod.de/

Sortierfunktion für Namen aus einem Textfile
https://www.adminmod.de/viewtopic.php?t=3493
Seite 1 von 2

Autor:  Sir Drink a lot [ 04.07.2002, 17:44 ]
Betreff des Beitrags:  Sortierfunktion für Namen aus einem Textfile

Hallo Cracks!

Ich wollte mal wissen, wie man so eine Sortierung am Besten und vor allem am Effizientesten lößt.

Ich weiss, dass AM dafür nicht konzipiert wurde, aber ich will ja in Sachen Programmierung und vor allem im Aufbau eines Arrays was lernen.

So. Hier mal eine der uneffizientesten Möglichkeiten :oops:, die ich durch rumprobieren (und ASCII-Tabelle) rausbekommen habe:
Code:
#include <core>
#include <console>
#include <string>
#include <admin>
#include <adminlib>

#define MAX_ENTRIES 10

new TextFile[MAX_TEXT_LENGTH]="Namen.txt";

new Data[MAX_ENTRIES][MAX_DATA_LENGTH];
new Data1[MAX_ENTRIES][MAX_DATA_LENGTH];
new maxlines;

public loadDB(){
	
	new i;
	new iLine;

	iLine=filesize(TextFile);
	
	for(i=1;i<=iLine;i++){
		readfile(TextFile,Data[i],i,MAX_DATA_LENGTH);
	}
	say("Database wurde geladen");
	maxlines = i-1;
	return PLUGIN_CONTINUE;
}

public admin_test() {
	
	new Text[MAX_TEXT_LENGTH];
	new i;
	new j;
	new k;
	new x;
	new position=1;

	selfmessage("---------------------");
	selfmessage("Namen unsortiert:");
	for(i=1;i<=maxlines;i++){
		snprintf(Text,MAX_TEXT_LENGTH,"Position: %i --- Name: %s",i,Data[i]);
		selfmessage(Text);
	}
	selfmessage("---------------------");
	for(j=1;j<=maxlines;j++){			/*erster Name*/
		for(k=1;k<=maxlines;k++){		/*Namen zum Vergleich heranziehen*/
			for(x=0;x<=10;x++){		/*Stellenweiser Zeichen-Vergleich der beiden Namen auf bis max.10 Stellen*/
				if(Data[j][x]<Data[k][x]){
					break;
				}else if(Data[j][x]>Data[k][x]){
					position++;
					break;
				}	
			}
		}
		strcpy(Data1[position],Data[j],MAX_DATA_LENGTH);
		position=1;
	}
	selfmessage("Namen sortiert:");
	for(i=1;i<=maxlines;i++){
		snprintf(Text,MAX_TEXT_LENGTH,"Position: %i --- Name: %s",i,Data1[i]);
		selfmessage(Text);
	}
	selfmessage("---------------------");
	return PLUGIN_HANDLED;
}
public plugin_init() {
	plugin_registerinfo("Test-Data in 2-dim Array speichern","admin_test","1.0");
	plugin_registercmd("admin_test","admin_test",ACCESS_ALL,"admin_test: Wandelt unsortierte Data in sortierte Data");
	loadDB();
	return PLUGIN_CONTINUE;
}
In der Namen.txt stehen bei mir diese Namen:
Zacharias
Peter
Anton
Antoniette
Maria
Karl
Kai
Otto
Antonia

Bitte nicht gleich verprügeln, wenn der Code oben totaler Blödsinn ist. Aber er hat mir die Namen richtig sortiert.

Ich weiss natürlich, dass es eine ewige redundante Überprüfung ist, aber das würde ich ja gerne gelößt haben :-)

Die Anzahl der Namen in dem Textfile ist auf 10 Namen begrenzt. Erstmal. Braucht sowieso schon fast eine Sekunde auf meinem 1GHz Rechner, um die Liste zu sortieren. Naja, nicht ganz :-)

Autor:  Warhead [ 04.07.2002, 21:23 ]
Betreff des Beitrags: 

Also den Namensvergleich hättest Du nicht nochmal programmieren müssen, den bietet Dir strcmp schon an. Zur Sortierung gibts eigentlich nicht viel zu sagen, da gibs Standardalgorithmen (Quicksort, Hashtables, etc). Da sollte es auch für den uninformierten etwas im Kindernet drüber geben...

Autor:  frostschutz [ 04.07.2002, 22:43 ]
Betreff des Beitrags: 

Hachja, Small ist doch ne herrliche Sprache.

In meinem C-Derivat hätte mans da leichter:
Code:
sort_array(Namensliste, #'>);
Aber man muss es dem Programmierer ja schwer machen.


Ich hab mal schnell ne Quicksort-Implementierung für Small geschrieben. Ich hoffe, Small kommt wenigstens mit rekursiven Funktionen klar. Getestet habe ich den Code in keinster Weise. Nichtmal versucht zu compilieren. Ich weiß nicht genau, wie man in Small einer Funktion ein 2dimensionales Array referenziert übergibt, evtl. musst du da was anpassen, oder mach aus liste einfach ein globales Array.

Dein Aufruf muss so aussehen:
Zitat:
quicksort(liste, 0, liste_size, string_size) *** FALSCH, siehe unten

Wobei liste mit liste[liste_size][string_size] vereinbart ist.
Code:
quicksort(liste[][], min, max, string_size)
{
    new left, right;
    new compare[string_size];
    new temp[string_size];

    /* Abbruchkriterium */
    if(max > min)
    {
        /* Die Partition wird mit ihrem ersten Element verglichen */
        strcpy(compare, liste[min], string_size);

        left = min;
        right = max;

        /* Gesamte Partition durchgehen und anhand von 'compare'
           in 2 Teile aufteilen, wobei ein Teil unter und der
           andere Teil ueber 'compare' liegt */
        while(right >= left)
        {
            /* Position von Eintraegen links von compare unveraendert lassen */
            while( strcmp(liste[left], compare) <= 0 )
            {
                left++;
            }

            /* Position von Eintraegen rechts von compare unveraendert lassen */
            while( strcmp(liste[right], compare) == 1 )
            {
                right--;
            }

            if(left > right)
            {
                /* Holla. Wir sind fertig mit dieser Partition. */
                break;
            }

            /* Da ist was in falscher Reihenfolge -> austauschen */
            strcpy(temp, liste[left], string_size);
            strcpy(liste[left], liste[right], string_size);
            strcpy(liste[right], temp, string_size);

            left++;
            right--;

            /* Und weiter gehts... */
        }

        /* Schoen, wieder ne Partition fertig, die naechsten 2 bitte... */
        quicksort(liste, min, right, string_size);
        quicksort(liste, left, max, string_size);
    }
}
// EDIT: 04.07.02 23:57 Syntaxfehler im Code korrigiert
// EDIT: 05.07.02 00:00
Zitat:
Ach so, ich habe vergessen, daß Small gar keine dynamischen Arrays hat. (Mann, bin ich verwöhnt). Der obige Code geht davon aus, daß jedes Element der liste ein String ist, der Sortiert werden soll. Dein Array ist ja möglicherweise größer.

D.h. dein Aufruf muss dann wohl sowas wie
Code:
quicksort(liste, 0, num, string_size)
sein, wobei num die Nummer des letzten Strings in deinem Array ist und string_size nach wie vor die Größe der String-Arrays.
// EDIT 05.07.02 00:06
Zitat:
Sorry für die vielen EDIT's, ich bin wohl um diese Urzeit schon etwas zu unkonzentriert. Ich gehe in obigem Code natürlich davon aus, daß strcmp() bereits den Alphabetisch-Knickknack übernimmt, also strcmp("A","B") == -1, strcmp("B","A") == 1, usw.

Außerdem habe ich obigen Code jetzt nochmal geändert, weil mir da noch ein Fehlerchen aufgefallen ist... aber um ein bisschen selber basteln wirste wahrscheinlich nicht rumkommen.

Autor:  frostschutz [ 04.07.2002, 23:04 ]
Betreff des Beitrags: 

Ach ja, das beste wärs natürlich einfach das Textfile schon alphabetisch zu speichern. :lol: So ne Sortierfunktion bietet dir jeder bessere Texteditor. :wink:

Autor:  Sir Drink a lot [ 04.07.2002, 23:58 ]
Betreff des Beitrags: 

jo danke schonmal!

ich weiss natürlich, dass es jeder bessere Texteditor kann.
Ich will es ja einfach mal mit Small ausprobieren. :-)

Nun denn, dann will ich das mal mit strcmp verstehen und ausprobieren.

Autor:  daRope [ 05.07.2002, 09:39 ]
Betreff des Beitrags: 

Zitat:
Hachja, Small ist doch ne herrliche Sprache.

In meinem C-Derivat hätte mans da leichter:
Code:
sort_array(Namensliste, #'>);
Aber man muss es dem Programmierer ja schwer machen.
Und in meinem Linux Terminal muesste ich nur tippen:
Code:
sort dateiname
:roll:


Noch viel geiler ist aber die von mir selbst entwickelte Sprache Easy, wo jedes Programm aus nur einer Zeile besteht:
Code:
do_what_I_want()


Merke: auch unter der Haube von Maedchensprachen wird nur mit Wasser gekocht.

Autor:  Sir Drink a lot [ 05.07.2002, 19:55 ]
Betreff des Beitrags: 

Ich habe mich mal ein wenig schlau gemacht und Quicksort über Google im "Kindernet" gefunden.

Jetzt kommt natürlich mal wieder mein Unwissenheit über den Aufbau eines Arrays.

Ist es so, dass bei einem einem einfachen Array Data [MAX_DATA_LENGTH] 200 Nullen reserviert werden?

Wenn ich jetzt den String "Maria" habe und diesen in Data kopiere, wie sieht der Array dann aus?

So? : Data['M','a','r','i','a',0] (=>war die 0 die Terminierung?)
oder stehen da eben auch Zahlen drin? Sind dann 194 reservierte Stellen ungenutzt?

Bei dem Quicksort Beispiel, welches ich mir angeschaut habe, war eine Zahlen Reihe im Array a gespeichert. (0,1,5,8,7,9)

Um diese zu sortieren, wurde jetzt der Array in 2 Hälften geteilt. Linke und Rechte Seite. Diese beiden Seiten wurden getrennt sortiert und nachher wieder zusammenkopiert. Vorher noch überprüft ob rechts<links. Wenn kleiner , dann wurde links mit rechts vertauscht.
(Ich hoffe, so habe ich das richtig verstanden.)

Aber, ich habe ja eine Liste mit Namen. Daher hatte ich auch einen 2-dimensionalen Array gewählt, da ich denke, dass so nur eine Reihenfolge hinzubekommen ist.

Das Aufteilen der MAX_ENTRIES in Links und Rechts ist ok. Jetzt muss ich aber nicht MAX_ENTRIES sortieren, sondern den MAX_DATA_LENGTH, da ich ja bisher noch annehme, das dort die Strings drin stehen.

Tja, so siehts bisher in meinem kleinen Kopf aus. Ich hoffe, wenn ich das irgendwann mal mit den Arrays richtig raffe, dass ich dann auch einen Bitweisen-Vergleich nutzen kann, ohne immer das rechenaufwendigere strcmp zu nutzen. Denn wer mal meine Codes angesehen hat weiß, wieviel Rechenpower die verbrauchen, da sie schlecht gecodet sind.

Auch wenn es Euch sehr viel Mühe macht, habt ein Herz und versucht es mir zu erklären.

Gruß,
SDal

Autor:  Warhead [ 05.07.2002, 21:06 ]
Betreff des Beitrags: 

Zitat:
So? : Data['M','a','r','i','a',0] (=>war die 0 die Terminierung?)
oder stehen da eben auch Zahlen drin? Sind dann 194 reservierte Stellen ungenutzt?
Sozusagen.
An das strcmp übergibst Du natürlich Data[x][] bzw. Data[x][0] und Data[y][] bzw. Data[y][0] (je nachdem was der Compiler akzeptiert).

Autor:  frostschutz [ 06.07.2002, 00:52 ]
Betreff des Beitrags: 

Zitat:
Jetzt kommt natürlich mal wieder mein Unwissenheit über den Aufbau eines Arrays.

Ist es so, dass bei einem einem einfachen Array Data [MAX_DATA_LENGTH] 200 Nullen reserviert werden?
Bei "new Data[MAX_DATA_LENGTH] = { 0, ... }" ist das sicher so. Ob Small standardmäßig alles mit 0 initialisiert, weiß ich nicht. Gut möglich, daß die Einträge auch irgendwelche "zufälligen" Werte haben - die Werte die der Speicher an der Adresse halt grad hatte.
Zitat:
Wenn ich jetzt den String "Maria" habe und diesen in Data kopiere, wie sieht der Array dann aus?

So? : Data['M','a','r','i','a',0] (=>war die 0 die Terminierung?)
oder stehen da eben auch Zahlen drin? Sind dann 194 reservierte Stellen ungenutzt?
Klar stehen da Zahlen drin. 'M', 'a', 'r', usw. sind ja alles zahlen. Das Array wird dadurch nicht kleiner, wenn du das meinst. D.h. 194 Stellen sind ungenutzt (die 0 ist ja genutzt, als Terminierung). Ab der 0 wird einfach nur der Rest des Arrays ignoriert, existiert aber noch, belegt Speicher.
Zitat:
Bei dem Quicksort Beispiel, welches ich mir angeschaut habe, war eine Zahlen Reihe im Array a gespeichert. (0,1,5,8,7,9)

Um diese zu sortieren, wurde jetzt der Array in 2 Hälften geteilt. Linke und Rechte Seite. Diese beiden Seiten wurden getrennt sortiert und nachher wieder zusammenkopiert. Vorher noch überprüft ob rechts<links. Wenn kleiner , dann wurde links mit rechts vertauscht.
(Ich hoffe, so habe ich das richtig verstanden.)
Getrennt und nacher zusammenkopiert stimmt nicht ganz. Die Funktion arbeitet Rekursiv, d.h. sie ruft sich selbst auf. Alle Instanzen der gleichen Funktionen arbeiten jedoch mit dem gleichen Array, d.h. da werden keine Arrayteile kopiert und wieder zusammengefügt oder so.

(*)
Das erste Element eines Teils dient als Vergleicher; alle anderen Elemente des Teils werden mit diesem verglichen und anhand des Ergebnisses in einen positiv und in einen negativ-Teil geschoben. (z.B. ist die Zahl größer (positiv) oder kleiner-gleich (negativ)). Dabei werden Elemente des Arrays miteinander vertauscht, bis der Vergleicher in der Mitte zwischen Positiv- und Negativ-Teil liegt und damit "sortiert" ist.

Positiv- und Negativ-Teil sind wieder Array-Teile. Bitte bei (*) weiterlesen um zu erfahren wie mit jedem einzelnen von diesen vorgegangen wird.

Das ganze Spiel hört erst auf, wenn ein Teil nur noch aus einem oder weniger Elementen besteht. Da jedes Element sortiert wurde (mit jedem Durchgang wird ja ein Element sortiert, siehe oben) ist das komplette Array sortiert.
Zitat:
Aber, ich habe ja eine Liste mit Namen. Daher hatte ich auch einen 2-dimensionalen Array gewählt, da ich denke, dass so nur eine Reihenfolge hinzubekommen ist.
Das ist ja richtig so. Dein Array ist also { "Anton", "Hubert", "Olaf", "Berta }.
Zitat:
Das Aufteilen der MAX_ENTRIES in Links und Rechts ist ok. Jetzt muss ich aber nicht MAX_ENTRIES sortieren, sondern den MAX_DATA_LENGTH, da ich ja bisher noch annehme, das dort die Strings drin stehen.
Moment. MAX_DATA_LENGTH ist doch die Länge deiner Strings, oder bin ich jetzt falsch? Die willst du doch nicht sortieren (also aus "Berta" "aBert" machen oder so). Du willst nur die Reihenfolge der Namen aendern, also MAX_ENTRIES, wobei du aufpassen musst - die Arraygröße ist statisch, d.h. nicht jedes Element deines Arrays muss ein String sein.
Code:
5 Strings in einem data[10][10]; - Array:
{
    {'A', 'n', 't', 'o', 'n', 0, 0, 0, 0, 0},
    {'B', 'e', 'r', 't', 'a', 0, 0, 0, 0, 0},
    {'C', 'r', 'i', 's', 't', 'o', 'f', 0, 0, 0},
    {'D', 'u', 0, 0, 0, 0, 0, 0, 0, 0},
    {'E', 'e', 'r', 'i', 'e', 0, 0, 0, 0, 0}, /* == "Eerie" */
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /* == "" */
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
}
Bei ner Sortierung würds dir da womöglich die "" - Strings nach vorne hauen.
Zitat:
Auch wenn es Euch sehr viel Mühe macht, habt ein Herz und versucht es mir zu erklären.
Quicksort kann man schlecht erklären, vielleicht bin ich auch schlecht im Erklären, es klingt immer so kompliziert. Am besten ist es wenn du dich mal mit einem kleinen Array (6 Elemente) an ein Blatt Papier setzt und es mit der Quicksort-Methodik im Kopf - auf Papier - durchsortierst.

Mein Code von oben sollte dir da weiterhelfen.

Autor:  Sir Drink a lot [ 06.07.2002, 08:38 ]
Betreff des Beitrags: 

Vielen Dank Leute !
Zitat:
Sir Drink a lot hat folgendes geschrieben::

Das Aufteilen der MAX_ENTRIES in Links und Rechts ist ok. Jetzt muss ich aber nicht MAX_ENTRIES sortieren, sondern den MAX_DATA_LENGTH, da ich ja bisher noch annehme, das dort die Strings drin stehen.


Moment. MAX_DATA_LENGTH ist doch die Länge deiner Strings, oder bin ich jetzt falsch? Die willst du doch nicht sortieren (also aus "Berta" "aBert" machen oder so). Du willst nur die Reihenfolge der Namen aendern, also MAX_ENTRIES, wobei du aufpassen musst - die Arraygröße ist statisch, d.h. nicht jedes Element deines Arrays muss ein String sein.
Ups. Korrekt. Mein Fehler. Da lag noch ein Gedankenfehler vor.

So. Ich hoffe jetzt, dass ich es verstanden habe. War ja doch alles so ungefähr, wie ich es mir in meiner "Phantasie" ausgemalt habe.

Ich danke Euch nochmal für Eure Mühe!

Gruß,
SDal

Autor:  Sir Drink a lot [ 06.07.2002, 12:20 ]
Betreff des Beitrags: 

Um das Thema zum "Aufbau eines Arrays" fortzuführen, kommen wir auf die Funktionsweise von strcmp.

1.Werde mit strcmp die kompletten zu vergleichenden Arrays durchgegangen?

2.Wenn ja, dann heißt das aber, wenn wir Name[MAX_NAME_LENGTH] und Name1[MAX_DATA_LENGTH] haben, dass wenn in beiden z.B. Maria drinsteht, es keine Übereinstimmung gibt, da die Arrays eine unterschiedliche Größe haben. Oder gehe ich da von einer falschen Annahme aus?

3.Andere Sache. Ich habe ein "normalen" Array, in dem z.B. nur Ja oder Nein stehen kann.

Ist es jetzt, wenn man von 1. ausgehen kann, immer sinnvoll, einen "bit-weisen"(heißt das so? Ich meine damit einzelne Positionen, nicht das Bier :-)) Vergleich heranzuziehen, als den aufwendigen strcmp?

Also anstatt If(strcmp(Data,"Ja")==0), einfach so if(Data[0]=='J') ?

4. Würde ein if(Data[0]==74) zum selben Ergebniss führen, da laut ASCII-Tabelle die Zahl 74 für den Großbuchstaben J steht?

Ich finde es richtig gut, dass ihr meine Fragen beantwortet (auch wenn sie für Euch trivial erscheinen), da es sicher viele ' Copy und Paste "Programmierer" ' auch interessiert und es vielleicht dazu führt, das effizientere Codes geschrieben werden.

Gruß,
SDal

Autor:  Warhead [ 06.07.2002, 12:27 ]
Betreff des Beitrags: 

1. Hä?

2. Der Vergleich geht immer bis zur terminierenden Null. Die Größe der Arrays ist irrelevant. Steht also in beiden dasselbe drin, wird Gleichheit durch strcmp festgestellt.

3. Ja.

Autor:  Sir Drink a lot [ 06.07.2002, 12:30 ]
Betreff des Beitrags: 

Ich habe gerade noch einen Punkt 4 drangehängt...ist der auch ok?

Autor:  Sir Drink a lot [ 06.07.2002, 12:33 ]
Betreff des Beitrags: 

zu 1. meinte ich es so: es wird mit strcmp der komplette Array "bitweise" komplett durchgegangen und mit dem anderen verglichen. Aber durch Deine Bestätigung durch Punkt 2. ist das ja dann so :-)

Autor:  Warhead [ 06.07.2002, 12:38 ]
Betreff des Beitrags: 

Nein? Ja?

new ArrayName[5];
new ArrayName2[10];

strcpy(ArrayName, "Mary", 5);
strcpy(ArrayName2, "Mary", 10);

Inhalt:

ArrayName={ 'M', 'a', 'r', 'y', 0};
ArrayName2={ 'M', 'a', 'r', 'y', 0, x, x, x, x, x};

x=unbekannt

Klar?

Autor:  Warhead [ 06.07.2002, 12:40 ]
Betreff des Beitrags: 

4. Wenn die 74 ein J ist, Ja.

Autor:  Sir Drink a lot [ 06.07.2002, 12:44 ]
Betreff des Beitrags: 

Gut...Klar!

Damit sind meine Fragen vorläufig geklärt.

Autor:  daRope [ 06.07.2002, 12:44 ]
Betreff des Beitrags: 

4. Ja.

Ausserdem glaube ich, dass Du nicht "bitweise", sondern "elementweise" meinst.

Autor:  Sir Drink a lot [ 06.07.2002, 12:47 ]
Betreff des Beitrags: 

ok. Elementweise!

Da sieht man ja, dass ich die fachliche Terminologie nicht beherrsche. Thx! Wieder was gelernt!

Autor:  frostschutz [ 06.07.2002, 12:56 ]
Betreff des Beitrags: 

Zitat:
3.Andere Sache. Ich habe ein "normalen" Array, in dem z.B. nur Ja oder Nein stehen kann.

Also anstatt If(strcmp(Data,"Ja")==0), einfach so if(Data[0]=='J') ?
Bedingt ja. Ein == Vergleich ist weniger aufwendig als ein strcmp-Funktionsaufruf, hinter dem noch eine Schleife etc. pp. steht.

Allerdings reicht if(Data[0] == 'J') nicht immer aus. Diese Bedingung ist zwar wahr, wenn Data == "Ja", aber genauso wahr bei "Jehova" oder "Jein" und nicht wahr bei "ja".

D.h. wenn anderweitig gesichert ist, daß Data nur die Werte "Ja" und "Nein" haben kann, dann ist es ok. Sonst womöglich nicht.

Seite 1 von 2 Alle Zeiten sind UTC+01:00
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/