Vergelijkingen
Verwisselingen
Ronde

  • Wordt ingevoegd
  • Vergeleken
  • Verwisseld
  • Gesorteerd deel

Meer over insertion sort

Insertion sort

Insertion sort werkt zoals veel mensen speelkaarten in hun hand sorteren. Het houdt vooraan in de lijst een gesorteerd deel bij, neemt de volgende waarde en schuift die terug langs elke grotere waarde tot die past. Speel het sorteren af op elke snelheid, of loop er per vergelijking doorheen, en volg de tellers voor vergelijkingen, verwisselingen en rondes. Druk op Afspelen om het sorteren te volgen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om ergens naartoe te springen. De tegels tellen vergelijkingen, verwisselingen en rondes. Kies hoeveel staven, hoe ze beginnen, of typ je eigen getallen. Als het bord geselecteerd is, zetten de pijltjestoetsen een stap, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

Hoe het werkt

  1. Kies hoeveel staven en hoe ze beginnen: willekeurig, bijna gesorteerd, omgekeerd of met weinig unieke waarden. Of typ je eigen getallen.
  2. Druk op Afspelen, of gebruik Stap en Terug om per vergelijking te gaan. Sleep de stappenschuif om naar elk punt in het sorteren te springen.
  3. Probeer een bijna gesorteerde lijst en een omgekeerde, en vergelijk hoeveel vergelijkingen elk kost.

Hoe insertion sort werkt

De eerste waarde alleen is al een gesorteerd deel. Neem de tweede waarde en vergelijk die met de waarde ervoor; is die groter, verwissel ze dan, en blijf vergelijken en verwisselen tot de waarde ervoor niet groter is of de waarde vooraan staat. Nu staan de eerste twee waarden op volgorde. Doe hetzelfde met de derde waarde, de vierde, enzovoort tot het eind van de lijst.

Snel bij bijna gesorteerde lijsten

Elke ronde stopt bij de eerste waarde die niet groter is, dus een waarde die al dicht bij zijn plek staat, kost maar een of twee vergelijkingen. Een gesorteerde lijst kost n − 1 vergelijkingen en geen verwisselingen; een omgekeerde lijst, het slechtste geval, kost van elk n(n − 1)/2. Het aantal verwisselingen is altijd gelijk aan het aantal inversies in de beginlijst: de paren die in de verkeerde volgorde staan. Daarom wordt insertion sort vaak gebruikt voor korte of bijna gesorteerde lijsten, en binnen snellere sorteeralgoritmen om kleine stukken af te maken.

Veelgestelde vragen

Hoe werkt insertion sort?

Het bouwt vooraan in de lijst een gesorteerd deel op. Elke ronde neemt de volgende waarde en schuift die terug langs elke grotere waarde ervoor, tot die past. Na ronde k staan de eerste k + 1 waarden op volgorde, maar een latere waarde kan er nog tussen worden gevoegd.

Hoeveel vergelijkingen en verwisselingen doet insertion sort?

Het aantal verwisselingen is altijd gelijk aan het aantal inversies in de beginlijst: geen bij een gesorteerde lijst, n(n − 1)/2 bij een omgekeerde. Het aantal vergelijkingen is het aantal verwisselingen plus hoogstens één per ronde, dus tussen n − 1 en n(n − 1)/2.

Waarom is insertion sort snel bij bijna gesorteerde lijsten?

Omdat een ronde stopt zodra die een waarde tegenkomt die niet groter is. Staat elke waarde dicht bij zijn definitieve plek, dan is elke ronde kort en kost het hele sorteren ongeveer n stappen.

Is insertion sort stabiel?

Ja. Een waarde schuift alleen langs waarden die strikt groter zijn, dus gelijke waarden passeren elkaar nooit en houden hun oorspronkelijke volgorde.

Worden mijn getallen ergens naartoe gestuurd?

Nee. Het sorteren gebeurt in je browser, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor