Ein '''Gozintograph''' (von engl. ''goes into'' = „geht hinein“) ist ein gerichteter Graph, der die Zerlegung eines Endprodukts in seine Einzelteile oder Komponenten beschreibt.
Jede Kante stellt dabei eine „Gozinto“-Beziehung dar: Sie zeigt von einer Komponente auf das Produkt, in das sie eingeht. Der Gozintograph ist ein zentrales Hilfsmittel in der Produktionsplanung und Stücklistenverwaltung.

== Definition ==

Ein Gozintograph ist ein gerichteter, azyklischer Graph

:<math>G=(V,E)</math>

mit:
* <math>V</math> als Menge der Knoten (Produkte oder Komponenten),
* <math>E \subseteq V \times V</math> als Menge der gerichteten Kanten.

Zusätzlich besitzt jede Kante ein Gewicht <math>a_{ij} \in \mathbb{N}</math>.
Eine Kante <math>(v_i,v_j)\in E</math> mit Gewicht <math>a_{ij}</math> bedeutet, dass zur Herstellung des Produkts <math>v_j</math> genau <math>a_{ij}</math> Einheiten der Komponente <math>v_i</math> benötigt werden.

Da rekursive Stücklisten ausgeschlossen werden, enthält ein Gozintograph keine Zyklen.

== Zusammenhang zu Matrizen ==

Die Informationen eines Gozintographen lassen sich in einer sogenannten '''Gozintomatrix''' darstellen.

Dies ist eine Matrix

:<math>A=(a_{ij})</math>

bei der das Element <math>a_{ij}</math> die Anzahl der Einheiten der Komponente <math>i</math> angibt, die unmittelbar zur Herstellung des Produkts <math>j</math> benötigt werden.

Unter der Voraussetzung, dass der Gozintograph zyklusfrei ist und <math>I-A</math> invertierbar ist, kann der Gesamtbedarf aller Komponenten über die Gleichung

:<math>
\mathbf{x}=(I-A)^{-1}\mathbf{y}
</math>

bestimmt werden, wobei:
* <math>\mathbf{y}</math> den Vektor der Endprodukte,
* <math>\mathbf{x}</math> den Vektor der insgesamt benötigten Komponentenmengen

beschreibt.

== Beispiele ==

=== Produktion eines Produkts aus Einzelteilen ===

Im folgenden Beispiel werden fünf Bauteile <math>B_1,B_2,B_3,B_4,B_5</math> aus vier Einzelteilen <math>E_1,E_2,E_3,E_4</math> gefertigt.
Die Pfeile zeigen, welche Einzelteile in welches Bauteil eingehen. Die Zahlen an den Pfeilen geben die benötigte Stückzahl an.

<html>
<style>
.gozinto-wrap {
width:95vw;
height:50vw;
max-width:1100px;
max-height:450px;
border:0;
margin:0;
padding:0;
}

svg {
width:100%;
height:100%;
touch-action:none;
user-select:none;
background:white;
}

.node-rect {
fill:#3498db;
stroke:#1f4e78;
stroke-width:2;
cursor:grab;
}

.node-text, .count-text {
font-family:sans-serif;
font-size:14px;
fill:#000;
pointer-events:none;
}

.edge-line {
stroke:#000;
stroke-width:2;
fill:none;
}

.edge-arrow {
fill:#000;
}

.count-circle {
fill:#fff;
stroke:#000;
stroke-width:1.5;
}
</style>

<div class="gozinto-wrap">
<svg id="gozinto_svg_2"
viewBox="0 0 1200 450"
preserveAspectRatio="xMinYMin meet">
</svg>
</div>

<script>
(function(){

const svg=document.getElementById("gozinto_svg_2");

const scale=100;
const yOffset=0;
const xOffsetGlobal=120;

function svgEl(name,attrs){
const el=document.createElementNS("http://www.w3.org/2000/svg",name);
for(const k in (attrs||{})) el.setAttribute(k,attrs[k]);
return el;
}

function getSVGcoords(evt){
const pt=svg.createSVGPoint();
pt.x=evt.clientX;
pt.y=evt.clientY;
return pt.matrixTransform(svg.getScreenCTM().inverse());
}

function createNode(id,cx,cy,w,h,label){

cx+=xOffsetGlobal/scale;

const g=svgEl("g",{"data-id":id});

const rect=svgEl("rect",{
class:"node-rect",
x:(cx-w/2)*scale,
y:(cy-h/2)*scale+yOffset,
width:w*scale,
height:h*scale,
rx:6,
ry:6
});

const text=svgEl("text",{
class:"node-text",
x:cx*scale,
y:cy*scale+yOffset,
"text-anchor":"middle",
"dominant-baseline":"middle"
});

text.textContent=label;

g.appendChild(rect);
g.appendChild(text);

svg.appendChild(g);

const node={id,cx,cy,w,h,rect,text,g};

let dragging=false,start={};

rect.addEventListener("pointerdown",e=>{
rect.setPointerCapture(e.pointerId);
dragging=true;

const p=getSVGcoords(e);

start={
px:p.x,
py:p.y,
cx:node.cx,
cy:node.cy
};
});

rect.addEventListener("pointermove",e=>{

if(!dragging) return;

const p=getSVGcoords(e);

node.cx=start.cx+(p.x-start.px)/scale;
node.cy=start.cy+(p.y-start.py)/scale;

updateNode(node);
updateAllEdges();
});

rect.addEventListener("pointerup",e=>{
dragging=false;
rect.releasePointerCapture(e.pointerId);
});

return node;
}

function updateNode(n){
n.rect.setAttribute("x",(n.cx-n.w/2)*scale);
n.rect.setAttribute("y",(n.cy-n.h/2)*scale+yOffset);

n.text.setAttribute("x",n.cx*scale);
n.text.setAttribute("y",n.cy*scale+yOffset);
}

function intersectRectBorder(node,tx,ty){

const cx=node.cx;
const cy=node.cy;

const w2=node.w/2;
const h2=node.h/2;

const dx=tx-cx;
const dy=ty-cy;

let pts=[];

if(Math.abs(dx)>1e-9){

let t1=(-w2)/dx;
let y1=cy+t1*dy;

if(t1>0 && y1>=cy-h2 && y1<=cy+h2)
pts.push({x:cx-w2,y:y1,t:t1});

let t2=(w2)/dx;
let y2=cy+t2*dy;

if(t2>0 && y2>=cy-h2 && y2<=cy+h2)
pts.push({x:cx+w2,y:y2,t:t2});
}

if(Math.abs(dy)>1e-9){

let t3=(-h2)/dy;
let x3=cx+t3*dx;

if(t3>0 && x3>=cx-w2 && x3<=cx+w2)
pts.push({x:x3,y:cy-h2,t:t3});

let t4=(h2)/dy;
let x4=cx+t4*dx;

if(t4>0 && x4>=cx-w2 && x4<=cx+w2)
pts.push({x:x4,y:cy+h2,t:t4});
}

pts.sort((a,b)=>a.t-b.t);

return pts[0]||{x:cx,y:cy};
}

function pointOnCircle(cx,cy,R,tx,ty){

const dx=tx-cx;
const dy=ty-cy;

const d=Math.sqrt(dx*dx+dy*dy);

if(d<1e-9) return {x:cx,y:cy};

return {
x:cx+R*dx/d,
y:cy+R*dy/d
};
}

function makeArrowHead(x,y,ux,uy,size){

let px=-uy;
let py=ux;

return `M ${x} ${y}
L ${x-ux*size+px*size*0.5} ${y-uy*size+py*size*0.5}
L ${x-ux*size-px*size*0.5} ${y-uy*size-py*size*0.5} Z`;
}

const edges=[];

function makeConnection(fromNode,toNode,amount,yMid,xOffset){

const g=svgEl("g",{});

const lineA=svgEl("path",{class:"edge-line"});
const lineB=svgEl("path",{class:"edge-line"});
const circle=svgEl("circle",{class:"count-circle"});
const text=svgEl("text",{class:"count-text"});
const arrow=svgEl("path",{class:"edge-arrow"});

text.textContent=amount;

g.appendChild(lineA);
g.appendChild(lineB);
g.appendChild(circle);
g.appendChild(text);
g.appendChild(arrow);

svg.appendChild(g);

let e={
fromNode,
toNode,
amount,
yMid,
xOffset,
circle,
text,
lineA,
lineB,
arrow
};

edges.push(e);

updateEdge(e);
}

function updateEdge(e){

const cx=(e.fromNode.cx+e.toNode.cx)/2+(e.xOffset||0);
const cy=e.yMid;
const R=0.14;

const pF=intersectRectBorder(e.fromNode,cx,cy);
const pT=intersectRectBorder(e.toNode,cx,cy);

const pCircleIn=pointOnCircle(cx,cy,R,pF.x,pF.y);
const pCircleOut=pointOnCircle(cx,cy,R,pT.x,pT.y);

const px=p=>[p.x*scale,p.y*scale+yOffset];

const F=px(pF);
const Ci=px(pCircleIn);
const Co=px(pCircleOut);
const T=px(pT);

e.lineA.setAttribute("d",`M ${F[0]} ${F[1]} L ${Ci[0]} ${Ci[1]}`);
e.lineB.setAttribute("d",`M ${Co[0]} ${Co[1]} L ${T[0]} ${T[1]}`);

e.circle.setAttribute("cx",cx*scale);
e.circle.setAttribute("cy",cy*scale+yOffset);
e.circle.setAttribute("r",R*scale);

e.text.setAttribute("x",cx*scale-5);
e.text.setAttribute("y",cy*scale+yOffset+5);

let ux=T[0]-Co[0];
let uy=T[1]-Co[1];

let L=Math.sqrt(ux*ux+uy*uy);

if(L<1e-6) L=1;

ux/=L;
uy/=L;

e.arrow.setAttribute("d",makeArrowHead(T[0],T[1],ux,uy,10));
}

function updateAllEdges(){
edges.forEach(updateEdge);
}

const nodes={};

nodes.E1=createNode("E1",0,0.5,1.0,0.5,"E1");
nodes.E2=createNode("E2",2.5,0.5,1.0,0.5,"E2");
nodes.E3=createNode("E3",5.0,0.5,1.0,0.5,"E3");
nodes.E4=createNode("E4",7.5,0.5,1.0,0.5,"E4");

nodes.B1=createNode("B1",0.75,4.5,1.0,0.5,"B1");
nodes.B2=createNode("B2",2.5,4.5,1.0,0.5,"B2");
nodes.B3=createNode("B3",5.0,4.5,1.0,0.5,"B3");
nodes.B4=createNode("B4",7.5,4.5,1.0,0.5,"B4");
nodes.B5=createNode("B5",10,4.5,1.0,0.5,"B5");

makeConnection(nodes.E1,nodes.B1,"2",2.2,-0.2);
makeConnection(nodes.E2,nodes.B1,"1",2.2,0.2);

makeConnection(nodes.E1,nodes.B2,"2",2.2,-0.2);
makeConnection(nodes.E2,nodes.B2,"1",2.2,0.2);

makeConnection(nodes.E1,nodes.B3,"1",2.2,-0.25);
makeConnection(nodes.E2,nodes.B3,"1",2.2,0.0);
makeConnection(nodes.E3,nodes.B3,"1",2.2,0.25);

makeConnection(nodes.E1,nodes.B4,"2",2.2,-0.3);
makeConnection(nodes.E3,nodes.B4,"1",2.2,0.0);
makeConnection(nodes.E4,nodes.B4,"1",2.2,0.3);

makeConnection(nodes.E1,nodes.B5,"1",2.2,-0.2);
makeConnection(nodes.E4,nodes.B5,"2",2.2,0.2);

updateAllEdges();

})();
</script>
</html>

Die Gozintomatrix zum oberen Gozintographen kann aus folgender Tabelle abgeleitet werden:

{| class="wikitable"
! !! B1 !! B2 !! B3 !! B4 !! B5
|-
| '''E1''' || 2 || 2 || 1 || 2 || 1
|-
| '''E2''' || 1 || 1 || 1 || 0 || 0
|-
| '''E3''' || 0 || 0 || 1 || 1 || 0
|-
| '''E4''' || 0 || 0 || 0 || 1 || 2
|}

und ist durch

:<math>
A=
\begin{pmatrix}
2 & 2 & 1 & 2 & 1 \\
1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 2
\end{pmatrix}
</math>

gegeben.

=== Produktion von Spielwaren aus Rohstoffen über Zwischenprodukte ===

Ein Spielwarenhersteller produziert aus drei Rohstoffen <math>R_1,R_2,R_3</math> zunächst die beiden Zwischenprodukte <math>Z_1,Z_2</math>, aus denen anschließend die drei Endprodukte <math>E_1,E_2,E_3</math> gefertigt werden.

Die Pfeile im Gozintographen geben an, wie viele Mengeneinheiten eines Materials zur Produktion einer Mengeneinheit des entstehenden Produkts benötigt werden.

<html>
<style>
.gozinto-wrap2 {
width:95vw;
height:70vw;
max-width:1200px;
max-height:800px;
border:0;
margin:0;
padding:0;
}

.gozinto-wrap2 svg {
width:100%;
height:100%;
touch-action:none;
user-select:none;
background:white;
}
</style>

<div class="gozinto-wrap2">
<svg id="gozinto_svg"
viewBox="0 0 1180 700"
preserveAspectRatio="xMinYMin meet">
</svg>
</div>

<script>
(function(){

const svg=document.getElementById("gozinto_svg");

const scale=100;
const yOffset=0;
const xOffsetGlobal=120;

function svgEl(name,attrs){
const el=document.createElementNS("http://www.w3.org/2000/svg",name);
for(const k in (attrs||{})) el.setAttribute(k,attrs[k]);
return el;
}

function createNode(id,cx,cy,w,h,label){

cx+=xOffsetGlobal/scale;

const g=svgEl("g",{});

const rect=svgEl("rect",{
class:"node-rect",
x:(cx-w/2)*scale,
y:(cy-h/2)*scale,
width:w*scale,
height:h*scale,
rx:6,
ry:6
});

const text=svgEl("text",{
class:"node-text",
x:cx*scale,
y:cy*scale,
"text-anchor":"middle",
"dominant-baseline":"middle"
});

text.textContent=label;

g.appendChild(rect);
g.appendChild(text);

svg.appendChild(g);

return {cx,cy,w,h};
}

function drawArrow(x1,y1,x2,y2,label){

const line=svgEl("line",{
x1,y1,x2,y2,
stroke:"black",
"stroke-width":"2"
});

svg.appendChild(line);

const text=svgEl("text",{
x:(x1+x2)/2,
y:(y1+y2)/2-10,
class:"count-text",
"text-anchor":"middle"
});

text.textContent=label;

svg.appendChild(text);
}

const R1=createNode("R1",0,1,1,0.5,"R1");
const R2=createNode("R2",2.5,1,1,0.5,"R2");
const R3=createNode("R3",5,1,1,0.5,"R3");

const Z1=createNode("Z1",1.2,3.5,1,0.5,"Z1");
const Z2=createNode("Z2",3.8,3.5,1,0.5,"Z2");

const E1=createNode("E1",0.5,6,1,0.5,"E1");
const E2=createNode("E2",2.8,6,1,0.5,"E2");
const E3=createNode("E3",5.1,6,1,0.5,"E3");

drawArrow(170,120,240,320,"3");
drawArrow(420,120,240,320,"4");

drawArrow(170,120,500,320,"1");
drawArrow(420,120,500,320,"2");
drawArrow(670,120,500,320,"3");

drawArrow(240,370,170,570,"2");
drawArrow(240,370,420,570,"1");

drawArrow(500,370,170,570,"1");
drawArrow(500,370,420,570,"3");
drawArrow(500,370,670,570,"2");

})();
</script>
</html>

Die vollständigen Mengen seien wie folgt definiert:

{| class="wikitable"
! !! Z1 !! Z2
|-
| '''R1''' || 3 || 1
|-
| '''R2''' || 4 || 2
|-
| '''R3''' || 0 || 3
|}

{| class="wikitable"
! !! E1 !! E2 !! E3
|-
| '''Z1''' || 2 || 1 || 0
|-
| '''Z2''' || 1 || 3 || 2
|}

Aus diesen Tabellen ergibt sich die '''Gozintomatrix Rohstoffe → Endprodukte''' durch Matrixmultiplikation:

:<math>
RZ=
\begin{pmatrix}
3 & 1 \\
4 & 2 \\
0 & 3
\end{pmatrix}
</math>

:<math>
ZE=
\begin{pmatrix}
2 & 1 & 0 \\
1 & 3 & 2
\end{pmatrix}
</math>

:<math>
RE=RZ \cdot ZE
=
\begin{pmatrix}
3 & 1 \\
4 & 2 \\
0 & 3
\end{pmatrix}
\cdot
\begin{pmatrix}
2 & 1 & 0 \\
1 & 3 & 2
\end{pmatrix}
</math>

Berechnung:

:<math>
RE=
\begin{pmatrix}
7 & 6 & 2 \\
10 & 10 & 4 \\
3 & 9 & 6
\end{pmatrix}
</math>

Die Matrix zeigt, wie viele Mengeneinheiten der Rohstoffe <math>R_1,R_2,R_3</math> jeweils zur Herstellung einer Einheit der Endprodukte <math>E_1,E_2,E_3</math> notwendig sind.

[[Kategorie:Lineare_Algebra]]
[[Kategorie:AHR_WuV_Mathe_GK]]

Gozintograph

2026-05-27T08:24:26Z

Flbkwikiadmin:

Gozintograph

2026-05-27T08:23:54Z

Flbkwikiadmin: /* Produktion eines Produkts aus Einzelteilen */

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

#WEITERLEITUNG [[Insertionsort]]

Insertionsort

2026-04-28T08:52:09Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

== Einführung ==
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relativ simpel. Das Prinzip von Insertion Sort ist folgendes: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links verschoben – und zwar so lange, bis das einzufügende Element größer oder gleich dem Element ist, das an der aktuell betrachteten Position steht.

Der Platz für das Element, das verschoben wird, ist währenddessen frei. Diese Lücke wird anschließend mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite (grün dargestellt) befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links verschoben wurde. Das aktuell eingefügte Element ist fett markiert.

{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''<span style="color:green;">5</span>'' || <span style="color:blue;">7</span> || <span style="color:blue;">0</span> || <span style="color:blue;">3</span> || <span style="color:blue;">4</span> || <span style="color:blue;">2</span> || <span style="color:blue;">6</span> || <span style="color:blue;">1</span> || (0)
|-
| '''<span style="color:green;">5</span>''' || '''<span style="color:green;">7</span>''' || <span style="color:blue;">0</span> || <span style="color:blue;">3</span> || <span style="color:blue;">4</span> || <span style="color:blue;">2</span> || <span style="color:blue;">6</span> || <span style="color:blue;">1</span> || (0)
|-
| '''''<span style="color:green;">0</span>''''' || <span style="color:green;">5</span> || <span style="color:green;">7</span> || <span style="color:blue;">3</span> || <span style="color:blue;">4</span> || <span style="color:blue;">2</span> || <span style="color:blue;">6</span> || <span style="color:blue;">1</span> || (2)
|-
| <span style="color:green;">0</span> || '''''<span style="color:green;">3</span>''''' || <span style="color:green;">5</span> || <span style="color:green;">7</span> || <span style="color:blue;">4</span> || <span style="color:blue;">2</span> || <span style="color:blue;">6</span> || <span style="color:blue;">1</span> || (2)
|-
| <span style="color:green;">0</span> || <span style="color:green;">3</span> || '''''<span style="color:green;">4</span>''''' || <span style="color:green;">5</span> || <span style="color:green;">7</span> || <span style="color:blue;">2</span> || <span style="color:blue;">6</span> || <span style="color:blue;">1</span> || (2)
|-
| <span style="color:green;">0</span> || '''''<span style="color:green;">2</span>''''' || <span style="color:green;">3</span> || <span style="color:green;">4</span> || <span style="color:green;">5</span> || <span style="color:green;">7</span> || <span style="color:blue;">6</span> || <span style="color:blue;">1</span> || (4)
|-
| <span style="color:green;">0</span> || <span style="color:green;">2</span> || <span style="color:green;">3</span> || <span style="color:green;">4</span> || <span style="color:green;">5</span> || '''''<span style="color:green;">6</span>''''' || <span style="color:green;">7</span> || <span style="color:blue;">1</span> || (1)
|-
| <span style="color:green;">0</span> || '''''<span style="color:green;">1</span>''''' || <span style="color:green;">2</span> || <span style="color:green;">3</span> || <span style="color:green;">4</span> || <span style="color:green;">5</span> || <span style="color:green;">6</span> || <span style="color:green;">7</span> || (6)
|}

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode so aus:

<syntaxhighlight lang="text">
prozedur insertionSort(A ist Liste sortierbarer Elemente)
n = Länge von A
für i von 1 bis n - 1 wiederhole
einzusortierenderWert = A[i]
j = i - 1
solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole
A[j + 1] = A[j]
j = j - 1
ende solange
A[j + 1] = einzusortierenderWert
ende für
ende prozedur
</syntaxhighlight>

== Komplexität ==

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente <math>n</math>.

Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.

=== Average Case ===
Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.

Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.

Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei <math>O(n^2)</math>.

=== Worst Case ===
Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:

<math>[11, 7, 5, 3, 2, 0]</math>

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen <math>c</math> gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt <math>n</math>.

Beim ersten äußeren Schleifendurchlauf ist <math>c = 1</math>, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit <math>n - 1</math> Vergleichen.

Die Gesamtanzahl der Vergleiche ergibt sich zu:

<math>1 + 2 + 3 + \dots + (n - 1)</math>

Dies ist eine [[Arithmetische-reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:

<math>\frac{n(n-1)}{2}</math>

Für große <math>n</math> dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]