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    42     14      7    ||     50
33    14     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)