Sortierung
|
Sortierung |
Als Sortierung bezeichne ich .... sowohl der Vorgang als auch das Ergebnis eines Auslesens und Ordnens. Das zugrundeliegende Verb sortieren wurde im 16. Jahrhundert in der Bedeutung „in [Güte]klassen einteilen, auslesen, sondern, ordnen“ aus dem gleichbedeutenden italienischen sortire entlehnt, das wiederum auf das lateinische sortiri „[er]losen, auswählen“ zurückgeht. Verwandte Begriffe sind Sorte und Sortiment.[1] Sortiert werden materielle Güter, Daten und Informationen. Sortieren ist auch eine andere Bezeichnung für die Vollprüfung im Qualitätsmanagement. Streng genommen bezeichnet das Sortieren einen anderen Vorgang als das Ordnen, da beim Sortieren gleichartige Objekte zusammengenommen bzw. unterschiedliche getrennt werden (z. B. Äpfel und Birnen), während beim Ordnen eine Reihenfolge (z. B. Datum, Alphabet) zwischen unterschiedlichen Objekten zugrundegelegt wird. Üblicherweise werden beide Vorgänge miteinander verbunden, so dass beim „Sortieren“ nach Größe zugleich eine entsprechende Ordnung der unterschiedlichen Größen hergestellt wird. Ergebnisse eines Sortiervorgangs können Listen und Verzeichnisse sein. In der Informationsverarbeitung werden häufig Namen, Nummern und ähnliche Werte geordnet, wofür die Informatik verschiedene Sortierverfahren kennt. Bei einer alphabetischen Sortierung werden Zeichenketten entsprechend der Reihenfolge der Buchstaben im Alphabet angeordnet. Topologische Sortierung bezeichnet eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind. Mechanische, chemische oder physikalische Sortierverfahren zum Trennen von Stoffgemischen werden auch als Trennverfahren bezeichnet. Beim Sortieren von Dokumentenablagen spricht man von einer kaufmännischen Heftung, wenn das jeweils neueste Dokument oben, also über den älteren Dokumenten, einsortiert wird. Wird das jeweils neueste Dokument unten (hinten) einsortiert, so spricht man von Amtsheftung. Das Sortieren bewerteter Objekte kann zu einer Rangordnung (Ranking) führen. Währungen.
[1] transitiv: etwas nach Art, Größe, Farbe ordnen [2] übertragen, auch reflexiv: seine Gedanken sammeln und sich auf eine Situation einstellen ========================================== Zur Suche springen Die alphabetische Sortierung ist eine Sortierung, nach der Zeichenketten nach der Reihenfolge der Buchstaben im Alphabet angeordnet werden. Die herkömmliche Sortierung wird auch als initialalphabetische Sortierung bezeichnet, da die Ordnung der einzelnen Buchstaben in Schriftrichtung ermittelt wird. Während für die Buchstaben des Alphabets üblicherweise die allgemein anerkannte Reihenfolge benutzt wird, gibt es für die Sortierung von Besonderheiten wie Sonderzeichen, diakritischen Zeichen, Leerzeichen, Groß- und Kleinschreibung, Bindestrichen sowie Ziffern unterschiedliche Regeln und Normen. Inhaltsverzeichnis [Verbergen] 1 Grundprinzip 2 Geschichte 3 Sortierregeln nach Sprachen 3.1 Deutsche Sprache 3.1.1 Einsortierungsregeln für weitere Buchstaben 3.1.2 Deutschland 3.1.3 Österreich 3.1.4 Beispiel für deutschsprachige Sortierungen 3.2 Dänische und norwegische Sprache 3.3 Finnische und schwedische Sprache 3.4 Isländische Sprache 3.5 Estnische Sprache 3.6 Albanische Sprache 3.7 Andere Sprachen 4 Computersysteme 5 Rückläufige Sortierung 6 Siehe auch 7 Weblinks 8 Einzelnachweise ↑ Grundprinzip[Bearbeiten] Um bei zwei gegebenen Zeichenketten zu entscheiden, welche in der (initial)alphabetischen Sortierung zuerst kommt, werden die Zeichenketten, beginnend vom ersten Zeichen, zeichenweise verglichen. Die erste Zeichenposition, an denen sich die beiden Zeichenketten unterscheiden, entscheidet die Reihenfolge: Die Zeichenkette, deren Zeichen an dieser Position weiter vorne im Alphabet steht, kommt zuerst. So kommt beispielsweise „elektrisch“ vor „fertig“ (e vor f) und „Fahrrad“ vor „Fahrstuhl“ (r vor s). Wenn eine Zeichenkette kürzer als die andere ist und gleich dem Anfang der anderen, kann diese Regel nicht angewandt werden. Dann wird üblicherweise die kürzere Zeichenkette zuerst sortiert. So kommt beispielsweise „Fahrrad“ vor „Fahrradkette“. Für den Umgang mit Satzzeichen, Sonderzeichen und Groß- und Kleinschreibung gibt es verschiedene Regeln; siehe dazu Abschnitt Sortierregeln nach Sprachen. Die alphabetische Sortierung ist die Vorlage für das mathematische Konzept der lexikographischen Ordnung. Umgekehrt ist die alphabetische Sortierung selber eine lexikographische Ordnung, mit der Reihenfolge der Buchstaben im Alphabet als zugrundeliegender linearer Ordnung. ↑ Geschichte[Bearbeiten] Marcus Verrius Flaccus (* um 10 v. Chr.) ordnete als Erster ein lateinisches Wörterbuch alphabetisch an. Die Suda aus der 2. Hälfte des 10. Jahrhunderts ist die erste alphabetisch angeordnete byzantinische Enzyklopädie. Der Liber de proprietatibus rerum des Bartholomaeus Anglicus aus dem 13. Jahrhundert ist ebenfalls alphabetisch geordnet und wird oft als ein Vorläufer der Enzyklopädie angesehen. Das Prinzip, die Schriftzeichen überhaupt in einer bestimmten Abfolge anzuordnen, ist schon über dreitausend Jahre alt; siehe Ugaritische Schrift und allgemein Geschichte des Alphabets. ↑ Sortierregeln nach Sprachen[Bearbeiten] ↑ Deutsche Sprache[Bearbeiten] Dieser Artikel oder Absatz stellt die Situation in Deutschland und Österreich dar. Bitte hilf uns dabei, die Situation in anderen Staaten zu schildern. ↑ Einsortierungsregeln für weitere Buchstaben[Bearbeiten] Das deutsche Alphabet ergänzt das moderne lateinische Alphabet um die Umlaute Ä, Ö und Ü sowie den Buchstaben ß. Diese zusätzlichen Buchstaben können auf vier Arten einsortiert werden: 1.Ignorieren der Umlautpunkte. Müll wird wie Mull sortiert. 2.Gleichordnung von Grundbuchstaben, Doppelbuchstaben und Umlaut, wenn Doppelbuchstabe wie Umlaut gesprochen wird. Mull wird wie Muell oder Müll sortiert. Duell dagegen zwischen Duden und Dugast. 3.Auflösung des Umlauts. Müll wird wie Muell vor Muffe einsortiert. 4.Separierung als selbstständiger Buchstabe. 1.Einordnung hinter dem Grundbuchstaben. Müll steht zwischen Muzin und Münze. Später folgt Myalgie. 2.Einordnung am Ende des Alphabets. Müll steht hinter Mythos. Für alle sonstigen (fremdsprachigen) diakritischen Zeichen gilt im deutschsprachigen Raum, dass sie einheitlich weggelassen werden; so auch alle Akzente, Tilde, Makron: é und e, ç und c, ñ und n, č und c, ō und o sind gleich. ↑ Deutschland[Bearbeiten] DIN 5007 Bereich Schriftverkehr Titel Ordnen von Schriftzeichenfolgen Teile Teil 1: Allgemeine Regeln für die Aufbereitung (ABC-Regeln) Teil 2: Ansetzungsregeln für die alphabetische Ordnung von Namen Letzte Ausgabe Teil 1: 2005-08 Teil 2: 1996-05 Klassifikation 01.140.20 DIN 31638 Bereich Schriftverkehr Titel Bibliographische Ordnungsregeln Letzte Ausgabe August 1994 Klassifikation 01.140.20 Die deutsche Norm DIN 5007-1 beschreibt unter dem Titel „Ordnen von Schriftzeichenfolgen (ABC-Regeln)“ das Sortieren. DIN 5007 Variante 1 (für Wörter verwendet, etwa in Lexika; Abschnitt 6.1.1.4.1) ä und a sind gleich ö und o sind gleich ü und u sind gleich ß und ss sind gleich DIN 5007 Variante 2 (spezielle Sortierung für Namenslisten, etwa in Telefonbüchern; Abschnitt 6.1.1.4.2) ä und ae sind gleich ö und oe sind gleich ü und ue sind gleich ß und ss sind gleich Dies berücksichtigt, dass bei Eigennamen unterschiedliche Schreibweisen möglich sind, während Begriffe in einem Lexikon oder Wörterbuch nur unter genau einer Schreibung einzutragen sind. Dagegen kann nicht erschlossen werden, ob jemand nun Moeller oder Möller heißt. Dies gilt vor allem für deutschsprachige Einzelpersonen, Institutionen und Ortsnamen. Personennamen werden in Deutschland häufig (z. B. in Telefonbüchern) in der folgenden Art und Weise alphabetisch sortiert: Zuerst werden die Einträge nach Nachnamen sortiert, wobei akademische Grade wie „Prof.“, „Dr.“ und Namenszusätze wie „von“, „vor“, „am“, „zum“ weggelassen werden. Dabei ist zu beachten, dass Namenszusätze auch aus mehreren Wörtern bestehen können, wie etwa bei „von der Lippe“. Bei identischen Nachnamen wird anschließend nach eventuell vorhandenen Namenszusätzen alphabetisch sortiert, wobei Personennamen ohne Namenszusätze immer zuerst aufgeführt werden. Stimmen auch die Namenszusätze überein (oder sind keine vorhanden), wird als letztes anhand des Vornamens alphabetisch sortiert. Diese Art der Sortierung ist in den bibliographischen Ordnungsregeln DIN 31638 geregelt. =============================================0000000 springen Dieser Artikel behandelt Sortierverfahren in der Informatik. Zu Sortierverfahren in der Verfahrenstechnik siehe Technisches Sortierverfahren. Unter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist („kleiner-gleich“), z. B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen. Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten bezüglich der Zeitkomplexität (Anzahl der nötigen Operationen) sowie der Platzkomplexität (zusätzlich zum Eingabe-Array benötigter weiterer Speicherplatz). Die Komplexität eines Algorithmus wird üblicherweise in der Landau-Notation dargestellt (s. u. Ausdrücke wie Θ ( n ⋅ log ( n ) ) {\displaystyle \Theta (n\cdot \log(n))} {\displaystyle \Theta (n\cdot \log(n))}). Die Zeitkomplexität hängt bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bei günstigster „Vorsortierung“), Average Case (Normalfall) und Worst Case (schlechtester Fall ~ die Werte sind „maximal ungünstig vorgeordnet“). Häufig sind zusätzliche Faktoren zu beachten, die Einfluss auf Zeit- oder Platzkomplexität haben, zum Beispiel langsamer Zugriff auf extern liegende Daten, begrenzte Größe des Arbeitsspeichers oder ähnliches. Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren. Ist beispielsweise die Mitarbeiterliste einer Firma nach Nachname geordnet und wird anschließend nach Alter (in Jahren) sortiert, so bleibt die (Nachnamen-)Reihenfolge unter gleichaltrigen Mitarbeitern bei einem stabilen Sortierverfahren bestehen. Zudem unterscheidet man zwischen Sortierverfahren, die in-place (auch in situ) arbeiten, d. h. der zusätzliche Speicherbedarf ist unabhängig von der Anzahl der zu sortierenden Elemente (also konstant und meist gering), und solchen, bei denen er abhängig ist (out-of-place oder ex situ). Und man unterscheidet auch zwischen natürlichen Sortierverfahren, die bei vorsortierten Daten schneller arbeiten als bei unsortierten Daten, und solchen, die es nicht tun. Algorithmen, bei denen der Kontrollfluss von den Daten abhängt, nennt man adaptiv und dementsprechend Sortierverfahren, die nicht von den Eingabedaten abhängen, nicht-adaptiv. Nicht-adaptive Algorithmen sind demnach besonders interessant für Hardware-Implementierungen. Manuelles Sortieren (etwa von Karteikarten) sowie elektro-mechanische Sortierverfahren (z. B. für Lochkarten) entsprechen meist einem der hier beschriebenen softwarebasierten Sortierverfahren, oder Mischtypen. ============================== Ein technisches Sortierverfahren ist ein physikalischer Unterscheidungs- und Ordnungsprozess (im Gegensatz zu theoretischen Sortierverfahrens in der Informatik). Beispiele für technische Sortierverfahren sind das Sieben, das Aussondern magnetischer Bestandteile bei der maschinellen Mülltrennung mittels starker Magnete oder die Farbtrennung beim Glas-Recycling. Sortier-Kriterium kann jede messbare physikalische Eigenschaft einer Objektmenge sein, wie beispielsweise Größe, Magnetismus, Leitfähigkeit, Farbe. Inhaltsverzeichnis [Verbergen] 1 Mechanisches Trennverfahren 1.1 Klassieren 2 Siehe auch 3 Literatur ↑ Mechanisches Trennverfahren[Bearbeiten] Unter mechanischen Trennverfahren versteht man das Trennen von Mischungen unterschiedlicher Eigenschaften voneinander oder aus einem Trägermedium heraus, und zwar mit mechanischen Methoden. Mögliche Verfahren zur Trennung von Stoffen/ Objekten mit unterschiedlicher Größe oder Dichte sind: das Sieben Trennverfahren für Stoffe aus einem Trägermedium: Das Filtrieren nutzt ein Filtermittel zum Abscheiden von Stoffen aus einem Fluidstrom. Ein Beispiel hierfür ist der Luftfilter in Kraftfahrzeugen. Im großtechnischen Einsatz werden unter anderem Filterpressen eingesetzt. Das Sedimentieren nutzt die Wirkung der Schwerkraft, um Mischungen zu trennen. Teilchen mit höherer Dichte sinken zum Boden des Gefäßes, während Teilchen geringerer Dichte oben aufschwimmen (Flotation). Beim Flotieren treiben Stoffe geringerer Dichte in einem Fluid nach oben. Beim Zentrifugieren wird im Unterschied zum Sedimentieren nicht die Schwerkraft zum Trennen eingesetzt, sondern die Fliehkraft. Diese wird in einer sich drehenden Trommel, der Zentrifuge, erzeugt. Dieses Verfahren hat den Vorteil, dass durch schnellere Trennung als beim Sedimentieren ein höherer Durchsatz erreicht werden kann. Auch wirken beim Zentrifugieren höhere Beschleunigungskräfte. Der Fliehkraftabscheider lässt Teilchen mit größerer Dichte nach außen wandern. Fliehkraftabscheider werden im Apparatebau auch Zyklon genannt. Der Umlenkabscheider trennt Partikel aus einem Fluid durch die Trägheitskräfte an einer Umlenkung der Strömung. Das Medium folgt der Umlenkung, während schwerere Teilchen bestrebt sind, ihre geradlinige Bewegung beizubehalten. ↑ Klassieren[Bearbeiten] Beim Klassieren werden ansonsten gleichartige Teilchen aufgrund einer speziellen Eigenschaft abgesondert. Die Begriffe Separieren, Absondern und Sortieren werden teilweise synonym verwendet. Beim Sieben werden Teilchen nach ihrer Größe sortiert. Ebenso kann der Plansichter Teile verschiedener Größe voneinander separieren. Andere Verfahren des Sichtens, wie im Windsichter, trennen leichtere Teilchen von schwereren ab.