Technopedia Center
PMB University Brochure
Faculty of Engineering and Computer Science
S1 Informatics S1 Information Systems S1 Information Technology S1 Computer Engineering S1 Electrical Engineering S1 Civil Engineering

faculty of Economics and Business
S1 Management S1 Accountancy

Faculty of Letters and Educational Sciences
S1 English literature S1 English language education S1 Mathematics education S1 Sports Education
teknopedia

teknopedia

teknopedia

teknopedia

teknopedia
  • Registerasi
  • Brosur UTI
  • Kip Scholarship Information
  • Performance
  1. Weltenzyklopädie
  2. Hybridsort – Wikipedia
Hybridsort – Wikipedia
aus Wikipedia, der freien Enzyklopädie

Hybridsort ist ein spezielles Sortierverfahren, das die Eigenschaften von Bucketsort mit anderen Sortierverfahren wie Heapsort oder Quicksort kombiniert. Die zu sortierenden Schlüssel werden nach dem Prinzip von Bucketsort aufgeteilt. Die so vorsortierten Elemente werden dann mit dem Heapsort-Algorithmus endgültig sortiert. Die durchsortierten Kübel werden dann aneinandergefügt.

Voraussetzung

[Bearbeiten | Quelltext bearbeiten]

Ähnlich wie bei Bucketsort muss die Anzahl der von den Sortierschlüsseln annehmbaren Werte endlich sein.

Prinzip

[Bearbeiten | Quelltext bearbeiten]

Die Elemente einer Liste werden entsprechend ihrer Schlüsseleigenschaft auf eine endliche Menge von Eimern verteilt. Die Schlüssel werden mit Hilfe des maximalen Schlüssels max {\displaystyle {\text{max}}} {\displaystyle {\text{max}}} auf das Intervall [ 0 ; 1 ] {\displaystyle [0;1]} {\displaystyle [0;1]} normiert. Durch die Anzahl der Körbe a {\displaystyle a} {\displaystyle a} werden die Grenzen in diesem Intervall definiert. Mit folgender Formel werden dann die Elemente auf die Körbe verteilt:

Index Korb = Schlüssel max ⋅ a {\displaystyle {\text{Index}}_{\text{Korb}}={\frac {\text{Schlüssel}}{\text{max}}}\cdot a} {\displaystyle {\text{Index}}_{\text{Korb}}={\frac {\text{Schlüssel}}{\text{max}}}\cdot a}

Die so verteilten Schlüssel werden innerhalb der Körbe mit Heapsort sortiert.

Die vor- und durchsortierten Körbe liefern aneinandergereiht die sortierte Liste.

Komplexität

[Bearbeiten | Quelltext bearbeiten]

Unter der Annahme, dass xi unabhängig und gleichverteilt ist, ergibt sich sowohl im best als auch im average case des Verfahrens eine Laufzeit von O ( n ) {\displaystyle {\mathcal {O}}(n)} {\displaystyle {\mathcal {O}}(n)}. Für den allgemeinen Fall ergibt sich jedoch eine deutlich schlechtere Laufzeit. Der worst case wird dominiert von der Laufzeit von Heapsort und ist damit O ( n ⋅ log ⁡ n ) {\displaystyle {\mathcal {O}}(n\cdot \log n)} {\displaystyle {\mathcal {O}}(n\cdot \log n)}.

Literatur

[Bearbeiten | Quelltext bearbeiten]
  • Torben Hagerup: Hybridsort revisited and parallelized. In: Information Processing Letters. Band 32, Nr. 1, 1989, S. 35–39, doi:10.1016/0020-0190(89)90066-5. 
  • Henk Meijer und Selim G. Akl: The design and analysis of a new hybrid sorting algorithm. In: Information Processing Letters. Band 10, Nr. 4,5, 1980, S. 213–218, doi:10.1016/0020-0190(80)90143-X. 
Abgerufen von „https://de.teknopedia.teknokrat.ac.id/w/index.php?title=Hybridsort&oldid=247603398“
Kategorie:
  • Sortieralgorithmus

  • indonesia
  • Polski
  • العربية
  • Deutsch
  • English
  • Español
  • Français
  • Italiano
  • مصرى
  • Nederlands
  • 日本語
  • Português
  • Sinugboanong Binisaya
  • Svenska
  • Українська
  • Tiếng Việt
  • Winaray
  • 中文
  • Русский
Sunting pranala
Pusat Layanan

UNIVERSITAS TEKNOKRAT INDONESIA | ASEAN's Best Private University
Jl. ZA. Pagar Alam No.9 -11, Labuhan Ratu, Kec. Kedaton, Kota Bandar Lampung, Lampung 35132
Phone: (0721) 702022
Email: pmb@teknokrat.ac.id