# Array sortieren



## TimN (31. Mai 2007)

Hallo,

ich habe ein Array zufällig mit den Zahlen 0 und 1 gefüllt( z.B. {0, 1, 1, 1, 0, 0, 1} )
Jetzt möchte ich dieses Array sortieren. Also {0, 0, 0, 1, 1, 1, 1} soll herauskommen.
Wichtig: Der Sortieralgorithmus soll einen Aufwand von O haben. Habt ihr da eine Idee?
Meine Idee war folgende: Zwei Arrays anlegen, alle nullen in den einen und alle einen in den anderen kopieren. Dann die beiden Arrays hintereinander in den Anfangsarray kopieren. Aber irgendwie wollte das nicht funktionieren.

Eine andere Möglichkeit wäre natürlich, wenn man alle Nullen und Einsen zählt und dann in ein Array schreibt. aber ich glaube nicht, das das die gesuchte Lösung ist...


----------



## zerix (31. Mai 2007)

Hallo,

ich bin mir nicht sicher, aber ich glaube Java kann schon von Haus aus soritieren, weiß aber leider auch nicht wie. Vielleicht weiß es einer und postet es, aber solange kannst du dir ja mal diese Seite anschauen.

http://www.wissensbasar.de/andreas/wi5/java/wirth/Sort/sorting.html

MFG

zEriX


----------



## Matthias Reitinger (31. Mai 2007)

Hallo,

spontane Idee:

Zwei Indexzähler i = 0 und j = arr.length-1 definieren, neues Array sorted gleicher Größe anlegen
Zu sortierendes Array durchlaufen:
Ist aktuelles Element eine 0, schreibe in sorted[ i ] eine 0 und inkrementiere i
Ist aktuelles Element eine 1, schreibe in sorted[ j ] eine 1 und dekrementiere j

Sollte funktionieren und auch in O liegen.

Grüße,
Matthias


----------



## Thomas Darimont (31. Mai 2007)

Hallo,

schau mal hier:

```
/**
 * 
 */
package de.tutorials;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Tom
 * 
 */
public class SpecialCaseExample {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] numbers = generateRandomZerosOrOnes(10);
        System.out.println(Arrays.toString(numbers));
        numbers = sort(numbers);
        System.out.println(Arrays.toString(numbers));
    }

    private static int[] sort(int[] numbers) {
        int[] newNumbers = new int[numbers.length];
        for (int i = 0,j=numbers.length-1; i < numbers.length; i++) {
            if(numbers[i] == 1){
                newNumbers[j--] = 1;
            }
        }
        return newNumbers;
    }

    final static Random randomizer = new Random();

    private static int[] generateRandomZerosOrOnes(int numberCount) {
        int[] numbers = new int[numberCount];

        for (int i = 0; i < numberCount; i++) {
            numbers[i] = randomizer.nextInt(2);
        }

        return numbers;
    }
}
```

//Edit: Mist zu langsam ;-)

Gruß Tom


----------



## Thomas Darimont (31. Mai 2007)

Hallo,

...und so gings ohne neues Array:

```
/**
 * 
 */
package de.tutorials;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Tom
 * 
 */
public class SpecialCaseExample {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] numbers = // {1, 1, 0, 1, 0, 1, 1, 1, 0, 0};
		generateRandomZerosOrOnes(10);
		System.out.println(Arrays.toString(numbers));
		sort(numbers);
		System.out.println(Arrays.toString(numbers));
	}

	private static void sort(int[] numbers) {
		for (int i = 0, j = numbers.length - 1; i <= j;) {
			if (numbers[j] == 0) {
				if (numbers[i] == 1) {
					numbers[i] = 0;
					numbers[j] = 1;
				}
				i++;
			} else {
				j--;
			}
		}
	}

	final static Random randomizer = new Random();

	private static int[] generateRandomZerosOrOnes(int numberCount) {
		int[] numbers = new int[numberCount];

		for (int i = 0; i < numberCount; i++) {
			numbers[i] = randomizer.nextInt(2);
		}

		return numbers;
	}
}
```

Gruß Tom


----------



## TimN (31. Mai 2007)

Ok, vielen Dank für den "kleinen Denkanstoß" 

Funktioniert einwandfrei


----------



## MeinerEiner_80 (31. Mai 2007)

Hm, und die ein wenig fauleren Leute nutzen einfach die Arrays.sort() Methoden...
http://java.sun.com/javase/6/docs/api/java/util/Arrays.html

Wenn ichs recht in Erinnerung habe, nutzen diese den Quicksort Algorithmus, wäre in diesem Fall also langsamer als die Eigenimplementierung..

*grüssle*
MeinerEiner


----------



## Turgor (4. Juni 2007)

Ich hätte da noch eine weitere Frage zu Arrays:
Wie überprüfe ich, ob ein (double-)Array auf- oder absteigend sortiert ist? In beiden Fällen würde eine einfache Boolean-Rückgabe reichen.
Danke schon mal für die Hilfe!


----------



## Matthias Reitinger (4. Juni 2007)

Turgor hat gesagt.:


> Ich hätte da noch eine weitere Frage zu Arrays:
> Wie überprüfe ich, ob ein (double-)Array auf- oder absteigend sortiert ist?


Du überprüfst einfach, ob für alle Paare von aufeinanderfolgenden Werten des Arrays gilt, dass der Wert mit dem kleineren Index nicht größer (aufsteigend) bzw. nicht kleiner (absteigend) als der andere Wert ist. Am einfachsten ginge das wohl mit einer entsprechenden Schleife.

Grüße,
Matthias


----------



## Turgor (5. Juni 2007)

Ja, richtig. So weit die Theorie. Aber ich bekomme - wenn ich es so wie ich mir das denke, mache - immer true zurückgeliefert.
mal als ganz einfachen Code dargestellt:

```
public boolean isSorted(){
		boolean tmp = false;
		for (int i=0; i<a.length; i++){
			if (a[i]<a[i+1]){
				System.out.println("Das Array ist sortiert");
				tmp = true;
				return tmp;
			}
			else if (a[i]>a[i+1]){
				System.out.println("Das Array ist sortiert");
				tmp = true;
				return tmp;
			}
			else {
				System.out.println("Das Array ist nicht sortiert");
				tmp = false;
				return tmp;
			}
		}
		return tmp;
	}
```


----------



## Matthias Reitinger (5. Juni 2007)

Hallo,

deine Schleife wird maximal einmal durchlaufen, da in jedem Codezweig ein return steht. Mach es einfach so, dass du in der Schleife ein false zurückgibst, falls für das aktuelle Paar die Bedingung nicht gilt. Wenn dann die Schleife komplett durchläuft, muss die Bedingung für alle Paare gelten und das Array ist sortiert. Daher reicht es, wenn man dann nach der Schleife ohne weitere Überprüfung true zurückgibt.

Grüße,
Matthias


----------



## Turgor (5. Juni 2007)

```
public boolean isSorted2() {
		boolean tmp = true;
		if (a.length>2){
			if(a[0] < a[1]) {
				for(int i=0; i<a.length-1; i++) {
					if(a[i] > a[i+1]) {
						tmp = false;
					}
				}
			} else {
				for(int i=0; i<a.length-1; i++) {
					if(a[i] < a[i+1]) {
						tmp = false;
					}
				}
			}
			System.out.println("Arraysortierung: " + tmp);
			return tmp;
		}
		else {
			System.out.println("Array enthält nur ein oder kein Element.");
			return tmp;
		}
	}
```

danke für die Hinweise! Jetzt funktionierts.


----------

