/**
 * AlgDs, WS99, Aufgabe 24.
 * Studenten sortieren.
 *
 * @author Christian Semrau, 28.11.1999, 25.12.1999
 * <a href="mailto:Christian.Semrau@Student.uni-magdeburg.de">
 * Christian.Semrau@Student.uni-magdeburg.de</a>
 */
class ChS_Student {
  String nachname, vorname; int matnr;

// ChS_Student constructor.
public ChS_Student(String nach, String vor, int mat) {
  nachname = nach; vorname = vor; matnr = mat;
}

// -1 wenn this < s, 0 wenn this==s, +1 wenn this > s
public int compareTo(ChS_Student s) {
  // Komplettvergleich: nachname, vorname, matnr
  int cn = nachname.compareTo(s.nachname);
  if (cn!=0) return cn; else{
	int cv = vorname.compareTo(s.vorname);
	if (cv!=0) return cv; else
	  return (matnr - s.matnr);
  }
}

// Compares two objects for equality.
// true if these Objects are equal; false otherwise.
public boolean equals(Object obj) {
  // NOTE: obj might be an instance of any class
  if ((obj != null) && (obj instanceof ChS_Student)) {
	 return toString() == ((ChS_Student)obj).toString();
  }else return false;
}

public static void main(java.lang.String[] args) {
  ChS_Student[] stud = new ChS_Student[5];

  stud[0] = new ChS_Student("Trug","Rainer B.",314159);
  stud[1] = new ChS_Student("Putze","Karl",271828);
  stud[2] = new ChS_Student("Wurstl","Hansi",125992);
  stud[3] = new ChS_Student("Silie","Peter",141421);
  stud[4] = new ChS_Student("Wurstl","Hansi",173205);
  studentOut(stud); System.out.println();

  sortQuick(stud);
  studentOut(stud); System.out.println();

  ChS_Student[] stud2 = new ChS_Student[8];
  for(int i=0; i<stud.length; i++) stud2[i]=stud[i];
  stud = stud2;
  stud[5] = new ChS_Student("Konda","Anna",123435);
  stud[6] = new ChS_Student("Bolika","Anna",123243);
  stud[7] = new ChS_Student("Babbage","Charles",13);

  sortInsertion(stud);
  studentOut(stud); System.out.println();
}

public static void sortInsertion(ChS_Student[] feld) {
  for (int i = 1; i < feld.length; i++){
	int marker = i;
	ChS_Student temp = feld[i];
	//fuer alle Elemente links vom Marker-Feld
	while (marker > 0 && (feld[marker - 1].compareTo(temp)>0)) {
	  // verschiebe alle groesseren Element nach hinten
	  feld[marker] = feld[marker - 1]; marker--;
	}
	//setze temp auf das freie Feld
	if (marker!=i) feld[marker] = temp;
  }
}

static void sortQuick (ChS_Student[] array) {
  sortQuick2(array, 0, array.length - 1);
}

static void sortQuick2(ChS_Student[] array, int l, int r) {
  int lo = l,hi = r;
  if (hi > lo) {
	// Pivotelement bestimmen
	ChS_Student mid = array[(lo + hi) / 2];
	while (lo <= hi) {
	  while ((lo < r) && (array[lo].compareTo(mid)<0)) lo++;
	  while (( hi > l ) && ( array[hi].compareTo(mid)>0)) hi--;
	  if (lo <= hi) {
		if (lo < hi) swap(array, lo, hi);
		lo++; hi--;
	  }
	}
	// linke Partition sortieren
	if (l < hi) sortQuick2(array, l, hi);
	// rechte Partition sortieren
	if (lo < r) sortQuick2(array, lo, r);
  }
}

// Gibt das Studentenfeld auf die Konsole aus.
public static void studentOut(ChS_Student[] stud) {
  for(int i=0; i<stud.length; i++) System.out.println(stud[i]);
}

static void swap (ChS_Student[] array, int idx1, int idx2) {
  ChS_Student tmp = array[idx1];
  array[idx1] = array[idx2];
  array[idx2] = tmp;
}

// Returns a String that represents the value of this object.
public String toString() {
  return nachname+", "+vorname+", ("+matnr+")";
}
} // class ChS_Student