Sortierung eines Array überprüfen

shadowman

OC Addicted

Registered: Oct 2000
Location: Feldkirchen
Posts: 1612

06.11.2005 - 15:35

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

Bearbeitet von shadowman am 06.11.2005, 15:40

Taltos

Here to stay

Registered: Jan 2004
Location: Wien
Posts: 1520

06.11.2005 - 16:03

del

Bearbeitet von Taltos am 06.11.2005, 20:02

gue

Addicted

Registered: Feb 2003
Location: Linz
Posts: 400

06.11.2005 - 16:03

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

that

Hoffnungsloser Optimist

Registered: Mar 2000
Location: MeidLing
Posts: 11343

06.11.2005 - 16:08

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.

shadowman

OC Addicted

Registered: Oct 2000
Location: Feldkirchen
Posts: 1612

06.11.2005 - 17:01

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

Bearbeitet von watchout am 08.11.2005, 18:43

that

Hoffnungsloser Optimist

Registered: Mar 2000
Location: MeidLing
Posts: 11343

06.11.2005 - 20:01

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.

that

Hoffnungsloser Optimist

Registered: Mar 2000
Location: MeidLing
Posts: 11343

06.11.2005 - 20:18

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

shadowman

OC Addicted

Registered: Oct 2000
Location: Feldkirchen
Posts: 1612

06.11.2005 - 20:20

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.

Bearbeitet von shadowman am 06.11.2005, 20:27

that

Hoffnungsloser Optimist

Registered: Mar 2000
Location: MeidLing
Posts: 11343

06.11.2005 - 20:27

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)

shadowman

OC Addicted

Registered: Oct 2000
Location: Feldkirchen
Posts: 1612

06.11.2005 - 20:44

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

Bearbeitet von shadowman am 07.11.2005, 00:38

Neo-=IuE=-

Here to stay

Registered: Jun 2002
Location: Berndorf, NÖ
Posts: 3232

07.11.2005 - 12:06

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...

watchout

Legend
undead

Registered: Nov 2000
Location: Off the grid.
Posts: 6845

07.11.2005 - 12:27

O(n) is doch eh sexy...

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

Neo-=IuE=-

Here to stay

Registered: Jun 2002
Location: Berndorf, NÖ
Posts: 3232

07.11.2005 - 12:31

ä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

watchout

Legend
undead

Registered: Nov 2000
Location: Off the grid.
Posts: 6845

07.11.2005 - 13:42

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

vernachlässigbar

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

nein, er hat trotzdem 2 schleifen - du brauchst aber nur eine, weil du in einem Durchgang schon auf ASC & DESC gleichzeitig testen kannst. Wenns dann ASC *und* DESC is, dann hast du nur gleiche Werte, weder noch is dann unsortet - und nur bei weder noch kannst du O(1) schaffen, sonst ists immer O(n) dann.

BTW:
Liebe Vollbildsurfer - Mind your Code-Width.

Bearbeitet von watchout am 07.11.2005, 15:48

that

Hoffnungsloser Optimist

Registered: Mar 2000
Location: MeidLing
Posts: 11343

07.11.2005 - 20:54

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

O(1) schaffst du nur, wenn du die gültigen Eingabewerte auf Array beschränkst, die in den ersten 3 Elementen garantiert unsortiert sind.

shadowman OC Addicted Registered: Oct 2000 Location: Feldkirchen Posts: 1612	06.11.2005 - 15:35 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; }` Bearbeitet von shadowman am 06.11.2005, 15:40
Taltos Here to stay Registered: Jan 2004 Location: Wien Posts: 1520	06.11.2005 - 16:03 del Bearbeitet von Taltos am 06.11.2005, 20:02
gue Addicted Registered: Feb 2003 Location: Linz Posts: 400	06.11.2005 - 16:03 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
that Hoffnungsloser Optimist Registered: Mar 2000 Location: MeidLing Posts: 11343	06.11.2005 - 16:08 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.
shadowman OC Addicted Registered: Oct 2000 Location: Feldkirchen Posts: 1612	06.11.2005 - 17:01 @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 } Bearbeitet von watchout am 08.11.2005, 18:43
that Hoffnungsloser Optimist Registered: Mar 2000 Location: MeidLing Posts: 11343	06.11.2005 - 20:01 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.
that Hoffnungsloser Optimist Registered: Mar 2000 Location: MeidLing Posts: 11343	06.11.2005 - 20:18 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; }`
shadowman OC Addicted Registered: Oct 2000 Location: Feldkirchen Posts: 1612	06.11.2005 - 20:20 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. Bearbeitet von shadowman am 06.11.2005, 20:27
that Hoffnungsloser Optimist Registered: Mar 2000 Location: MeidLing Posts: 11343	06.11.2005 - 20:27 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)
shadowman OC Addicted Registered: Oct 2000 Location: Feldkirchen Posts: 1612	06.11.2005 - 20:44 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; }` Bearbeitet von shadowman am 07.11.2005, 00:38
Neo-=IuE=- Here to stay Registered: Jun 2002 Location: Berndorf, NÖ Posts: 3232	07.11.2005 - 12:06 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...
watchout Legend undead Registered: Nov 2000 Location: Off the grid. Posts: 6845	07.11.2005 - 12:27 O(n) is doch eh sexy... Mit zwei "Sticky"-Booleans sollte man aber zB. auch eine Schleife noch wegbekommen
Neo-=IuE=- Here to stay Registered: Jun 2002 Location: Berndorf, NÖ Posts: 3232	07.11.2005 - 12:31 ä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
watchout Legend undead Registered: Nov 2000 Location: Off the grid. Posts: 6845	07.11.2005 - 13:42 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(2n) aber wie gsagt, des is schlechtester fall vernachlässigbar 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 nein, er hat trotzdem 2 schleifen - du brauchst aber nur eine, weil du in einem Durchgang schon auf ASC & DESC gleichzeitig testen kannst. Wenns dann ASC und DESC is, dann hast du nur gleiche Werte, weder noch is dann unsortet - und nur bei weder noch kannst du O(1) schaffen, sonst ists immer O(n) dann. BTW: Liebe Vollbildsurfer - Mind your Code-Width. Bearbeitet von watchout am 07.11.2005, 15:48
that Hoffnungsloser Optimist Registered: Mar 2000 Location: MeidLing Posts: 11343	07.11.2005 - 20:54 Zitat von watchout und nur bei weder noch kannst du O(1) schaffen O(1) schaffst du nur, wenn du die gültigen Eingabewerte auf Array beschränkst, die in den ersten 3 Elementen garantiert unsortiert sind.

Sortierung eines Array überprüfen

Forum Index > Software > Coding Stuff

shadowman

Taltos

gue

that

shadowman

that

that

shadowman

that

shadowman

Neo-=IuE=-

watchout

Neo-=IuE=-

watchout

that