Insertionsort

Insertionsort (engl. insertion – das Einfügen, sort – sortieren) ist ein einfaches stabiles Sortierverfahren.

1. einfach zu implementieren
2. effizient bei
   • kleinen Eingabemengen
   • vorsortiert (stabilen) Eingabemengen
3. minimaler Speicherverbrauch (da der Algorithmus ortsfest arbeitet)

1. nicht so effizient bei größeren Eingabemengen
2. hat oft Probleme mit nicht vorsortierten Programme

Dies ist eine Methode, die z.B. auch Kartenspieler beim Sortieren ihrer Karten verwenden: Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben). Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem freigewordenen Platz eingefügt wird.

Die erste Karte ganz links ist sortiert. Wir nehmen die zweite Karte und stecken sie, je nach größe, vor oeder hinter die erste Karte. Damit sind die beiden ersten Karten relativ zueinander sortiert. Wir nehmen die dritte, vierte, fünfte, … Karte und schieben sie so lange nach links, bis wir an die Stelle kommen, an der sie hineinpasst. Dort stecken wir sie hinein

// Programmname: Insertionsort
// erstellt von: Stefan Artmüller & Thomas Zlabinger
 
#include <iostream>
#include <conio.h>
 
using namespace std;
 
eingabe(int zahlen[10])
{
 cout << "Geben Sie nun die 10 Zahlen ein:\n";
 for (int i=0; i<10; i++)
	{
	 cout << "   " << i+1 << ". Zahl: ";
	 cin >> zahlen[i];
	}
}
 
ausgabe(int zahlen[10])
{
 cout << "  ";
 for (int i=0; i<10; i++)
	{
	 cout << " " << zahlen[i];
	}
}
 
insertionsort(int zahlen[10])
{
 int min;
 int hilfe;
 for (int i=0; i<9; i++)
	{
	 min=i;
	 for (int j=i+1; j<10; j++)
		{
		 if (zahlen[j]<zahlen[min])
			min=j;
		}
	 hilfe=zahlen[min];
	 for (int k=min; k>i; k--)
		{
		 zahlen[k]=zahlen[k-1];
		}
	 zahlen[i]=hilfe;
	}
}
 
void main()
{
 int zahlen[10];
 cout << "Dieses Programm sortiert 10 von Ihnen eingegebene Zahlen der Groesse nach"
		 " und\nmit der kleinsten beginnend!\n\n";
 eingabe(zahlen);
 cout << "\n\nDie Zahlen in ungeordneter Reihenfolge:\n";
 ausgabe(zahlen);
 insertionsort(zahlen);
 cout << "\n\nDie Zahlen in geordneter Reihenfolge:\n";
 ausgabe(zahlen);
 
  getch();
}