001 package de.hska.info1.suchen;
002
003 /**
004 * Zum Suchen des k-kleinsten Elements in einer ungeordneten Folge
005 * von Zahlen.
006 *
007 * @author Christian Pape
008 *
009 */
010 public class KKleinsteElement {
011
012
013 /**
014 * Gibt das k-kleinste Element der Folge zahlen zurück.
015 * Falls k kleiner 1 oder grösser der Anzahl Elemente in zahlen
016 * ist, wird Integer.MIN_VALUE zurückgegeben.
017 * @param k 1 <= k <= zahlen.length
018 */
019 public int getKKleinsteElement(int k, int [] zahlen) {
020 if ( 0 < k && k <= zahlen.length) {
021 return getKKleinsteElement1(k, zahlen, 0, zahlen.length - 1, 1);
022 }
023
024 return Integer.MIN_VALUE;
025 }
026
027
028 /**
029 * Gibt das k-Kleinste Element zurück.
030 * Falls k < 0 oder k > zahlen.length ist, dann
031 * gibt es eine IndexOutOfBoundException.
032 */
033 private int getKKleinsteElement(int k, int [] zahlen, int links, int rechts) {
034 int j = links;
035 int t = zahlen[j];
036 for (int i = links + 1; i <= rechts; i++) {
037 if (zahlen[i] < zahlen[j]) {
038 zahlen[j] = zahlen[i];
039 zahlen[i] = zahlen[j + 1];
040 zahlen[++j] = t;
041 }
042 }
043
044 if (j == k - 1) {
045 return t;
046 } else if (j > k - 1) {
047 return getKKleinsteElement(k, zahlen, links, j - 1);
048 } else {
049 return getKKleinsteElement(k, zahlen, j + 1, rechts);
050 }
051 }
052
053 /**
054 * Gibt das k-Kleinste Element in der Folge zahlen zurück, wobei
055 * nur die Teilfolge a[links], a[links+schrittweite], ... bis a[rechts] betrachtet wird.
056 * Falls k < 0 oder k > zahlen.length ist, dann
057 * gibt es eine IndexOutOfBoundException.
058 */
059 private int getKKleinsteElement1(int k, int [] zahlen, int links, int rechts, int schrittweite) {
060 int j = links;
061 int t = zahlen[j];
062 for (int i = links + schrittweite; i <= rechts; i += schrittweite) {
063 if (zahlen[i] < zahlen[j]) {
064 zahlen[j] = zahlen[i];
065 zahlen[i] = zahlen[j + schrittweite];
066 j += schrittweite;
067 zahlen[j] = t;
068 }
069 }
070
071 if (j == (k - 1) * schrittweite) {
072 return t;
073 } else if (j > (k - 1) * schrittweite) {
074 return getKKleinsteElement1(k, zahlen, links, j - schrittweite, schrittweite);
075 } else {
076 return getKKleinsteElement1(k, zahlen, j + schrittweite, rechts, schrittweite);
077 }
078 }
079
080 /**
081 * Gibt das k-Kleinste Element in der Folge zahlen zurück, wobei
082 * nur die Teilfolge a[links], a[links+schrittweite], ... bis a[rechts] betrachtet wird.
083 * Es wird so paritioniert und rekursiv weitergesucht, dass das Auswahlelement
084 * nicht mehr im linken und rechten Bereich vorkommt.
085 *
086 * Falls k < 0 oder k > zahlen.length ist, dann
087 * gibt es eine IndexOutOfBoundException.
088 */
089 public int getKKleinsteElement(int k, int [] zahlen, int offset, int links, int rechts, int schrittweite) {
090 int jl = links;
091 int jr = jl;
092 int t = zahlen[jl];
093 for (int i = links + schrittweite; i <= rechts; i += schrittweite) {
094 if (zahlen[i] < zahlen[jl]) {
095 zahlen[jl] = zahlen[i];
096 zahlen[i] = zahlen[jr + schrittweite];
097 zahlen[jr + schrittweite] = t;
098 jl += schrittweite;
099 jr += schrittweite;
100 } else if (zahlen[i] == zahlen[jr]) {
101 zahlen[i] = zahlen[jr + schrittweite];
102 zahlen[jr + schrittweite] = t;
103 jr += schrittweite;
104 }
105 }
106
107 if ( jr < offset + (k - 1) * schrittweite) {
108 return getKKleinsteElement(k, zahlen, offset, jr + schrittweite, rechts, schrittweite);
109 } else if (offset + (k - 1) * schrittweite < jl) {
110 return getKKleinsteElement(k, zahlen, offset, links, jl - schrittweite, schrittweite);
111 } else {
112 return t;
113 }
114 }
115
116 }