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.
Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | |||
pruefungen:bachelor:aud:loesungss07 [30.07.2012 10:53] – Ayane | pruefungen:bachelor:aud:loesungss07 [04.03.2020 13:26] (aktuell) – kat04 | ||
---|---|---|---|
Zeile 83: | Zeile 83: | ||
3|7(3)|-|1|4|-|2|5|6(4)|-| | 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, | ||
+ | System.out.println(quickSelect(array, | ||
+ | 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, | ||
+ | |||
+ | } | ||
+ | |||
+ | // 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, | ||
+ | quickSortAuf(a, | ||
+ | } | ||
+ | |||
+ | static int quickSelect(int a[], int r) { | ||
+ | int[] tmp = new int[a.length]; | ||
+ | System.arraycopy(a, | ||
+ | return quickSelect(tmp, | ||
+ | |||
+ | } | ||
+ | |||
+ | // 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> | ||
+ | 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, | ||
+ | quickSelect(a, | ||
+ | } | ||
+ | return a[r]; | ||
+ | |||
+ | } | ||