Programmieren in C

Sortieren, Suchen

Hochschule Fulda – FB AI

Sommersemester 2013/14

http://c.rz.hs-fulda.de

Peter Klingebiel, HS Fulda, DVZ

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 2

Sortieren 1

• Sortieren von Zahlen, Strings, allgemein von Daten, ist oft auftretende Aufgabenstellung

• Meist: Daten sind in Feldern vorhanden Sortieren von Feldelementen• Intuitiver Algorithmus:

– Feld von oben nach unten (oder von links nach rechts) durchlaufen und elementweise sortieren

– Feld solange immer wieder durchlaufen, bis Feld sortiert ist

Bubblesort-Algorithmus• http://de.wikipedia.org/wiki/Bubblesort

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 3

Sortieren 2

• 1. Durchlauf bei Bubblesort

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 4

Sortieren 3

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 5

Sortieren 4

die größten Elemente wandern nach und nach an das Ende des Feldes

steigen wie Blasen auf Bubblesort• Algorithmus für int-Feld mit n Elementen:

void bsort(int v[], int n)

int i, j;

for(i = 0; i < n; i++) for(j = 0; j < n-i-1; j++) if(v[j] > v[j+1])

swap(v, j, j+1);

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 6

Sortieren 5

• Bubblesort für Feld von Strings

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 7

Sortieren 6

• Sortierprogramm für Strings

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 8

Sortieren 7

• Diskussion– Stabilität?– Geschwindigkeit?

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 9

Sortieren 8

• Schnellerer Algorithmus Quicksort• rekursiver Algorithmus für int-Feld

void qsort(int v[], int left, int right)

int i, last;

if(left >= right) return; swap(v, left, (left + right) / 2); last = left; for(i = left + 1; i <= right; i++) if(v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last - 1); qsort(v, last + 1, right);

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 10

Sortieren 9

• Prinzip: teile und herrsche

• http://de.wikipedia.org/wiki/Quicksort

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 11

Sortieren 10

• Quicksort für Feld von Strings

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 12

Sortieren 11

• Sortierprogramm für Strings

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 13

Sortieren 12

• Diskussion– Stabilität?– Geschwindigkeit?

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 14

Sortieren 13

• bisher: nur Sortieren von Strings• Es gibt aber oft andere Typen zu sortieren,

z.B. Integer-, Double-, Struct-Typen usw. Generischer Sortieralgorithmus für Felder• Sortieralgorithmen identisch bis auf

– Vergleichsfunktion comp()– Austauschfunktion swap()

Generische Funktionsparameter Funktionen als Parameter

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 15

Sortieren 14

• Generische Funktionsparameter Nutzung des Typs void• Beispiel: swap-Funktion void swapv(void *s[], int i, int j){ void *t;

t = s[i]; s[i] = s[j]; s[j] = t;}

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 16

Sortieren 15

• Funktionen als Parameter• C erlaubt, Funktionen als Parameter an

Funktionen zu übergeben und aufzurufen• Übergabe der Funktion comp()void bsortv(void *v[], int n, int (*comp)(void *, void *)){ ...

• Aufruf der Funktion comp() ... if((* comp)(v[j], v[j+1]) > 0) ...

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 17

Sortieren 16

• Bubblesort generisch

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 18

Sortieren 17

• Quicksort generisch

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 19

Sortieren 18

• sortlib – snumcmp()

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 20

Sortieren 19

• sortlib – sswapv()

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 21

Sortieren 20

• bsort5

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 22

Sortieren 21

• qsort5

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 23

Sortieren 22

• Mit generischen Funktionen und Funktionen als Parametern auch Sortieren von komplexeren Datenstrukturen möglich

• Beispiel: Personaldatentypedef struct _person { /* Personaleintrag: */ int no; /* Personalnummer */ char *nn; /* Nachname */ char *vn; /* Vorname */ int gj; /* Geburtsjahr */ int gm; /* Geburtsmonat */ int gt; /* Geburtstag */} person_t, *person_p;

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 24

Sortieren 23

• Personalliste nach verschiedenen Kriterien (Name, P-Nr., Geburtsdatum) sortierbar

Implementierung einer Vergleichsfunktion• Beispiel: Nachnamen vergleichen

int compnn(person_p p1, person_p p2){ int n; if(n = strcmp(p1->nn, p2->nn)) return(n); else return(strcmp(p1->vn, p2->vn));}

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 25

Sortieren 24

• personal.c

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 26

Suchen 1

• Häufige Aufgabe: in größeren Datenmengen nach Einzelelementen suchen

• Oft: Daten in Feldern gespeichert• Intuitives Verfahren: Feld mit Daten von

Anfang bis Ende durchlaufen und nach gesuchtem Element fahnden– ist bei großen Datenmengen sehr langsam– notwendig bei unsortierten Daten / Feldern

in sortierten Feldern mit binärer Suche arbeiten

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 27

Suchen 2

• Beispiel: Suche in Integer-Feld

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 28

Suchen 3

• Binäre Suche: teile und finde

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 29

Suchen 4

• 1 Schritt: teilen und vergleichen

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 30

Suchen 5

• 2. Schritt: weiter teilen und vergleichen

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 31

Suchen 6

• 3. Schritt: weiter teilen und vergleichen

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 32

Suchen 7

• 4. Schritt: teilen und finden

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 33

Suchen 8

• Binärsuche: teilen und finden

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 34

Suchen 9

int binsearchi(int v[], int n, int x, int *ind)int m, l, r; /* Mitte, links, rechts */l = 0; /* links: 1. Element */r = n - 1; /* rechts: letztes El. */while(1) { if(r < l) return(0); /* kein Treffer */ m = l + ((r - l) / 2); /* Bereich halbieren */ if (v[m] == x) { /* Elem. x gefunden */ *ind = m; return(1); } if (v[m] > x) r = m - 1; /* Rechts weiter */ else l = m + 1; /* Links weiters */}

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 35

Suchen 10

• binsearchi.c - Binärsuche in int-Feld

Programmieren in C - Peter Klingebiel - HS Fulda - DVZ 36

Suchen 11

• binsearchs.c - Binärsuche in String-Feld