#40 Binäre Suche in sortierten Folgen Flashcards
Wie sucht man ein Element in einem beliebigen Array?
int* sucheElement(int* array, int anzahl, int element) {
for(int i = 0; i < anzahl; i++) {
if(element == array[i]) {
return &array[i]; // array + i
}
}
return NULL;
}
Was fällt die zu dem Begriff Sequentielle Suche ein?
Sequentielle Suche
- Algorithmus: Durchsuche die Folge von vorne bis hinten
- Maximal werden n Suchschritte bei einer Folge der Länge n benötigt
- Funktioniert auch bei unsortierten Folgen
Suche Eintrag mit Nummer 78:
3 13 25 31 38 41 47 48 50 56 60 61 78 83 89 90 100
Best Case: 1 Schritt Worst Case: n Schritte
Was fällt dir zur Binären suche ein?
Algorithmus:
- Beginne in der Mitte des Feldes
- Wenn das zu testende Element dem Suchelement entspricht: fertig
- Ist das getestete Element kleiner als das Suchelement, muss die Suche rechts
fortgesetzt werden, sonst links
- Fahre auf diese Weise in der Mitte der rechten bzw. linken Hälfte fort, solange,
bis das Element gefunden wurde oder feststeht, dass das Element nicht in der
Liste sein kann
- Funktioniert nur bei sortierten Folgen
Suche Eintrag mit Nummer 78:
3 13 25 31 38 41 47 48 50 56 60 61 78 83 89 90 100
Best Case: 1 Schritt
Worst Case: 1 + ⌊log2 n⌋ Schritte
Welche Bibliothek steht uns zur Verfügung zur Binär Suche?
void *bsearch(
const void *key,
const void base,
size_t n,
size_t size,
int (cmp)(const void *a, const void *b)
)
7
- key = Suchwert
- base = das Feld, in dem gesucht werden soll (muss aufsteigend sortiert sein)
- n = Anzahl Elemente im Feld
- size = Größe eines Feldelements
- cmp = Zeiger auf eine Funktion, die den ersten Parameter (a) mit dem zweiten Parameter (b)
vergleicht und einen Wert < 0 zurückgibt, wenn a vor b in der Ordnung folgt, > 0, wenn
a nach b folgt und 0, wenn das Objekt gefunden wurde.
- Rückgabewert ist Zeiger auf das gefundene Element, oder NULL, wenn Element nicht gefunden wurde
Was ist Grundsätzlich zu Sortieralgorithmen zu sagen?
-Ziel: eine ungeordnete Folge von Daten (Array) soll nach einer bestimmten
Ordnung sortiert werden.
- Anforderung: Sortierung innerhalb des gegebenen Speichers (keine
komplette Kopie, sonst zu hoher Speicherbedarf)
- Einschränkung: Es können immer nur zwei Elemente miteinander verglichen
werden.
- Beispiele: Insertion Sort, Selection Sort, Bubble Sort, Quicksort,
Heapsort, Mergesort
(mehr Details im Modul „Algorithmen und Datenstrukturen“)
Erläutere bsearch.
Die Funktion bsearch implementiert das allgemeine Vorgehen der binären Suche. Der
konkrete Inhalt des Arrays ist der Funktion „egal“.
- Funktion ist unabhängig vom konkreten Datentyp, der im Array gespeichert ist:
- lediglich die Größe eines Elements muss angegeben werden, damit die Speicherzellen von
den Funktionen korrekt adressiert werden können
- die Anzahl der Elemente muss übergeben werden, damit die Funktionen wissen, wie groß
das Feld ist
Im Algorithmus ist es erforderlich, zwei Elemente zu vergleichen und zu
entscheiden, welches Element in der gesuchten Ordnung vor dem
anderen steht.
- dieser Teil ist als einziger nicht unabhängig vom Datentyp und kann daher nicht Teil der
allgemeinen Funktionen sein.
- stattdessen muss der Benutzer von bsearch selbst eine Funktion schreiben, die den
Vergleich vornimmt. Die Funktion wird als Parameter an bsearch übergeben.
- Notwendige Vereinbarung: Rückgabewert der selbstzuschreibenden Vergleichsfunktion
ist < 0, wenn Element 1 vor Element 2 kommt, > 0, wenn Element 1 nach Element 2
kommt und = 0, wenn sie gleich sind (vgl. strcmp).
- die beiden Parameter werden (um allgemein definiert sein zu können) als Zeiger auf
void (void*) übergeben und müssen zunächst in den eigentlichen Typ gewandelt
werden.
- bsearch ruft dann diese Funktion mit jeweils zwei Parametern aus dem Feld auf und
verfährt dann weiter gemäß dem entsprechenden Algorithmus.
Bsp
__________________________________________________
int compare(const void* pa, const void* pb) {
int* a = (int) pa;
int b = (int*) pb;
if(*a > b) {
return 1;
} else if(a < *b) {
return -1;
} else {
return 0;
}
}
int main() {
int a[] = { 1, 3, 7, 9, 13, 21, 23, 45 };
int n = sizeof(a) / sizeof(int);
int search = 47;
int *result = bsearch(&search, a, n, sizeof(int), compare);
if(result == NULL) {
printf(“Nicht gefunden!”);
} else {
printf(“Wert gefunden: %d\n”, *result);
}
return 0;
}
___________________________________________
Erkläre die Grundidee von Insertion Sort .
- Gegeben: Feld mit unsortierten Daten
- Sortieren durch direktes Einfügen:
- Analogie zum Sortieren der Karten auf der Hand beim Kartenspiel
- Betrachte die Karten der Reihe nach (z.B. von links nach rechts)
- Füge jede Karte in die Menge der bereits sortierten Karten an der richtigen
Stelle ein
Pseudocode: - a sei das zu sortierende Feld (a0 … an-1)
- n sei die Anzahl der Elemente in a
_____________________________________________
FÜR i = 1..n-1
v = a[i]
j = i
SOLANGE j ≥ 1 UND a[j-1] > v
a[j] = a[j-1]
j = j-1
ENDE
a[j] = v
ENDE
_____________________________________________
Betrachte Elemente der Reihe nach (ab zweitem)
v: einzusortierendes Element
(Elemente davor bereits sortiert)
Verschiebe alle Elemente die größer als das
einzusortierende Element sind um eine
Position nach rechts
Einsortieren des neuen Elements
___________________________________________
Mögliche Darstellung in C:
void insertionSort(int a[], int n)
{
for(int i = 1; i <= n-1; i++) {
int value = a[i];
int j = i;
while(j >= 1 && a[j - 1] > value) {
a[j] = a[j - 1];
j–;
}
a[j] = value;
}
}
Welche Bibliotheksfunktion gibt es zum Sortieren?
Bibliotheksfunktion Quicksort
- Quicksort ist ein sehr effizienter Sortieralgorithmus.
- Die C-Standardbibliothek beinhaltet Funktion qsort zum Sortieren eines
Feldes beliebigen Typs nach dem Quicksort-Algorithmus
_____________________________________________
void qsort(
void base,
size_t n,
size_t size,
int (cmp)(const void, const void)
)
- base = das Feld, in dem gesucht werden soll (muss aufsteigend sortiert sein)
- n = Anzahl Elemente im Feld
- size = Größe eines Feldelements
- cmp = Zeiger auf eine Funktion, die den ersten Parameter (a) mit dem zweiten
Parameter (b) vergleicht und einen Wert < 0 zurückgibt, wenn a vor b in der
Ordnung folgt, > 0, wenn a nach b folgt und 0, wenn das Objekt
gefunden wurde.
- Kein Rückgabewert
