OOPM1718 Übungswoche 01 (06.11-12.11.17)
Zielsetzung für die Übung
Such- und Sortierproblematik
Suchen
Suche in vielen alltäglichen Situationen notwendig:
Bsp. aus der Übung:
- Suche im Telefonbuch nach einer bestimmten Nummer
- Suche im Mäppchen nach einem bestimmten Stift
- Suche im Ordner nach einem bestimmten Dokument
- Suche im Supermarkt nach einer bestimmten Ware
- Suche im Schlüsselbund nach einem bestimmten Schlüssel
Allgemein (Abstrakt):
- Suche in einer Menge nach einem bestimmten Element
Bei einer unsortierten Menge steht meist nur die elementeweise Suche (Lineare Suche) zur Verfügung.
Der Suchvorgang kann durch Vorsortierung (je nach Anzahl der Elemente) erheblich beschleunigt werden z.B. durch die Binäre Suche.
Sortieren
Zum Sortieren gibt es mehrere Algorithmen:
- Bubblesort
- Insertionsort
- Selectionsort
- Mergesort
- …
In der Übung wurde Bubblesort auf Integer- und String-Arrays angewendet:
public static void bubblesort(int[] a) {
for(int i = 1; i < a.length; i++)
for(int j = 0; j < a.length-i; j++)
if(a[j] > a[j+1]) swap(a,j,j+1);
}
public static void swap(int[] array, int indexA, int indexB) {
array[indexA] = array[indexA] + array[indexB];
array[indexB] = array[indexA] - array[indexB];
array[indexA] = array[indexA] - array[indexB];
}
Bsp:
42 33 14 50 7
33 14 42 7 || 50
14 33 7 || 42 50
14 7 || 33 42 50
7 || 14 33 42 50
public static void bubblesort(String[] a) {
for(int i = 1; i < a.length; i++)
for(int j = 0; j < a.length-i; j++)
if(a[j].compareTo(a[j+1])>0) swap(a,j,j+1);
}
public static void swap(String[] array, int indexA, int indexB) {
String tmp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = tmp;
}
Bsp:
"Tisch" "Tafel" "Wand" "arbeiten" "Abfall"
"Tafel" "Tisch" "Wand" "Abfall" || "arbeiten"
"Tafel" "Tisch" "Abfall" || "Wand" "arbeiten"
"Tafel" "Abfall" || "Tisch" "Wand" "arbeiten"
"Abfall" || "Tafel" "Tisch" "Wand" "arbeiten"
Zielsetzung für das Programmierpraktikum
- Suchen in Arrays
- Lineare Suche
- Binäre Suche
- Sortieren von Arrays
- Bubblesort
- Insertionsort
- Selectionsort
- zu betrachtende Datentypen der Arrays
- int
- String
- Testen auf Sortiertheit (isSorted)
page revision: 8, last edited: 05 Feb 2018 13:22