Array sortieren

[TimN]

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]

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]

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]

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]

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]

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

Funktioniert einwandfrei

 

[MeinerEiner_80]

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]

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]

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]

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;
	}