Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forum   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung
Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungss07 [21.02.2012 17:06] LaCucarachapruefungen:bachelor:aud:loesungss07 [04.03.2020 13:26] (aktuell) kat04
Zeile 1: Zeile 1:
 === Forum === === Forum ===
-  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8853-Klausur-17-9-07]] +  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8853-Klausur-17-9-07]] A3,A1 
 +  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8883-17-09-2007-Aufgabe-5-ADT-Warteschlange]]
 ==== Lösungsversuch ==== ==== Lösungsversuch ====
  
Zeile 28: Zeile 28:
 richtig richtig
  
-falsch+falsch - eher richtig, siehe [[https://fsi.informatik.uni-erlangen.de/forum/thread/8853-Klausur-17-9-07]]
  
 falsch falsch
Zeile 82: Zeile 82:
 **e)**  **e)** 
  
- / 7|4(8)| |1|3(1)| |2|5|6| |+  3|7(3)|-|1|4|-|2|5|6(4)|-| 
 +   
 + === Aufgabe 6 - QuickSort ===  
 + 
 +  public class QuickSort { 
 + 
 + public static void main(String[] args) { 
 + 
 + int[] array = { 20, 35, -15, 7, 55, 1, -22,56,-8,100,-202 }; 
 + System.out.println(quickSelect(array, 6)); 
 + quickSort(array); 
 +  
 +  
 + 
 +  
 +
 + 
 + // v e r t a u s c h t zwei Positionen e i n e r Reihung 
 + static void swap(int a[], int i, int j) { 
 + int t = a[i]; 
 + a[i] = a[j]; 
 + a[j] = t; 
 +
 + 
 + // s o r t i e r t di e komplette Reihung 
 + static void quickSort(int a[]) { 
 + quickSortAuf(a, 0, a.length - 1); 
 + 
 +
 + 
 + // s o r t i e r t den Bereich von s t a r t b i s end ( i n k l u s i v e ) 
 + static void quickSortAuf(int a[], int start, int end) { 
 +  
 + if (start >= end) { 
 + return; 
 +
 + int pivot = a[start]; 
 + int i = start; 
 + int k = end; 
 + while (i < k) { 
 + while (i < k && a[i] < pivot) 
 + i++; 
 + while (i < k && a[k] > pivot) 
 + k--; 
 + if (i < k) { 
 + swap(a, i, k); 
 +
 +
 + 
 + quickSortAuf(a, start, i); 
 + quickSortAuf(a, i + 1, end); 
 +
 + 
 + static int quickSelect(int a[], int r) { 
 + int[] tmp = new int[a.length]; 
 + System.arraycopy(a, 0, tmp, 0, a.length); 
 + return quickSelect(tmp, 0, tmp.length - 1, r); 
 + 
 +
 + 
 + // sucht im Bereich von s t a r t b i s end ( i n k l u s i v e ) 
 + // nach dem rg r o e s s t e n Element 
 + static int quickSelect(int a[], int start, int end, int r) { 
 + System.out.println(Arrays.toString(a)); 
 + if(r>=start && r <= end && start <end) { 
 + int pivot = a[start]; 
 + int i = start; 
 + int k = end; 
 + while (i < k) { 
 + while (i < k && a[i] < pivot) 
 + i++; 
 + while (i < k && a[k] > pivot) 
 + k--; 
 + if (i < k) { 
 + swap(a, i, k); 
 +
 +
 + quickSelect(a, start, i,r); 
 + quickSelect(a, i+1, end,r); 
 +
 + return a[r]; 
 +  
 + }