class IntSorter{ private static void swap(int[] a, int i, int k){ int temp = a[i]; a[i] = a[k]; a[k] = temp; } static boolean isSorted(int[] a, int lo, int hi){ for (int k= lo; k a[k+1]) return false; return true; } static boolean isSorted(int[] a){ return isSorted(a, 0, a.length-1); } static void javaSort(int[] a){ java.util.Arrays.sort(a); } static void bubbleSort1(int[] a){ int hi = a.length-1; for (int k = hi; k > 0; k--) for (int i = 0; i < k; i++) if ( a[i] > a[i+1]) swap (a, i, i+1); } static void bubbleSort2(int[] a){ int hi = a.length-1; for (int k = hi; k > 0; k--){ boolean test = true; for (int i = 0; i < k; i++) if ( a[i] > a[i+1]) { swap (a, i, i+1); test = false;} if (test) break; } } static void bubbleSort3(int[] a){ int hi = a.length-1; int k = hi; while ( k > 0 ){ int maxSwap = 0; for (int i = 0; i < k; i++) if ( a[i] > a[i+1]) { swap (a, i, i+1); maxSwap = i;} k = maxSwap; } } private static int minPos(int[] a, int lo, int hi){ int Min = lo; for (int i = lo+1; i <= hi; i++) if (a[i] < a[Min]) Min = i; return Min; } static void selectionSort(int[] a){ int hi = a.length-1; for (int k = 0; k < hi; k++){ int Min = minPos(a, k, hi); if ( Min != k) swap (a, Min, k); } } static void insertionSort(int[] a){ int hi = a.length-1; for (int k = 1; k <= hi; k++) if (a[k] < a[k-1]){ int x = a[k]; int i; for ( i = k; ( (i > 0) && (a[i-1] > x) ) ; i-- ) a[i] = a[i-1]; a[i] = x; } } static void shellSort(int[] a){ int hi = a.length-1; int hmax, h ; for ( hmax = 1; hmax < hi ; hmax = 3*hmax+1 ); for ( h = hmax/3; h > 0; h /= 3) for (int k = h; k <= hi; k++) if (a[k] < a[k-h]){ int x = a[k]; int i; for ( i = k; ( (i > (h-1)) && (a[i-h] > x) ) ; i-=h ) a[i] = a[i-h]; a[i] = x; } } static void quickSort(int[] a){ int hi = a.length-1; rekQuickSort(a, 0, hi); } static void rekQuickSort(int[] a, int lo, int hi){ int li = lo; int re = hi; int mid = (li+re)/2; if (a[li] > a[mid]) swap(a, li, mid); if (a[mid] > a[re]) swap(a, mid, re); if (a[li] > a[mid]) swap(a, li, mid); // <= 3 Elemente haben wir schon sortiert ! // > 3 Elemente müssen noch sortiert werden ! if ((re - li) > 2){ int w = a[mid]; do{ while (a[li] < w) li++; while (w < a[re]) re--; if (li <= re){ swap(a, li, re); li++; re--;} }while (li <= re); if (lo < re) rekQuickSort(a, lo, re); if (li < hi) rekQuickSort(a, li, hi); } } static void quickSort2(int[] a){ int hi = a.length-1; rekQuickSort2(a, 0, hi); } static void rekQuickSort2(int[] a, int lo, int hi){ int li = lo; int re = hi; int mid = (li+re)/2; if (a[li] > a[mid]) swap(a, li, mid); if (a[mid] > a[re]) swap(a, mid, re); if (a[li] > a[mid]) swap(a, li, mid); // <= 3 Elemente haben wir schon sortiert ! // > 3 Elemente müssen noch sortiert werden ! if ((re - li) > 2){ int pivot = a[mid]; swap(a, mid, re); int k = li; for (int i= li; i < hi; i++){ if (a[i] < pivot)swap(a,i,k++); } swap(a,k,re); re = k-1; li = k+1; if (lo < re) rekQuickSort2(a, lo, re); if (li < hi) rekQuickSort2(a, li, hi); } } static int [] temp; static void mergeSort(int[] a){ int hi = a.length-1; temp = new int [hi+1]; rekMergeSort(a, 0, hi); } static void rekMergeSort(int[] a, int lo, int hi){ if (lo >= hi) return; if ((hi - lo) <= 2){ int mid = (hi+lo)/2; if (a[lo] > a[mid]) swap(a, lo, mid); if (a[mid] > a[hi]) swap(a, mid, hi); if (a[lo] > a[mid]) swap(a, lo, mid); } else { // mehr als 3 Elemente int mid = (lo + hi +1)/2; int len = hi-lo+1; rekMergeSort(a, lo, mid-1); rekMergeSort(a, mid, hi); for (int k=0, li=lo, re=mid; k < len; k++) if ((li < mid) && ((re > hi) ||(a[li] < a[re]))) // links gewinnt temp[k] = a[li++]; else temp[k] = a[re++]; //for (int i=0; i < len; i++) a[lo+i] = temp[i]; System.arraycopy(temp,0,a,lo,len); } } static void downHeap(int[] a, int i, int m){ int sonny = 2*i + 1; while (sonny <= m){ if ((sonny < m) && (a[sonny] < a[sonny+1])) sonny++; // Linker oder rechter Zweig if (a[i] < a[sonny]) { // tauschen ? swap(a, i, sonny); i = sonny; sonny += sonny + 1; } else break; } } static void heapSort(int[] a){ int hi = a.length-1; for (int i = hi/2; i >= 0; i--) downHeap(a, i, hi); for (int i = hi; i > 0; i--) { swap(a, i, 0); downHeap(a, 0, i-1);} } static void distributionSort(int[] a){ int hi = a.length-1; int[] b = new int[hi+1]; int[] count = new int[256]; // Byte 1 By1(x) = (x & 0xff) for (int i=0; i < 256; i++) count[i] = 0; for (int i=0; i <= hi; i++) // Zählen count[ a[i] & 0xff]++; for (int i=1; i < 256; i++) // aufsummieren count[i] += count[i-1]; for (int i = hi; i >= 0; i--) // Verteilen b[--count[a[i]& 0xff]] = a[i]; // for (int i=0; i <= hi; i++) a[i] = b[i]; System.arraycopy(b, 0, a, 0, hi+1); // Byte 2 By2(x) = ((x >> 8) & 0xff) for (int i=0; i < 256; i++) count[i] = 0; for (int i=0; i <= hi; i++) // Zählen count[ (a[i] >> 8) & 0xff]++; for (int i=1; i < 256; i++) // aufsummieren count[i] += count[i-1]; for (int i = hi; i >= 0; i--) // Verteilen b[--count[(a[i] >> 8) & 0xff]] = a[i]; // for (int i=0; i <= hi; i++) a[i] = b[i]; System.arraycopy(b, 0, a, 0, hi+1); // Byte 3 By3(x) = ((x >> 16) & 0xff) for (int i=0; i < 256; i++) count[i] = 0; for (int i=0; i <= hi; i++) // Zählen count[ (a[i] >> 16) & 0xff]++; for (int i=1; i < 256; i++) // aufsummieren count[i] += count[i-1]; for (int i = hi; i >= 0; i--) // Verteilen b[--count[(a[i] >> 16) & 0xff]] = a[i]; // for (int i=0; i <= hi; i++) a[i] = b[i]; System.arraycopy(b, 0, a, 0, hi+1); // Byte 4 By4(x) = ((x >> 24) & 0xff) for (int i=0; i < 256; i++) count[i] = 0; for (int i=0; i <= hi; i++) // Zählen count[ (a[i] >> 24) & 0xff]++; for (int i=1; i < 256; i++) // aufsummieren count[i] += count[i-1]; for (int i = hi; i >= 0; i--) // Verteilen b[--count[(a[i] >> 24) & 0xff]] = a[i]; // for (int i=0; i <= hi; i++) a[i] = b[i]; System.arraycopy(b, 0, a, 0, hi+1); } }