Zum Inhalt springen

Combsort

aus Wikipedia, der freien Enzyklopädie
Datei:Comb sort demo.gif
Sortierung eines Feldes von 33 Elementen mittels Combsort.

Combsort (von {{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}, Kamm) ist ein im April 1991 im BYTE magazine von S. Lacey und R. Box vorgestellter, vom Bubblesort abgeleiteter, nicht-stabiler In-place-Sortieralgorithmus, der eine Folge linear angeordneter Elemente (z. B. Zahlen, Alphabete) einem Vergleichskriterium (z. B. der Größe) nach anordnet.

Prinzip

Anders als Bubblesort, der nur jeweils benachbarte Elemente vergleicht und ggf. vertauscht, beginnt Combsort zunächst mit weit auseinanderliegenden Elementen (engl. Gap = Lücke). Dadurch finden grob falsch sortierte Elemente schneller ihre Zielposition. Nach jedem Durchlauf wird die Lücke mit Division durch 1,3 verkleinert und der Vorgang wiederholt. Durch diesen empirisch gefundenen krummen Divisor wird erreicht, dass sich angrenzende Bereiche in aufeinanderfolgenden Durchläufen stets überlappen und keine Cluster bilden, die erst in späteren Durchläufen aufgelöst würden.

Der Algorithmus endet, wenn mindestens ein Durchlauf mit Gap =1 erfolgt und keine Vertauschung mehr stattgefunden hat.

Bei diesem Endwert Gap =1 ist er am Ende praktisch identisch mit dem Bubblesort, und die Richtigkeit der Sortierung ist bewiesen.

Zum Namen: Das zu sortierende Feld wird quasi wie mit einem Kamm ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}) mit immer dichter werdenden Zähnen durchgekämmt.

Combsort ähnelt dem auf Insertionsort basierenden Shellsort.

Komplexität

Die Komplexität liegt je nach Ausgangssituation zwischen <math> \mathcal{O}(n^2) </math> (Worst-Case) und <math> \mathcal{O}(n \log (n)) </math> (Best-Case).

Im Best-Case ist die Liste der zu sortierenden Elemente geordnet, sobald die Schrittlänge 1 beträgt.

Im Worst-Case müssen alle benachbarten Elemente nochmals getauscht werden (mehrere Durchgänge mit Schrittlänge 1). In diesem Fall ist Combsort nicht schneller als Bubblesort.

Der Avg. Case ist <math> \mathcal{O}(n^2) </math>, analog zu Bubblesort.

Formaler Algorithmus

Im Pseudocode sieht der CombSort-Algorithmus so aus: 

prozedur combSort ( A: Liste sortierbarer Elemente )
  schritt:= Länge ( A )
  wiederhole
     vertauscht:= falsch
     für jedes i von 0 bis (Länge ( A ) - schritt) wiederhole
        falls ( A[ i ] > A[i + schritt]) dann
           vertausche ( A [ i ], A [ i + schritt ] )
           vertauscht:= wahr
        falls ende
     für ende
     falls (schritt > 1) dann 
           schritt:= Ganzzahl ( schritt/1.3 )
           vertauscht := wahr
     falls ende
  solange (vertauscht == wahr oder schritt > 1)
prozedur ende

Literatur

  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}

Weblinks

[{{canonicalurl:Commons:Category:{{#if:Sort algorithms|Sort algorithms|Combsort}}|uselang=de}} Commons: {{#if:Sortieralgorithmen|Sortieralgorithmen|{{#if:Sort algorithms|Sort algorithms|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if: 

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Sort algorithms 

   | {{#ifeq: {{#invoke:Str|left|sort algorithms|9}} 
       | category:
| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

[[b:{{#if:|{{{lang}}}:}}{{#if:Algorithmensammlung: Sortierverfahren: Combsort|Algorithmensammlung: Sortierverfahren: Combsort|Combsort}}|Wikibooks: {{#if:Combsort|Combsort|{{#if:Algorithmensammlung: Sortierverfahren: Combsort|Algorithmensammlung: Sortierverfahren: Combsort|Combsort}}}}]]{{#switch: Implementierungen in der Algorithmensammlung

|1|= – Lern- und Lehrmaterialien |0|-= |X|x={{#switch: 0 

      |0|4|10|12|14|100=}}

|#default= – Implementierungen in der Algorithmensammlung

}}{{#if: | ({{#invoke:Multilingual|format|{{{lang}}}|slang=!|shift=m}}) }}

{{#invoke:TemplatePar|check 

  |opt= 1= 2= lang= suffix=
  |template=Vorlage:Wikibooks
  |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt
  }}
  • <templatestyles src="Webarchiv/styles.css" />{{#if:20050419014554
      | {{#ifeq: 20050419014554 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Combsort | {{#invoke:WLink|getEscapedTitle|Combsort}} | {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20050419014554}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Combsort | {{#invoke:WLink|getEscapedTitle|Combsort}} | {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20050419014554}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Combsort | {{#invoke:WLink|getEscapedTitle|Combsort}} | {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Combsort | {{#invoke:WLink|getEscapedTitle|Combsort}} | {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Combsort | {{#invoke:WLink|getEscapedTitle|Combsort}} | {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Combsort | {{#invoke:WLink|getEscapedTitle|Combsort}} | {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20050419014554|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://objectz.com/columnists/leif/07242000.htm}}
    || {{#if:  || }}
  }}{{#if: Combsort
    | {{#if: {{#invoke:WLink|isBracketedLink|Combsort}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://objectz.com/columnists/leif/07242000.htm%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://objectz.com/columnists/leif/07242000.htm%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://objectz.com/columnists/leif/07242000.htm }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} bei Computer Science for the COBOL Community
Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Combsort&oldid=310129“