# Zahlen in ARRAY Sortieren



## tanjaHS (29. Nov 2008)

Hi Leute ich habe hier ein Programm das Zahlen die in einem Array stehen sortieren soll, nach folgender Art.
Nehmen wir an wir haben *|*9, 5, 4, 3, 1, 8*|* hier sollen wir nun die größte und die kleinste Zahl bestimmen. Die kleinste ganz rechts und die größte ganz links. Dann werden die sortierten nicht mehr betrachtet und man nimmt die sotierte folge 1 *|* 5, 4, 3, 8, *|* 9 jetzt wird im 2ten Schleifenlauf die Zahlen 5, 4, 3, 8 sortiert usw. Ich habe den ersten Schritte geschafft aber mir fehlt die Idee, wie ich die darauf folgenden Schritte realisieren kann, jemand eine Idee ? Meine IDEE mit y ist im CODE beschrieben, aber funktioniert nicht. Bitte um ideen.DANKE


```
static void Sort(int[] array){
		// Hilfvariablen
		int lowerBound = array[0];
		int upperBound = array[0];
		int x = 0, y = 0, z = 0, buffer = 0, buffer2 = 0;

		//wird solange Ausgeführt wie das Array groß ist
		while(x < array.length){
```



> y wird auf 0 gesetzt und i=y so kann man beim nächsten Schleifendurchlauf von while
> dass array an der stelle [0] auslassen weil y=1 und i=y -> _ = 1, dadurch wird beim
> ersten durchlauf die 1 und 9 sotiert und wenn i=1 ist, dann sind die Grenzen für den 2ten
> Durchlauf gesetzt - > ab array[1] bis array[array.lenght-1-z] z=1_


_



		Code:In die Zwischenablage kopieren


			for(int i=y; i<array.length-z; i++){
				if(lowerBound > array[i]){
					lowerBound = array[i];
				}
				if (upperBound < array[i]){
					upperBound = array[i];
				}
			}





			/* kopiervorgang, dieser soll nur einmal ausgeführt werden deshalb j = 0 und dann j++
			 * -> j!=0 Schleifenabbruch*/
		
Zum Vergrößern anklicken....




		Code:In die Zwischenablage kopieren


			for(int i=y; i<array.length-z; i++){
				int j = 0;
				if(j==0 && array[i] == lowerBound){
					buffer = array[0];
					array[0] = lowerBound;
					buffer2 = array[array.length-1];
					array[i] = buffer2;
					//println("Buffer: "+buffer);
					array[array.length-1] = buffer;
				}
				j++;
			}
			x++;
			y++;
                        z++;
		}
	}

	public static void main(String[] args) {
		//initializing the array
		int[] array = {9, 5, 4, 3, 1, 8};
		Sort(array);
	}

_


----------



## SlaterB (29. Nov 2008)

wenn x bis array.length läuft und immer um 1 erhöht wird, warum dann eine while-Schleife und keine deutlichere for-Schleife?

fünf namenlose Variablen x, y, z, i, j sind ein unverständliches Durcheinander,
da x, y und z gleichförmig erhöht werden, haben sie zu jedem Zeitpunkt den gleichen Inhalt, da reicht doch eine Variable?

wieso dieser komische Kopiervorgang, der nur einmal durchgeführt werden soll, mit der seltsamen i/j-Konstruktion?
gehts nicht GANZ OHNE SCHLEIFE auch genau einmal?


du brauchst:

```
for-i-Schleife bis zur Hälfte des Arrays {

   for-j-Schleife, die erst bei Position i anfängt und bis bis length-i läuft, hast du ja schon einigermaßen {
       lowerBound + upperBound bestimmen + deren Indexe im Array
   }

   ohne Schleife die Grenzwerte an den Rand des Arrays setzen,
   die dortigen Werte auf die vorherigen Positionen von upper + lower,
   deshalb musst du dir auch die Indexe im Array merken,

}
```


----------



## Zed (29. Nov 2008)

Ist das eine Schulaufgabe die so gelöst werden muss? 
Schaumal hier vorbei : http://www.sortieralgorithmen.de/


Ansonsten würde ich die eher eine ArrayList<Integer> und Arrays.sort() vorschlagen.


----------



## tanjaHS (29. Nov 2008)

ja das muss so gelöst werden, so ist die Aufgabenstellung. Das mit den überflüssigen Variablen stimmt. Der Kopiervorgang deshalb, weil ich ja lower und upper verschieben muss, deshalb muss ich sie vorher irgendwo hin speichern. 

Wenn beim ersten mal i = 0 ist startet das Array von 0 und endet beim letzten Array_ und beim zweiten durchlauf wird i um 1 erhöht nun heisst es array[0] wird ausgelassen und läuft bis array.lenght-1, das war meine Idee, aber wie gesagt klappt nicht._


----------



## hdi (30. Nov 2008)

Puh... also ich hab das jetz mal gemacht. Hab fast 2 Stunden gebraucht, ist immer wieder erstaunlich wie 
schwer sowas eigentlich ist (oder ich tu mich nur so schwer).

Wie immer gibt es *sicherlich* bessere Lösungen. Ich habe gewisse Print-Meldungen eingebaut, damit du
das mal an einem Beispiel aufrufen kannst, und *verstehst*, wie das funktioniert.

Und in diesem Zuge siehst du vllt noch Dinge, die man besser machen kann, und schreibst die Funktion selber
nochmal besser!

Hier der Code, die Methode returned dir das übergebene Array als sortiertes Array. Das kannst du ja dann
in einer Schleife element-weise auslesen.


```
private static int[] sort(int[] array) {

		// das wird am ende das sortierte array
		int[] sorted = new int[array.length];

		// diese zahlen geben die stellen an, an die wir in das sorted-array
		// im jedem schleifendurchlauf die werte einfüllen. mir machen es von
		// aussen nach innen, d.h. der erste min-wert kommt an den anfang,
		// der erste max wert ganz an das Ende, danach 2. und vorletzte Stelle,
		// usw.
		int beginIndex = 0;
		int endIndex = array.length - 1;

		// zu sortierendes array durchlaufen
		// (immer wenn wir das max und min haben, nehmen wir diese werte raus
		// und schrumpfen das array
		while (array.length > 0) {
			System.out.println("NEUER SCHLEIFENDURCHLAUF - Länge des Arrays: "
					+ array.length);
			int max = 0;
			int min = array[0]; // einfach mal der erstbeste Wert
			// wir speichern auch die stelle des min/max ab, nicht nur den wert,
			// weil das min/max auch öfters vorkommen könnte.
			int maxIndex = 0;
			int minIndex = 0;
			for (int i = 0; i < array.length; i++) {
				// falls dieser wert > max, max updaten:
				if (array[i] > max) {
					max = array[i];
					maxIndex = i;
				}
				// analog zu max
				if (array[i] < min) {
					min = array[i];
					minIndex = i;
				}
			}
			System.out.println("max: " + max + " (index " + maxIndex + ")");
			System.out.println("min: " + min + " (index " + minIndex + ")");
		        // das min/max dieses durchlaufs in unser sorted-array einfügen
			// und den platz der nächsten werte neu setzen:
			sorted[beginIndex] = min;
			sorted[endIndex] = max;
			beginIndex++;
			endIndex--;

			// array durch neues array ohne diese zwei werte ersetzen:
			if (array.length > 1) {
				int[] temp = new int[array.length - 2];
				int tempIndex = 0;
				System.out.println("Erstelle neues Array ohne min/max:");
				for (int i = 0; i < array.length; i++) {
					boolean skip = false;
					// wenn wir beim min/max sind, überspringen wir es, d.h. wir
					// kopieren den wert nicht in unser neues array:
					if (i == minIndex || i == maxIndex) {
						System.out.println("skipping: " + array[i]);
						skip = true;
					}
					if (!skip) {
						System.out.println("kopiere: " + array[i]);
						// weder max noch min, d.h. das brauchen wir noch für
						// den
						// nächsten schleifendurchlauf:
						temp[tempIndex] = array[i];
						tempIndex++;
						skip = false;
					}
				}
				// array updaten (ist jetzt das array ohne das min/max dieses
				// durchlaufs):
				array = temp;
			}
			// hier kommen wir an, falls das array eine ungerade anzahl von
			// elementen
			// hatte, und nun nur noch eins übrig ist. Dann müssen wir natürlich
			// nix mehr
			// kopieren und aussortieren, das letzte element wurde oben ja schon
			// in das
			// sorted-array eingefügt. wir sind also fertig!
			else {
				break;
			}
		}
		return sorted;
}
```


----------



## SlaterB (30. Nov 2008)

zum Ausgleich des Code-Verratens ist es immerhin eine unnötig komplizierte Variante


----------



## hdi (30. Nov 2008)

Naja ich hab ja drauf hingewiesen dass die Thread Erstellerin das verstehen soll, nich nur copy n paste.

Kann man das mit Arrays noch sehr viel besser machen? Ich meine, ohne ArrayList, Maps etc. Ich denke nämlich
nicht dass sowas verwendet werden darf. Würde mich interessieren, weil ich find's selber auch etwas schlecht,
dass ich so verdammt lange brauche um das fehlerfrei hinzukriegen, auch wenn ichs mit Absicht nur mit normalen
Arrays mach..


----------



## SlaterB (30. Nov 2008)

ich habe eine Variante halb vorgegeben, es reicht, innerhalb des vorhandenen Arrays zu agieren,
die sortierten Werte an den Rand drücken und dann nur im inneren Teil des Arrays weitermachen,

ist zwar bisschen Gefummel mit den Indexen, aber beim Erstellen des neuen Arrays auch nicht leichter,

Maps und Listen brauch man da nicht, nein


----------



## hdi (30. Nov 2008)

Ja, ich hatte das auch erst ohne temporäres Array versucht, aber an dieser Stelle:



> ...ohne Schleife die Grenzwerte an den Rand des Arrays setzen,
> die dortigen Werte auf die vorherigen Positionen von upper + lower...



...gabs plötzlich n Problem, denn das ganze haut nicht mehr so unkompliziert hin, 
wenn upper+lower selber schon zufällig an den Rändern des Arrays liegen! Das alleine könnte
man per simpler if-Abfrage testen, aber dann kommt noch das Problem, das dein Array so aussehen könnte:

{ 1,1,1,1,4,9}

oder ich hab grad ne Blockade... Zumindest gabs beim Test verschiedener Arrays manchmal Probleme,
dann hab ichs eben mit dem Kopieren des arrays gemacht.


----------



## SlaterB (30. Nov 2008)

man vertauscht in Runde 1 array[0] mit array[lowerIndex],
völlig egal ob lowerIndex gerade auch 0 ist oder einer der anderen,
da brauch man kein if,

---

in 
> { 1,1,1,1,4,9} 
sehe ich keine Blockade,

vielleicht passiert bei allem Vertauschen nix, aber das ist ja kein Nachteil


----------



## tanjaHS (30. Nov 2008)

> man vertauscht in Runde 1 array[0] mit array[lowerIndex],
> völlig egal ob lowerIndex gerade auch 0 ist oder einer der anderen,
> da brauch man kein if,



ja das stimmt und das gilt auch für upperIndex. Naja ich schick das mal meinen Prof. mal schauen ob er meinen Fehler im Code findet, aber ich danke euch recht herzlich.


----------

