1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:

#include <stdio.h>
#include <stdlib.h>
#include "readline.h"
#include <time.h>

typedef struct person{
	char nameperson[20];
	char Abteilung;
	int TelNr;
	struct person *next;
}Person;
struct person *anfang = NULL;
struct person *sanfang = NULL;

void neuePerson()
{	
	struct person* zeiger;
	if(anfang==NULL){  
		anfang=(Person*)malloc(sizeof(struct person));
		readLine(anfang->nameperson, 20);
		anfang->TelNr=rand()%100;
		anfang->Abteilung = rand() % 3 + 65; 
		anfang->next=NULL;
		}
	else{
		zeiger=anfang;
		while(zeiger->next != NULL) zeiger=zeiger->next;
		if(zeiger->next == NULL){
			zeiger->next=(Person*)malloc(sizeof(struct person));
			zeiger=zeiger->next;
			readLine(zeiger->nameperson, 20);
			zeiger->TelNr=rand()%100;
			zeiger->Abteilung = rand() % 3 + 65; 
			zeiger->next=NULL;
		}
	}
}

void listeAusgeben(Person* p)
{
	struct person* zeiger = p;
	int mitarbeiter = 0;
	printf("Personalpool Firma:\n");
	while(zeiger != NULL){
		printf("name: %s	abteilung: %c	telNr: %i\n",zeiger->nameperson, zeiger->Abteilung, zeiger->TelNr);
		zeiger=zeiger->next;
		mitarbeiter++;
	}
	printf("Personalpool ferig -- Anzahl Mitarbeiter: %d\n", mitarbeiter);	
}

int sortieren() {
	if (anfang == NULL) return 0; //nichts mehr zu machen
	//beim Probeablauf wird immer die letzte Person entfernt
	Person* letzte = anfang;
	Person* vorletzte = NULL;
	while (letzte->next != NULL) {
		vorletzte = letzte;
		letzte = letzte->next;
	}
	if (vorletzte != NULL) vorletzte->next = NULL; //entferne letzten Eintrag aus unsortierter Liste
	if (letzte == anfang) anfang = NULL;
	
	//Hier kommt das Einfügen in die sortierte Liste
	if (sanfang == NULL) sanfang = letzte; //Fall 1: leere Liste
	else {
		if (letzte->Abteilung < sanfang->Abteilung) { //Fall 2.1
			letzte->next = sanfang;
			sanfang = letzte;
		}
		else { //Fall 2.2
			Person* pos = sanfang;
			int eingefuegt = 0;
			while (pos->next != NULL) {
				if (letzte->Abteilung < pos->next->Abteilung) { //Fall 3.1
					letzte->next = pos->next;
					pos->next = letzte;
					eingefuegt = 1;
					break;
				}
				pos = pos->next;
			}
			if (!eingefuegt) { //Fall 4
				pos->next = letzte;
			}
		}
	}	
	return 1; //weiter sortieren
}

int main()
{
	srand (time(NULL)); //srand gehört dahin, nicht nach oben - dann kann man die Eingabe auch von Datei einlesen und rand() liefert nicht immer das selbe
	printf("Bitte im Folgenden 10 Mitarbeiternamen (jeweils mit Enter) eingeben...\n");
	for(int i=0; i<10; i++)neuePerson();
	listeAusgeben(anfang);
	while (sortieren()) {
		printf("==Pool==\n");
		listeAusgeben(anfang);
		printf("==sortiert==\n");
		listeAusgeben(sanfang);
		printf("\n");	
	}
}