Suchen und Sortieren

Question 1

Sequentielle Suche

Answer 1

Indexpositionen des Feldes werden der Reihe nach betrachtet.

Werte werden mit dem Gesuchten verglichen.

Question 2

Sequentielle Suche Voraussetzung

Answer 2

keine, Feld kann unsortiert sein

Question 3

Sequentielle Suche Laufzeitanalyse

Answer 3

bester Fall: 1
schlechtester Fall: n
Durchschnitt: (n + 1) / 2

Question 4

Sequentielle Suche Java Quelltext

Answer 4

public class SeqSearch {
   public static final int NO_KEY = -1;

   public static int search(int[] array, int key) {
        for (int i = 0; i < array.length; i++) {
              if (array[i] == key) {
                   return i;
               }
         }
         return NO_KEY;
   }
}

Question 5

Binäre Suche

Answer 5

In jedem Schritt wird der Wert in der Mitte des betrachteten Feldbereichs mit dem gesuchten Wert verglichen. Falls diese nicht übereinstimmen, wird die Suche in der linken bzw. rechten Hälfte des Feldbereichs fortgesetzt – abhängig davon, in welcher Hälfte sich der gesuchte Wert aufgrund der Sortierung des Felds befinden muss.

Question 6

Binäre Suche Voraussetzung

Answer 6

Feld muss aufsteigend sortiert sein

Question 7

Binäre Suche Laufzeitanalyse

Answer 7

bester Fall: 1
schlechtester Fall: log2 (n)
Durchschnitt: log2 (n)

Question 8

Binäre Suche Java Quelltext

Answer 8

public class BinarySearch {
   public static final int NO_KEY = -1;

   public static int search(int[] array, int key) {
       int u = 0, o = array.length - 1;
       while (u <= o) {
          int m = (u + o) / 2;
          if (array[m] == key) {
              return m;
          } else if (key < array[m]) {
              o = m - 1;
          } else {
              u = m + 1;
          }
       }
       return NO_KEY;
   }
}

Question 9

Vergleich Binäre Suche vs. Sequentielle Suche

Answer 9

Verfahren  10   10^2   10^3   10^4
sequentiell (n/2)
≈ 5
≈ 50
≈ 500
≈ 5.000
binär (log2n)
≈ 3,3
≈ 6,6
≈ 10,0
≈ 13,3

Question 10

InsertionSort

Answer 10

Array imaginär in zwei Felder aufgeteilt:

• sortiert
• unsortiert

erstes Element des unsortierten Feldes wird in die richtige Stelle in dem sortierten Feld eingefügt

Question 11

InsertionSort Beispiel:

1 | 5 8 3 9 2

Answer 11

1 5 | 8 3 9 2

1 5 8 | 3 9 2

1 3 5 8 | 9 2

1 3 5 8 9 | 2

1 2 3 5 8 9

Question 12

SelectionSort

Answer 12

Array imaginär in zwei Felder aufgeteilt:

• sortiert
• unsortiert

kleinstes Element des unsortierten Feldes an das sortierte Feld dranhängen

Question 13

SelectionSort Beispiel:

1 | 5 8 3 9 2

Answer 13

1 | 5 8 3 9 2

1 2 | 5 8 3 9

1 2 3 | 5 8 9

1 2 3 5 | 8 9

1 2 3 5 8 | 9

1 2 3 5 8 9

Question 14

BubbleSort

Answer 14

1. Die nebeneinanderliegenden Werte werden miteinander verglichen und gegeben Falls getauscht
2. Das wird solang wiederholt, bis man am Ende des Feldes angekommen ist
3. Das ganze wiederholt man solange, bis in so einem Durchgang nichts mehr getauscht wurde

Question 15

BubbleSort Beispiel:

1 5 8 3 9 2

Answer 15

1 5 3 8 2 9

1 3 5 2 8 9

1 3 2 5 8 9

1 2 3 5 8 9

Question 16

QuickSort

Answer 16

rekursives Verfahren

Question 17

Vergleich Aufwand Sortieralgorythmen

Answer 17

InsertionSort: n^2
SelectionSort: n^2
BubbleSort: n^2
QuickSort: n * log2 (n)

Question 18

QuickSort Beispiel:

1 5 8 3 9 2

Answer 18

1.) ganze liste:
1 5 8 3 9 2
Pivotelement: 8

(1 5 2 3) (9 8)

links: keine größeren Elemente als das Pivotelement
rechts: keine kleineren Elemente als das Pivotelement

2.) linke Hälfte:
1 5 2 3
Pivotelement: 5

1 3 2 5

3.) linke Hälfte:
1 3 2
Pivotelement: 3

1 2 3

4.) linke Hälfte:
1 2
Pivotelement: 1

1 2

2.) rechte Hälfte:
9 8
Pivotelement: 9

8 9