IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Können Computer alphabetisch sortieren?



Können Computer alphabetisch sortieren?

Computer sind in der Lage grosse Mengen an Daten sortiert aufzulisten, aber irgendwie stimmt die Reihenfolge nicht immer ganz. Warum denn nur?


Autor: Patrick Faes (dreamer)
Datum: 03-07-2007, 20:12:00
Referenzen: siehe Text
Schwierigkeit: none
Ansichten: 7584x
Rating: 8 (2x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]




Seien es nun Wörterbücher, Telefonbücher oder Betriebsresultate: Daten sind für den Menschen nur brauchbar wenn diese strukturiert und übersichtlich sind. In den meisten Fällen bedeutet dies dass die Daten alphabetisch sortiert sein müssen. Telefonbücher sind heutzutage aber derart umfangreich dass mühsame Handarbeit nicht länger praktikabel ist. Daher entwickelt man Computerprogramme die uns diese Arbeit abnehmen. Nur leider ist dies auch nicht immer Fehlerfrei.

Nehmen wir z.B. mal folgender Vergleich. Sie sehen hier zwei Reihen an Daten: die Erste enthält numerische Werte, die Zweite dagegen beinhaltet Texte.


Reihe 1: numerische Werte

Reihe 2: Texte

23

von Saarbrücken

76

Köln

5

ausländisch

55

Anwalt

101

Microsoft

2

kalt

Wenn wir diese Daten sortieren, sehen diese Reihen so aus:


Reihe 1: numerische Werte

Reihe 2: Texte

2

Anwalt

5

Microsoft

23

Köln

55

ausländisch

76

kalt

101

von Saarbrücken

Und schon sind die Daten sortiert, oder... warte mal: die Texte sind doch nicht korrekt alphabetisch sortiert, die Zahlen aber schon! Woran liegt das? Um diese Frage beantworten zu können, muss man zuerst verstehen wie ein Computer Daten speichert.

Im Grunde kennt ein Computer nur zwei Dinge: "ja" und "nein", jeweils repräsentiert durch die Bit-Werte 1, bzw. 0. Damit kann ein Computer nur wenig anfangen. Deshalb setzen die Daten sich zusammen aus mehreren Bits die zusammengehören, so genannte Bit-Patronen. Ein Prozessor sendet alle Bit-Daten die zusammengehören nacheinander und der Empfänger (ein anderer Prozessor also) setzt diese Daten dann wieder zusammen. Dafür verwendet es die so genannten Binärzahlen.

Eine Binärzahl sieht z.B. so aus: 1011. Was das sein soll? Ist ganz einfach: jedes Bit repräsentiert einen sich bei jeder Stufe verdoppelten nummerischen Wert. Das letzte Zeichen (von rechts nach links) steht für den Wert "1". Wenn das Bit 1 (also "ja") ist, dann muss beim Endresultat schonmal 1 dazugezählt werden. Weiter gehts dann mit dem doppelten jeweils doppelten Wert des vorherigen Wertes. Das sind dann also (von links nach rechts, ab der zweiten Position aus gesehen) 2, 4 und 8.

Im unseren Beispiel ergibt das also folgendes:


8

4

2

1

1

0

1

1

Unser Resultat ist also 8 + 2 + 1 = 11. Mit 4 Bits kann man also alle Werte von 0 bis 15 erstellen, mit 5 Bits sind es dann alle Werte von 0 bis 31, usw.

Nun kann ein Computer seine Daten also speichern und diese auf Diskette, über ein Netzwerk oder sogar das Internet an einem anderen Computer weitergeben. Aber wie soll denn jetzt dieser andere Computer wissen was diese Bitfolgen zu bedeuten haben? Um dieses Problem zu lösen wurde in den 60-er Jahren des letzten Jahrhunderts ein Standardcode entwickelt der Bitfolgen enthält für Buchstaben die im amerikanischen Alphabet üblich sind: die American Standard Code for Information Interchange (ASCII, amerikanischer Standardcode für Informationsaustausch).

Entwickelt wurde eine Tabelle die insgesamt 128 verschiedene Zeichen enthält, 95 davon sind sichtbar (Buchstaben, Zahlen und einige Lesezeichen), die restlichen 33 sind unsichtbar. Gewönlich handelt es sich dabei um Zeichen die dazu dienten Text zu strukturieren, wie z.B. Zeilenumbrüche und "Ende des Textes"-Markierungen. Meistens sind sie jedoch veraltet und finden keine Verwendung mehr. Mit dieser Tabelle konnte jeden Wert von 0 bis 127 einen einzelnen Buchstaben o.ä. zugewiesen werden. Es sorgte also für eine Relation zwischen einer digitalen Bitpatrone und Symbolen einer menschlichen Sprache. Es ermöglichte Computern "Zeichen-orientierte" Daten zu verarbeiten und zu speichern.

Anmerkung: inzwischen kamen mehrere Ergänzungen hinzu und wurde auch schon der Unicode eingeführt, der viele Zeichen von Fremdsprachen beinhaltet.

Jetzt fragen Sie sich vielleicht was dies alles mit dem Sortieren von Texten zu tun hat. Nun, da ein Computer diese Textdaten als Bitpatronen speichert und diese in numerischen Werten umrechnet, wird er diese auch so sortieren. Und dann hängt das Resultat davon ab welche numerische Werte den einzelnen Buchstaben zugeteilt wurden. Die Großbuchstaben "A" bis "Z" haben die Werte 65 bis einschließlich 90, die Kleinbuchstaben "a" bis "z" dagegen 97 bis einschließlich 122. Daraus folgt dass ein großes "K" vom Wert 75 repräsentiert wird und ein kleines "b" vom Wert 98, wodurch Wörter die mit "K" anfangen vor Wörter mit "b" einsortiert werden.

Stellt sich ja nur die Frage wie so ein Sortierverfahren auf einem Computer abläuft. Der primitivste Sortieralgoritmus ist wohl der so genannte "Bubble Sort". Dabei wird der Computer eine Reihe von Daten immer wieder durchlaufen und einzelne Daten, die noch nicht in einer korrekten alphabetischen Reihenfolge stehen, vom Platz tauschen. Es vergleicht also immer Element A mit Element B und wird sie, fals Element B vor Element A kommen soll, von Platz tauschen. Dies geht so weiter bis der Computer zum Schluss kommt dass alle Elemente in einer richtigen Reihenfolge stehen. Aber wie schon gesagt, richtet ein Computer sich dabei an numerischen Werten die ein Buchstaben o.ä. Repräsentieren, nicht am eigentlichen Alphabet.

Um jetzt ein Programm zu entwerfen dass die Element korrekt sortieren kann, muss man halt nur verstehen wie ein Computer entscheidet welches Element zuerst kommen soll. Es nimmt dabei halt nur den ersten Buchstaben beider Elemente und vergleicht diese. So z.B. kommt "Gregor" vor "Patrick". Bei einem gleichen Anfangsbuchstaben, wird der Computer sich immer weiter von links nach rechts durcharbeiten bis er unterschiedliche Buchstaben findet die sich in den jeweiligen Wörtern an gleicher Stelle befinden. So kommt z.B. "klein" vor "kurz", da die jeweiligen Buchstaben die sich in beiden Wörtern an zweiter Stelle befinden ("l" und "u") eine verschiedene Stelle im Alphabet haben.

Daten die es zu sortieren gibt, können aber auch andere Zeichen als nur Buchstaben enthalten: Zahlen und Lesezeichen zum Biespiel. Zudem gibt es noch das vorher angesprochene Problem mit Klein- und Großbuchstaben. Auch Umlaute könnten zu Problemen führen. Der Grund dafür liegt darin dass Umlaute im Amerikanischen Alphabet nicht vorkommen und daher auch nicht in der anfänglichen Spezifikation von ACII aufgenommen wurden. Zwar wurden Buchstaben mit Umlaute nachträglich hinzugefügt, doch befinden sie sich nicht mehr in einer korrekten alphabetischen Reihenfolge.

Gleich folgen Anregungen dazu wie diese sich dennoch korrekt sortieren lassen. Unten gibt's noch ein Beispielprogramm das dies demonstriert (erfordert Javascript). Zuerst aber noch eine kurze Erklärung wie ein derartiges Programm zu realisieren ist.

Das Programm verwendet den sogenannten "Bubble Sort"-Algorithmus. Dieser durchläuft alle einzelne Texte u.ä. in einer Liste. Dabei wird das aktuelle Element jeweils mit dem nächsten verglichen. Wenn das Programm zum Schluss kommt dass das aktuelle Element nach dem nächsten kommen soll, so tauscht es die Plätze beider Elemente. Nachdem alle Elemente in einer Liste durchlaufen wurden, fängt das Programm wieder von vorne an, bis es zum Schluss kommt dass alle Elemente in der Liste in ihrer richtigen Reihenfolge stehen. Dabei orientiert sich das Programm immer am Platz den das Zeichen z.B. in der ASCII-Tabelle einnimmt.

Um jetzt Lesezeichen, Umlaute, usw. bei der Sortierung einbeziehen zu können, gehen Sie wie folgt vor: Sie lesen alle zu sortierene Elemente ein und kopieren diese dann in einer zweiten Liste. Die Elemente in der zweiten Liste bearbeiten Sie dann so, dass diese korrekt (bzw. nach den eigenen Wünschen) sortiert werden können. Dann wenden Sie den Sortieralgoritmus so an, dass die Elemente aus der zweiten Liste sortiert werden, und zugleichen die Elemente aus der ersten Liste analog sortiert werden. Im Klartext: wenn in der zweiten Liste Elemente A und B vom Platz tauschen, so geschieht dies auch mit den Elementen aus der ersten Liste die sich an den jeweiligen Stellen befinden.

Beim Sortiervorgang können folgende Probleme auftreten:


Kleinbuchstaben werden immer nach den Großbuchstaben einsortiert

Dieses Problem wurde vorher schon angesprochen. So z.B. wird "klein" immer nach "Groß" einsortiert, obwohl der Buchstabe "g" im Alphabet vor dem Buchstaben "k" kommt. Dies kann sehr einfach gelöst werden, indem die Großbuchstaben jeweils in Kleinbuchstaben umgewandelt werden.


Leerstellen verdrängen andere Buchstaben

Ein besonderes Problem ergibt sich bei Texte, bzw. Begriffe die Leerstellen enthalten. Es kann z.B. vorkommen dass die Begriffe "Äpfel aus Deutschland" und "Apfelsaft" sortiert werden müssen. Die Leerstelle ist das erste Zeichen in der ASCII-Tabelle und wird deshalb immer vor alle andere Zeichen einsortiert.

Das Resultat eines Sortiervorgangs währe in diesem Fall:

  1. Äpfel aus Deutschland

  2. Apfalsaft

Die Frage ist hierbei jedoch, ob man lieber hat dass der erstfolgende Buchstabe des nächsten Wortes beachtet wird, anstatt die Leerstelle. Das Resultat währe dann:

  1. Apfalsaft

  2. Äpfel aus Deutschland

Um diesen Effekt zu bekommen, müssen die Leerstellen einfach nur gelöscht werden. Es ist jedoch Geschmacksache welches zuerst kommen sollte.


Zahlen werden alphabetisch sortiert?

Wenn eine Liste sowohl Wörter als Zahlen enthält die sortiert werden müssen, fällt auf dass die Zahlen nicht richtig sortiert werden.

Folgendes Beispiel:


Unsortiert

Sortiert (alphabetisch)

67

355

355

67

Internet

9

9

Internet

Tür

Tür

Die Zahlen werden nicht korrekt (das heißt numerisch) sortiert. Das liegt daran dass ein Computer die Daten als Text einliest. Diese werden dann genauso sortiert wie Texte: alphabetisch nach Zeichen, von links nach rechts, nach deren Wert in der ASCII-Tabelle. Deshalb kommt 355 vor 67, weil die 3 vor die 6 kommt.

Dann müssen Sie testen ob sich ein Element in einer zu sortierenen Liste in eine Zahl umwandeln lässt und dies gegebenenfalls auch tun. Die Zahlen sollen dann in einer separaten Liste gespeichert werden. Die Liste mit den Zahlen und die Liste mit den Texten werden dann einzeln sortiert und nachher wieder zusammengefügt.

Die separate Liste dient dazu die Zahlen komplett von den anderen Elementen zu trennen. Texte werden auch sortiert je nach den numerischen Wert den der erste Buchstabe in der ASCII-Tabelle hat. Dann würde ein A (mit dem Wert 65) z.B. zwischen den numerischen Werten 40 und 101 einsortiert, was na nicht der Sinn der Sache ist.

Umlaute

In der anfänglichen Spezifikation der ASCII-Tabelle wurden Buchstaben mit Umlaut nicht aufgenommen, da diese nicht im Amerikanischen Alphabet vorkommen. Sie wurden aber nachträglich hinzugefügt. Diese wurden aber - warscheinlich um kompatibel zu bestehende Dokumenten zu bleiben - am Ende der Tabelle hinzugefügt. Dies hat zufolge dass ein "ö" nach "z" einsortiert wird. Um dieses Problem zu beheben, müssen alle Buchstaben mit Umlaut umgesezt werden in ihren Pendant ohne Umlaut.


Sonderzeichen

Möglich ist auch dass Texte Sonderzeichen wie z.B. Lesezeichen enthalten. Auch diese sind aufgelistet in der ASCII-Tabelle. Dies kann z.B. bei Englische Filmtitel wie "Bram Stoker's Dracula" vorkommen. Diese können in der zweiten Liste am Besten einfach gelöscht werden.


Hier noch das Live-Beispiel:

Tippen jeweils pro Zeile ein Begriff (Text, einzelnes Wort, Zahl, usw.) ein und wählen Sie dann die Sortierungsoptionen unten aus.


: Schriftgrößen beachten
: Leerstellen beachten
: Zahlen als solche interpretieren
: Umlaute beachten
: Sonderzeichen beachten
: Aufsteigend sortieren
: Absteigend sortieren

Weiterführende Links: Der Bubble-Sort-Algorithmus
Die ASCII-Tabelle


IsMirWurscht
Rookie
Beitrag vom:
30-08-2007, 21:19:26

Hi,
super Seite aber versuche einmal Widerstandswerte zu sortieren
1k
10k
9k9
100k

Hast Du dafür eine Lösung ?

-----------------------------------------------------


dreamer
Expert
Beitrag vom:
13-07-2007, 23:10:56

@paedubucher: im Nachhinein war "sichtbar/unsichtbar" wohl nicht die richtige Wortwahl, da ein Zeilenumbruch ja irgendwie schon "sichtbar" ist.

-----------------------------------------------------


no_comment
Professonial
Beitrag vom:
04-07-2007, 17:27:02

sehr interessanter Artikel!

-----------------------------------------------------
Es gibt nur 3 natürliche Feinde des Programmierers: Tageslicht, frische Luft und das unerträgliche Gebrüll der Vögel -- http://pc-intern.com http://straightvisions.com


paedubucher
Professonial
Beitrag vom:
03-07-2007, 19:55:08

sichtbar/unsichtbar

Du verwendest in deinem Text an gewissen Stellen die Begriffe "sichtbare Zeichen" und "unsichtbare Zeichen". Gebräuchlicher ist da die Unterscheidung in "druckbare" und "nicht druckbare" Zeichen. Aber nur ein Detail...

-----------------------------------------------------


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04506
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06243
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1142
Comments: 0