Prüfungsfrage 09 – n kleinste Elemente eines Feldes

 

Gegeben ist ein Feld mit n unsortierten Einträgen \left( {{x_i}} \right),\:\:i \in \mathbb{N}. Geben Sie einen Algorithmus an (in Pseudocode oder einer gängigen Programmiersprache), mit der die m kleinsten Einträge des Feldes gefunden werden können \left( {0 < m < n} \right), ohne dass das Feld komplett sortiert wird. Welche Rechenzeitkomplexität besitzt der von Ihnen angegebene Algorithmus?

Lösung

public class Suche {
	public static void main(String[] args) {
		double x[] = {10, 12, 50, 5, 13, 6, 8, 11};
		double Min = Double.POSITIVE_INFINITY;
		double LastMin = Double.NEGATIVE_INFINITY;
		int m = 3;
		int n = x.length;
		for (int j = 0; j < m ; j++){
			for (int i = 0; i < n ; i++)
				if (x[i] < Min && x[i] > LastMin)
					Min = x[i];
			LastMin = Min;
			Min = Double.POSITIVE_INFINITY;
			System.out.print(LastMin+" ; ");
		}
	}
}

Liefert: 5.0 ; 6.0 ; 8.0 ;

Rechenzeitkomplexität wäre allerdings: O\left( {m \cdot n} \right)

Ein besserer Algorithmus hat den Aufwand n:

sortiere den Vektor x im Bereich [0, m]
für i = m bis n
	tausche x[i] mit x[m]
	j = m
	solnge j > 0 und x[j-1] > x[j]
		tausche x[j-1] mit x[j]
		-- j