Sortierung eines Array überprüfen

Seite 1 von 2 - Forum: Coding Stuff auf overclockers.at

URL: https://www.overclockers.at/coding-stuff/sortierung_eines_array_ueberpruefen_152234/page_1 - zur Vollversion wechseln!

Irgendwie schaff ichs nicht einen sicherlich toddl einfachen Algo zu erstellen.

Es soll ein int Array überprüft werden und wenn die Zahlen aufsteigend sortiert sind eine 1, wenn absteigend -1 und wenn unsortiert 0 zurück gegeben werden.

Zur Zeit habe ich folgende Lösung, welche mir aber nicht wirklich gefällt. Meiner Meinung nach gibt es da sicher eine hübschere Variante.

Code:

private static int sortiert (int [] array)	{
		
	int temp=0,temp1=0;
		
	if (array.length==1)	//Per Definition geordnet
	return 1;

	if(array[0]<array[1])
		temp=1;
	else if(array[0]>array[1])
		temp=-1;
						
	for(int counter=1;counter<array.length-1;counter++)
	{
				
		if(array[counter]<array[counter+1])
			temp1=1;
		else if(array[counter]>array[counter+1])
			temp1=-1;
					
		if(temp!=temp1)
			return 0;
			
	}	
	return temp;
		}

del

Wenn es beabsichtigt ist, dass Arrays wie z.B. { 1, 1, 2, 2, 3 } als unsortiert angesehen werden, ist die Lösung schon mal ganz in Ordnung (außer, dass bei dem 2. if-Statement das letzte else fehlt, das 0 zurückgibt).
Eventuell könntest du deine 2 temporären Variablen durch eine ersetzen aber das spielt imho keine große Rolle. Für eine Hausaufgabe reicht es allemal

Genau genommen brauchst du 4 Zustände:

- bisher aufsteigend sortiert
- bisher alles gleich
- bisher absteigend sortiert
- unsortiert

Und für ein leeres Array musst du dir auch noch was überlegen.

@gue ja an diesem problem wurde gearbeitet. Nur hab ich es nicht erwähnt

@that leeres Array sollte nicht exsitieren, da sobald es in java initialisiert wird afaik die werte sowieso 0 sind. bilde ich mir zumindest ein.

Meine derzeitige Lösung:

Code: PHP

private static int isSorted (int [] array)	{
		
int temp=0,temp1=0;
		
if (array.length==1)	//Per Definition ist ein Array mit nur einem Element geordnet
 return 1;
	
				
  for(int counter=0;counter<array.length-1;counter++)
   {
      while(temp==0)		//Überprüfung auf gleiche Zeichen am Anfang des Arrays zb.: 8,8,8,8,1
	{
	   if(array[counter]<array[counter+1])
	     temp=1;
	   else if(array[counter]>array[counter+1])
	     temp=-1;
	   counter++;
	   
            if (counter==array.length-1)	//Array durchlaufen und nur gleiche Zeichen gefunden=sortiert 1 zurück
	      return 1;
	}
		
	if(array[counter]<array[counter+1])	//Vergleichen ob das nächste Element > oder < dem vorherigen ist.
	  temp1=1;				//Ergebnis in temp1 abspeichern.
	else if(array[counter]>array[counter+1])
	  temp1=-1;
	
	if(temp!=temp1 && temp1!=0)		//Tritt eine Änderung auf ist das Array unsortiert =>return 0
	  return 0;
			
	}	
	return temp;				//Keine Änderung aufgetreten Array ist sortiert. Ergebnis in temp1
		}

Leere Arrays gibt es sehr wohl. Und dein Code enthält einen kleinen Bug - in der inneren Schleife bist du bei der Abfrage vor dem return um 1 daneben.

Vereinfachen kannst du das Ganze, indem du die innere Schleife vor die andere ziehst und die zweite Schleife einfach dort weglaufen lässt wo die erste aufgehört hat.

Ein spannendes Problem - die Aufgabe klingt so trivial, aber die Lösung ist gar nicht so einfach richtig zu kriegen.

Mein derzeitiger Stand:

Code:

    public static int isSorted2(int[] array) {
        int i;
        for (i = 1; (i < array.length) && (array[i-1] == array[i]); ++i) {}
        if (i >= array.length)
            return ASCENDING;
        int order = (array[i-1] < array[i]) ? ASCENDING : DESCENDING;
        for (; i < array.length; ++i) {
            if (array[i-1] > array[i] && order == ASCENDING)
                return UNSORTED;
            if (array[i-1] < array[i] && order == DESCENDING)
                return UNSORTED;
        }
        return order;
    }

its not a bug its a feature

das is schon so in ordnung
denn zuvor wird ja array[counter] mit array[counter+1] verglichen. würde ich erst bei counter==array.length abbrechen würde der vergleich oben fehlschlagen.

Edit: wow that schön knackig, wusste ja das es besser geht.

Im Gegensatz zu dir teste ich meine Behauptungen vor dem Posten.

Probier mal isSorted(new int[]{3,3,2})

(du hast ein "++" vor dem if übersehen)

Ich habs vorher auch extra mal ganz schnell und grob getestet und da gings auch nicht

Dachte einfach "ja gut um eins daneben meint da liebe that" also mal flott die bedingung geändert und schon kommt der supergau

Sagen wir einfach das wir beide recht hatten. Habe meine Version ausgebessert. und wenn man meine logisch überdenkt und optimiert kommt man ja doch am ende auf deine.

Hätte halt doch mal die innere schleife rauslegen sollen so wie du gesagt hattest.

Und noch die einfachste Variante.
Warum mir die nicht gleich eingefallen ist.

Code:

private static int isSorted3 (int [] array){
boolean usorted = true;
boolean dsorted = true;

for(int i=0; i<(array.length-1) && dsorted; i++)
      dsorted = array[i] >= array[i+1];

for(int i=0; i<(array.length-1) && usorted; i++)
      usorted = array[i] <= array[i+1];

if(dsorted)
return -1;
if(usorted)
return 1;


return 0;
}

ich hätts wahrscienlich gleich gmacht wie die letzte variante, nur was da natürlich ist, dass bei großen arrays die zeit bei extrem blöden werten ziemlich rauf gehn kann
aber im normalfall wirds net wirklich länger sein...

O(n) is doch eh sexy...

Mit zwei "Sticky"-Booleans sollte man aber zB. auch eine Schleife noch wegbekommen

ähm i mein wennst pech hast und das array nur gleiche werte hat und nur der letzte wert kleiner/größer is, dann hast O(2*n)
aber wie gsagt, des is schlechtester fall

des mit den zwei wie du sagst "sticky" booleans hat er (und auch that) ja mit einem int wert eh vorher scho gmacht

Zitat von Neo-=IuE=-

ähm i mein wennst pech hast und das array nur gleiche werte hat und nur der letzte wert kleiner/größer is, dann hast O(2*n)
aber wie gsagt, des is schlechtester fall

Zitat von Neo-=IuE=-

des mit den zwei wie du sagst "sticky" booleans hat er (und auch that) ja mit einem int wert eh vorher scho gmacht

Zitat von watchout

und nur bei weder noch kannst du O(1) schaffen

overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025