# 100. Element in unsortiertem Array finden



## kulturfenster (28. Jun 2007)

Hallo,
Ich habe die Aufgabe, in einem unsortieren Array das Element an der 100. Stelle in der sortierten Reihenfolge zu finden. Es sind also genau 99 Integers im gegebenen Array grösser als das zurückgebene Element. Der Algorithmus soll eine Komplexität von der Ordnung O(n) haben.

Dies ist mein Versuch:

```
package findeZahl;

public class Nr100 {

	public void get100(int[] a)
	{
		int nr100 = a[0];
		
		for(int i = 0; i < 100; i++) 
		{
			for(int j = 0; j < a.length-1; j++)
			{
				if(a[j] > a[j+1]) swap(a, j, j+1);
			}
		}
		
	}
	
	private void swap(int[] a, int x, int y)
	{
		int temp = a[x];
		a[x] = a[y];
		a[y] = temp;
		return;
	}
	
	public static void main(String[] args)
	{
		Nr100 n = new Nr100();
		java.util.Random generator = new java.util.Random();
		int[] a = new int[1000];
		for(int i = 0; i < a.length; i++) a[i] = generator.nextInt(1000);
		n.get100(a);
		for(int i = 0; i < a.length; i++) System.out.println("Stelle: " + i + " " +a[i]);
		System.out.println("Zahl an Stelle 100: " +a[100]);
		
	}
}
```
Wie ich herausgefunden habe, stimmt die Lösung nicht genau.

Hat jemand eine Idee, wie ich es besser machen könnte?
Vielen Dank schon im Voraus!


----------



## Marco13 (28. Jun 2007)

Das ist wohl das, was hier beschrieben ist: http://en.wikipedia.org/wiki/Selection_algorithm


----------



## kulturfenster (1. Jul 2007)

alles klar, vielen Dank!

Hier noch die Lösung:


```
public class Nr100 {

	public int get100(int[] a, int k)
	{
		for(int i = 0; i <= k; i++)
		{
			int minIndex = i;
			int minValue = a[i];
			for(int j = i+1; j < a.length; j++)
			{
				if(a[j] < minValue)
				{
					minValue = a[j];
					minIndex = j;
				}
			}
			swap(a,i, minIndex);
		}
		
		return a[k];
		
	}
	
	private void swap(int[] a, int i, int minIndex)
	{
		int temp = a[i];
		a[i] = a[minIndex];
		a[minIndex] = temp;
	}
	
	public static void main(String[] args)
	{
		Nr100 n = new Nr100();
		java.util.Random generator = new java.util.Random();
		int[] a = new int[1000];
		for(int i = 0; i < a.length; i++) a[i] = generator.nextInt(1000);
		System.out.println("Nr 100: " + n.get100(a,100));
		
		
		//for(int i = 0; i < a.length; i++) System.out.println("Stelle: " + i + " " +a[i]);	
	}
}
```


----------

