Institut für Informatik
Prof. Dr. Oliver Vornberger
Ann-Katrin Becker, M.Sc.
Nils Haldenwang, M.Sc.
Universität Osnabrück, 24.11.2015
http://www-lehre.inf.uos.de/~ainf
Testat bis 02.12.2015, 14:00 Uhr
Übungen zu Algorithmen
Wintersemester 2015/2016
Blatt 7: Suchen und Sortieren I
Aufgabe 7.1: Fragen (30 Punkte)
Beantworten Sie Ihrer Tutorin beziehungsweise Ihrem Tutor Fragen zu den Inhalten der Veranstaltung.
Aufgabe 7.2: Sortieren (20 Punkte)
Gegeben sei die Zahlenfolge 7, 4, 6, 8, 9, 1, 3, 2, die aufsteigend sortiert werden soll. Stellen Sie die
Arbeitsweise der folgenden Sortieralgorithmen durch geeignete Zwischenergebnisse dar.
a) SelectionSort
b) BubbleSort
c) QuickSort
d) MergeSort
Machen Sie bei der Darstellung des QuickSort deutlich, in welchen Grenzen aktuell sortiert wird,
welches das aktuelle Pivot-Element ist und wann neue Sortier-Vorgänge mit neuen Grenzen erfolgen.
Musterlösung:
a) SelectionSort:
7
1
1
1
1
1
1
1
4
4
2
2
2
2
2
2
6
6
6
3
3
3
3
3
8
8
8
8
4
4
4
4
9
9
9
9
9
6
6
6
1
7
7
7
7
7
7
7
3
3
3
6
6
9
9
8
2
2
4
4
8
8
8
9
b) BubbleSort:
7
4
4
4
4
4
4
7
6
6
6
6
6
6
7
7
7
7
8
8
8
8
8
8
9
9
9
1
1
1
1
1
1
9
3
3
3
3
3
3
9
2
2
2
2
2
2
9
4 6 7 8 1 3 2 9
4 6 7 1 8 3 2 9
4 6 7 1 3 8 2 9
4 6 7 1 3 2 8 9
4
4
4
4
6
6
6
6
7
1
1
1
1
7
3
3
3
3
7
2
2
2
2
7
8
8
8
8
9
9
9
9
4
4
4
4
6
1
1
1
1
6
3
3
3
3
6
2
2
2
2
6
7
7
7
7
8
8
8
8
9
9
9
9
4
1
1
1
1
4
3
3
3
3
4
2
2
2
2
4
6
6
6
6
7
7
7
7
8
8
8
8
9
9
9
9
1 3 2 4 6 7 8 9
1 2 3 4 6 7 8 9
1 2 3 4 6 7 8 9
1 2 3 4 6 7 8 9
c) QuickSort:
Sortiere Teilfolge zwischen Index 0, 7
i
x
j
7 4 6 8 9 1 3 2
Tausche 8 und 2
i
j
7 4 6 8 9 1 3 2
i
j
7 4 6 2 9 1 3 8
Tausche 9 und 3
i
j
7 4 6 2 9 1 3 8
i
j
7 4 6 2 3 1 9 8
Sortiere Teilfolge zwischen Index 0, 5
2
i
x
j
7 4 6 2 3 1 9 8
Tausche 7 und 1
i
j
7 4 6 2 3 1 9 8
i
j
1 4 6 2 3 7 9 8
Tausche 6 und 3
i
j
1 4 6 2 3 7 9 8
i
j
1 4 3 2 6 7 9 8
Sortiere Teilfolge zwischen Index 0, 3
i
x
j
1 4 3 2 6 7 9 8
Tausche 4 und 2
i
j
1 4 3 2 6 7 9 8
i
j
1 2 3 4 6 7 9 8
Sortiere Teilfolge zwischen Index 0, 2
i
x
j
1 2 3 4 6 7 9 8
Tausche 2 und 2
i
j
1 2 3 4 6 7 9 8
i
j
1 2 3 4 6 7 9 8
Sortiere Teilfolge zwischen Index 4, 5
i
3
x
j
1 2 3 4 6 7 9 8
Tausche 6 und 6
i
j
1 2 3 4 6 7 9 8
i
j
1 2 3 4 6 7 9 8
Sortiere Teilfolge zwischen Index 6, 7
i
x
j
1 2 3 4 6 7 9 8
Tausche 9 und 8
i
j
1 2 3 4 6 7 9 8
i
j
1 2 3 4 6 7 8 9
d) MergeSort:
7 4 6 8 9 1 3 2
7 4 6 8
9 1 3 2
7 4 6 8
7 4
6 8
7 4
7
4
7
4
4 7
6 8
6
8
6
8
6 8
4 6 7 8
9 1 3 2
9 1
4
3 2
9 1
9
1
9
1
1 9
3 2
3
2
3
2
2 3
1 2 3 9
1 2 3 4 6 7 8 9
Aufgabe 7.3: MergeSort Rekursiv (25 Punkte)
Schreiben Sie eine Klasse MergeSort mit der Methode
public static int[] sortRekursiv(int[] a)
die ein Array a beliebiger Länge nach der Methode des MergeSort rekursiv sortiert und das sortierte
Array zurückliefert. Kopieren Sie dazu die Methode merge(int[],int[]) aus der im Anhang
befindlichen Klasse Merge.java in Ihre neue Klasse.
Sollte die Länge n des übergebenen Arrays nicht ohne Rest durch zwei teilbar sein, teilen Sie es
ungleichmäßig in ein Array der Länge b 2n c und ein Array der Länge d n2 e auf.
Ergänzen Sie Ihre Klasse um eine private Klassenvariable int schritte, mit der Sie die Anzahl
der durchgeführten relevanten Arbeitsschritte des Sortierverfahrens approximieren. Die relevanten
Arbeitsschritte in dieser Implementierung sind die Kopiervorgänge für die einzelnen Array-Elemente
bei der Durchführung der merge-Operation. Erhöhen Sie die Variable in der Methode merge für
jeden Arbeitsschritt um 1.
Schreiben Sie eine main-Methode, die ein int-Array einliest, dieses mit der obigen Methode sortiert,
das Ergebnis ausgibt und die Anzahl der durchgeführten Schritte anzeigt.
5
Musterlösung:
/******************************
MergeSort.java
******************************/
import AlgoTools.IO;
/**
* Sortierung eines Arrays von beliebig vielen Elementen mit dem rekursiven
* Mergesort-Algorithmus.
*/
public class MergeSortRekursiv {
private static int schritte;
/**
* Methode, die den rekursiven MergeSort implementiert.
*
* @param a
zu sortierendes Array, wird innerhalb der Methode nicht veraendert
*
* @return sortiertes Array
*/
public static int[] sortRekursiv(int[] a) {
int l = a.length / 2;
// Laenge der beiden Teilfolgen
if (l == 0)
return a;
// eine einelementige Folge ist sortiert
int[] b = new int[l];
int[] c = new int[a.length - l];
// die beiden Teilfolgen
for (int i = 0; i < l; i++) {
// kopiere a in die Teilfolgen
// 1. Haelfte nach b
b[i] = a[i];
}
for (int i = l; i < a.length; i++) {
c[i - l] = a[i];
// 2. Haelfte nach c
}
// zurueckgegeben werden die beiden sortierten Teilfolgen gemischt
return merge(sortRekursiv(b), sortRekursiv(c));
}
/**
* Mischt zwei sortierte Arrays mit einer Laengendifferenz
6
* von 0 oder 1 zu einem sortierten Array
*
* @param a Array a, wird nicht veraendert
* @param b Array b, wird nicht veraendert
*
* @return gemischtes, sortiertes Array
*/
public static int[] merge (int[]a, int[]b) {
// mischt a und b
// liefert Ergebnis zurueck
int i=0, j=0, k=0;
int[] c = new int[a.length + b.length];
// Laufindizes
// Platz fuer Folge c besorgen
while ((i<a.length) && (j<b.length)) {
// mischen, bis ein Array leer
schritte++;
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
// jeweils das kleinere Element
// wird nach c uebernommen
}
// ggf.: Rest von Folge a
while (i<a.length){
schritte++;
c[k++] = a[i++];
}
// ggf.: Rest von Folge b
while (j<b.length){
schritte++;
c[k++] = b[j++];
}
return c;
// Ergebnis abliefern
}
/**
* Liest ein int-Array ein und gibt es unter Angabe der Schrittzahl
* sortiert wieder aus.
*/
public static void main(String argv[]) {
schritte = 0;
int[] a;
7
//Einlesen
do {
a = IO.readInts("Bitte die Zahlen: ");
} while(a.length == 0);
//Sortieren
a = sortRekursiv(a);
//Ausgabe
IO.println("Die sortierte Folge:");
for(int i = 0; i < a.length; i++) {
IO.print(a[i] + " ");
}
//Schrittzahl
IO.println("\nMit Anzahl Schritten: " + schritte);
}
}
Aufgabe 7.4: PancakeSort (25 Punkte)
Vervollständigen Sie die im Anhang befindliche Klasse PancakeSort. In dieser Klasse soll ein
Sortieralgorithmus implementiert werden, der auch unter dem Namen Pancake Sort bekannt ist.
Die Besonderheit hierbei ist, dass Sie auf dem zu sortierenden Array nur eingeschränkte Operationen durchführen können. Sie können die Werte des Array ganz normal lesen, allerdings nicht beliebig schreiben. Es gibt nur eine Möglichkeit, das Array überhaupt zu verändern: Mit der Methode
flip(int[] array, int count). Diese Methode dreht die Reihenfolge der ersten count
Elemente im Array um. So verändert sich das Array
6 7 8 9 2 5 3 4 1 durch den Aufruf von flip(array, 4) zu
9 8 7 6 2 5 3 4 1.
Der Name kommt durch folgende Analogie: Man stelle sich das Array als Haufen von Pfannkuchen
vor, wobei das erste Element des Arrays ganz oben liegt. Die einzige Möglichkeit, den Stapel zu
verändern, ist, einen Pfannenheber unter einen Pfannkuchen zu schieben und alle darüberliegenden
Pfannkuchen einmal umzudrehen.
Ihre Aufgabe ist nun, sich zu überlegen, wie Sie das Array mit den gegebenen Einschränkungen sortieren können. Gehen Sie dazu wie folgt vor: Implementieren Sie zuerst die Methode printArray
(Javadoc beachten!). Implementieren Sie als nächstes die Methode flip entsprechend der obigen Beschreibung bzw. der zugehörigen Beschreibung im Javadoc. Danach vervollständigen Sie die main
Methode, in der zuerst ein Array eingelesen, dann mit der Methode sort sortiert und am Ende ausgegeben wird. Zum Schluss müssen Sie natürlich noch die Methode sort mit Leben füllen, damit sie
ihre Funktion erfüllt. Achten Sie darauf, dass Sie den Inhalt des Arrays nur durch Aufruf von flip
verändern!
8
Machen Sie sich außerdem Gedanken dazu, in welcher Laufzeitklasse Ihr Algorithmus liegt und formulieren Sie schriftlich eine Begründung für ihre Behauptung.
Musterlösung:
import AlgoTools.IO;
public class PancakeSortLsg {
/**
* Dreht die Reihenfolge der ersten <tt>count</tt> Element in
* <tt>array</tt> um.
*
* @param array das zu sortierende Array
* @param count Anzahl zu flippender Elemente
*
* @throws RuntimeException wenn <tt>count</tt> > <tt>array.length</tt>
*/
public static void flip(int[] array, int count) {
// Maximal alle Elemente flippen
if (count > array.length) {
throw new RuntimeException("Count muss <= array.length sein!");
}
for (int i = 0; i < count/2; i++) {
int tmp = array[i];
array[i] = array[count - 1 - i];
array[count - 1 - i] = tmp;
}
}
/**
* Gibt ein Array auf dem Terminal aus
*
* @param array Das auszugebene Array
*/
public static void printArray(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
IO.print(array[i] + ", ", 5);
}
IO.println(array[array.length - 1], 3);
}
/**
* Sortiert das gegebene <tt>array</tt> mit dem PancakeSort Verfahren
*
* @param array zu sortierendes Array
*/
9
public static void sort(int[] array) {
// Von hinten alle Stellen mit den größten Elementen auffüllen
for (int end = array.length; end > 1; end--) {
// Maximum im unsortierten Teil finden
int max = array[0];
int maxPos = 0;
for (int i = 1; i < end; i++) {
if (array[i] > max) {
max = array[i];
maxPos = i;
}
}
// Erst das Maximum nach vorne flippen ...
flip(array, maxPos + 1);
// ... danach den ganzen unsortierten Teil flippen, um das Maximum
// ans Ende des unsortierten Teils zu bekommen.
flip(array, end);
}
}
public static void main(String[] args) {
int[] input = IO.readInts("Bitte eine Zahlenfolge eingeben: ");
IO.print("Eingabe : ");
printArray(input);
sort(input);
IO.print("Sortiert: ");
printArray(input);
}
}
10
© Copyright 2024 ExpyDoc
