Java/Sortieren und Weltgeschichte ab 1990: Unterschied zwischen den Seiten

Aus ZUM-Unterrichten
< Java(Unterschied zwischen Seiten)
(Artikel von Claus Schmitt, importiert aus ZUM-Classic)
 
main>Fontane44
K (Link)
 
Zeile 1: Zeile 1:
[[File:Postamt 1 am Stresemannplatz 1-5 (Kiel 34.332).jpg|300px|right]]Um 10 v. Chr. ordnete Marcus Verrius Flaccus als Erster ein lateinisches Wörterbuch alphabetisch an. Die Menschen wollten schon immer wissen, wer der größte, stärkste, mächtigste ist. In unserem Zeitalter gilt um so mehr: Was sollte man mit einem ungeordneten Telefonbuch anfangen? Was nutzt eine Kunden- (aktuell eine Spender-) datei, die man nicht nach Namen, Alter, Wohnort, Einkommen sortieren kann?
Die '''Weltgeschichte ab 1990''' steht durch den Zusammenbruch des Ostblocks von 1989/90 in einer neuen weltpolitischen Konstellation. Die zentralen Ereignisse danach waren der Angriff auf das {{wpde|Terroranschläge am 11. September 2001 in den USA|World Trade Center 2001}} und die [[Finanzkrise ab 2007|Weltfinanzkrise ab 2007]].


== Kurzdarstellung ==
Zunächst erschien es so, als könne die Beendigung des Kalten Krieges aufgrund allgemeiner Abrüstung zu einer Friedensdividende und zu allgemeiner Demokratisierung führen. Dabei herrschte angesichts der unumstrittenen Stellung der USA als einziger verbliebener Supermacht auch eine gewisse Einigkeit darüber, dass die wirtschaftliche Entwicklung von Deregulierung und [[Globalisierung]] geprägt sein sollte.<ref>vgl. ''Washington Consensus'' von 1990 und Umbau des GATT in die WTO mit stärkeren Kompetenzen, Zollabbau zu erzwingen, und die Kritik an dieser Politik durch attac (1998 gegründet) und u.a. den Wirtschaftsnobelpreisträger Joseph E. Stiglitz in //wpd|Die Schatten der Globalisierung}} (2002).</ref> Jedoch das Auseinanderbrechen Jugoslawiens und mehr noch die {{wpd|Terroranschläge am 11. September 2001 in den USA}} durch l-Qaida beendigten diese Friedenshoffnung. Die USA riefen einen weltweiten ''Krieg gegen den Terrorismus'' aus. Sie griffen 2001 {{wpde|Krieg in Afghanistan seit 2001|Afghanistan}}  und im März 2003 den Irak an. Es kam zu weiteren Terroranschlägen in Madrid (2004), in {{wpde|Terroranschläge am 7. Juli 2005 in London|London}} (2005) und in {{wpde|Anschläge am 26. November 2008 in Mumbai|Mumbai}} (2008).


{{Fortsetzung|
Russland kehrte unter Gorbatschows Nachfolger Boris Jelzin zu einer nationalistischeren Politik zurück, doch bereicherten sich {{wpde|Oligarch#Oligarchen_der_Ära_Jelzin|Wirtschaftsführer}} unverhältnismäßig, während ein großer Teil der Bevölkerung verarmte. Ab 2000 setzte Wladimir Putin mit diktatorischen Methoden die staatliche Autorität wieder durch, doch bei dem inneren Konflikt mit Tschetschenien ließ er schwere {{wpde|Zweiter_Tschetschenienkrieg#Menschenrechtssituation|Menschenrechtsverletzungen}} zu. Beim {{wpd|Kaukasus-Konflikt}} trat Russland deutlich als Hegemonialmacht auf. Auch nachdem Putin aus verfassungsrechtlichen Gründen als Staatspräsident von Dmitri Medwedew abgelöst wurde, blieb er als Ministerpräsident weiterhin der starke Mann.
weiter=Klassen und Objekte|weiterlink=Java/Klassen und Objekte|
vorher=Mustererkennung|vorherlink=Java/Mustererkennung|
übersicht=Einstieg in Java<br>(Übersicht)|übersichtlink=Java#Übersicht|}}


== Einführung von (statischen) Metoden ==
2004 nahm die [[Europäische Union]] 10 neue Mitglieder auf. Mit dem Vertrag von Lissabon von 2009<ref>unterzeichnet 2007, endgültig ratifiziert 1. Dezember 2009</ref> wurde die Struktur an die neue Situation angepasst, nachdem ein Verfassungsvertrag 2005 an Negativvoten bei Volksabstimmungen in Frankreich und den Niederlanden gescheitert war.  
Oft gibt es in einem Computerprogramm  Abläufe von Operationen, die mehrfach aufgerufen werden; das Sortieren ist dafür ein wichtiges Beispiel. Da man solche Handlungsanweisungen nicht immer wieder editieren möchte, modularisiert und verallgemeinert man diese Befehlsfolgen und nennt dies in Java eine '''Methode''' (in Pascal eine Funktion oder Prozedur). Insbesondere erreicht man durch den Aufruf von Modulen eine größere Übersichtlichkeit in der Aufrufebene.


Im letzten Kapitel ([[Java/Mustererkennung|Mustererkennung]]) hätte man z.B. Methoden nutzen können, um die Felder  mit Zufallszahlen zu füllen oder um die Inhalte aller Feldelemente auszugeben. Einer Methode kann man beim Aufruf Übergabe-Parameter mitschicken; man kann auch  Werte zurück erhalten. Soll die Methode der ganzen Klasse zur Verfügung stehen (unabhängig von der Erzeugung eines Objektes), erhält die Methode den Modifier <code>static</code>.
In den USA ging [[Barack Obama]], der erste schwarze Präsident, 2009 in deutlicher Abkehr von seinem Vorgänger George W. Bush zu einer kooperativen Außenpolitik über,<ref>Dafür wurde er 2009 mit dem Friedensnobelpreis geehrt. (>[http://nobelpeaceprize.org/en_GB/home/announce-2009/ The Norwegian Nobel Committee, 9. Oktober 2009: ''The Nobel Peace Prize for 2009''])</ref> und trieb die {{wpde|START#New_START|atomare Abrüstung}} voran. Innenpolitisch erzielte er 2010 mit seiner - aufgrund massiver Gegenwehr freilich verwässerten - {{wpde|Gesundheitssystem_der_Vereinigten_Staaten#Auswirkungen_der_Reform|Gesundheitsreform}} einen ersten und mit den Maßnahmen zur Regelung des Finanzmarktes<ref>[http://www.spiegel.de/wirtschaft/soziales/0,1518,706792,00.html spiegel.de: ''Schutzwall gegen die wilde Wall Street''] (Zugriff am 17. Juli 2010).</ref> einen zweiten Erfolg.  


== Suche des Maximums in einem gegebenen Feld ==
Neben die {{wpd|G 8}} trat als  internationales Konsultationsforum die G 20, der neben anderen Schwellenländern insbesondere China und Indien angehörten. Diese gewannen bei Beratungen über die [[Finanzkrise ab 2007]] verstärkte Bedeutung<ref>2008 trafen in Washington erstmals die Staats- und Regierungschefs der Gruppe zusammen, wobei China und Indien, weil sie von der Krise weniger betroffen waren, eine stärkere Position hatten.</ref> und machten auch sonst immer häufiger als Großmächte ihre nationalen Interessen geltend, z.B. auch auf der {{wpd|UN-Klimakonferenz in Kopenhagen}} 2009, die deshalb und wohl auch aufgrund unzureichenden Engagements der USA scheiterte.<ref>"Als wesentlich für das Scheitern gilt die mangelnde Einigung zwischen China und den USA. Während der Konferenz versuchte Präsident Obama Zeitungsmeldungen zufolge, eine nächtliche Kompromissformulierung in direkten Verhandlungen mit dem chinesischen Premierminister Wen Jiabao zu erreichen und traf Wen in einer Runde mit den Regierungschefs von Indien, Brasilien und Südafrika an." ({{wpde|UN-Klimakonferenz in Kopenhagen#Konferenzverlauf|UN-Klimakonferenz in Kopenhagen}}) sieh [http://www.spiegel.de/spiegel/print/d-70327184.html Bericht über die Videoaufzeichnung einer entscheidenden Verhandlungsphase] Spiegel online 3. Mai 2010, abgerufen 17. Mai 2010</ref>
Eine wichtige Vorstufe beim Sortieren ist das Finden eines Maximums z.B. in einem Zahlenfeld; dazu nutzen wir die Methode <code>maximum</code> und schicken das Feld <code> a </code> mit Typangabe als Parameter mit. Das <code>int</code> vor dem Methodennamen steht für den Rückgabetyp; unbedingt ist dann ein Ergebnis rückzumelden, und dies wird mit <code>return</code> gekennzeichnet.


<source lang="java">
== Daten ==
public class Max {
<poem>
'''1990'''
Wahlen in DDR, Währungsunion,
deutsche Einigung (3.10.) Major Premier (in Großbritannien)
Litauen selbständig,
KSE-Vertrag (über konventionelle Streitkräfte in Europa)
Irak besetzt Kuweit
'''1991 '''
Maastrichter Vertrag beschlossen, 
Krieg Serbien-Kroatien
Moskauer Putsch (19.8.) Zerfall der SU, Jelzin russ. Präsident, Gründung GUS (21.12.), START I (unterzeichnet)
2. Golfkrieg; Apartheid in Südafrika aufgehoben
'''1992'''
Krieg in Bosnien
Vertrag über offenen Himmel (unterzeichnet)
Umweltgipfel Rio,
Agenda 21
Nahrungsmittelhilfe in Somalia
'''1993'''
1.1. Maastrichter Vertrag in Kraft (EU)
Clinton Präsident,  russische Verfassungskrise  Verbot von C-Waffen, START II (unterz.)
UNO Kämpfe in Somalia, Israel.- paläst. Abkommen, Ruanda Bürgerkrieg
'''1994 '''
Herzog Bundespräsident der BRD
USA Intervention in Haiti, Partnerschaft für den Frieden
Israel.-jordan. Friedensvertrag; Bevölkerungskonferenz Kairo
'''1995'''
Österreich, Finnland u. Schweden in EU 
Friedensvertrag für Bosnien (Dayton; Paris)
Autonomieabkommen für Westjordanland, Ermordung Rabins (4.11.)
'''1996'''
Ifor-Einsatz der Bundeswehr
Jelzins Wiederwahl
'''1997  '''
Blair (GB), Jospin (Fkr.)
Partnerschaftsvertrag Rußland-NATO (Grundakte)
Hebronabkommen, Bürgerkrieg in Zaire
'''1998'''
Friedensregelung für Nordirland (10.4.)
Rot-grüne Koalition in BRD (Schröder-Fischer)
7.5. Daimler-Chrysler-Fusion vereinbart
'''1999 '''
Rücktritt Lafontaines (11.3.), CDU Parteispendenaffäre in BRD
Kosovo-Friedenskonferenz
März: 1. Osterweiterung der NATO (Polen, Tschechien, Ungarn) NATO-Angriff auf Serbien (24.3.)
Wahlen zum europäischen Parlament
UNO in Ost-Timor
6 Mrd. Menschen auf der Erde
'''2000'''
Sturz von Milosevic (Serbien)
Putin, Präsident Russlands, 
Bush junior, Präsident der USA
'''2001'''
11.9. Terrorangriff auf New York u. Washington
7.10. US-Angriff auf Afghanistan
'''2002''' 
Einführung des Euro-Bargelds
Wiederwahl Chirac, Rücktritt Jospin; Wiederwahl Schröder
USA-Russland Kooperation
Bundeswehr in Afghanistan
Indien-Pakistan-Konflikt
'''2003'''
Berlusconiskandal , Ermordung der schwedischen Außenministerin Lindh
Uneinigkeit in SR über Irak
19.3. Angriff der USA auf Irak (3. Golfkrieg)
'''2004 '''
Köhler Bundespräsident, 
große EU-Erweiterung, Terroranschläge in Spanien
Bundeswehreinsatz im Sudan 
2. Nato-Osterweiterung, Köhler Rücktritt von IWF, Wiederwahl Bushs,
Krise und Wahl in Ukraine , Juschtschenko Präsident
US-Besatzungsherrschaft und Folter im Irak, Völkermord im Sudan, Arafat (Tod)
26.12. Erdbeben im Indischen Ozean
'''2005'''
Visa-Affäre um Fischer, 19.4. Benedikt XVI. gewählt, 29.5. Frankreich gegen EU-Verfassung,                            7.7. Terroranschlag in London ; 18.9. BRD-Wahlen;        4.10. EU Beitrittsgespräche mit Türkei u. Kroatien; Unruhen in Frankreich (ab 27.10.), Merkel Kanzlerin einer Großen Koalition
Sept. Hurrikankatastrophe in New Orleans (USA)
30.1. Wahlen im Irak
8.10. Erdbeben in Pakistan 30 000 Tote
'''2006'''
Proteste gegen Mohammed-Karikaturen. I: Prodi neuer Minsiterpräsident;
Nordkorea Atomtest
Kongowahlen, Libanonkrieg, Ban Ki Moon wird UNO-Generalsekretär
'''2007'''
Deutsche EU-Ratspräsidentschaft; G8-Gipfel Heiligendamm
Bulgarien u. Rumänien werden 26. und 27. Mitglied der EU.
Sarkozy Sieger der Präsidentschaftswahlen in Frankreich,
Gordon Brown Premier in GB.
USA Subprimekrise
Hamas erobert  gegen Fatah Gazastreifen; Ban Ki Moon  UNO-Generalsekretär
4. Weltklimabericht
Friedensnobelpreis für Al Gore und den Weltklimarat (IPCC).
Proteste in Myanmar
Ermordung von  Benazir Bhutto
'''2008'''
Finanzkrise in Europa
Medwedew russ. Präsident
russ-georgischer Krieg
Weltfinanzkrise
Proteste in Tibet
Olympische Spiele in Peking
'''2009'''
Schuldenkrise Griechenland
Obama US-Präsident
'''2010'''
23. April: Griechenland bittet um Finanzhilfe, um Staatsbankrott zu verhindern
April bis August {{wpde|Ölpest im Golf von Mexiko 2010|Ölpest im Golf von Mexiko}}
30. Juni: Wulff Bundespräsident der Bundesrepublik Deutschland
August: Volksrepublik China erreicht Platz zwei der wirtschaftsstärksten Nationen der Welt.<ref>[http://www.stern.de/wirtschaft/news/auf-der-ueberholspur-china-ist-jetzt-zweitgroesste-wirtschaftsmacht-hinter-usa-1593933.html stern.de: ''Auf der Überholspur - China ist jetzt zweitgrößte Wirtschaftsmacht hinter USA''] (Zugriff am 17. August 2010).</ref>
19.8. Sieben Jahre nach der Invasion verlassen die letzten US-Kampftruppen den [[Irak]].<ref>[http://www.spiegel.de/politik/ausland/0,1518,712502,00.html spiegel.de:''US-Abzug aus dem Irak - "Die Tore zur Hölle stehen weit offen"''] (Zugriff am 19. August 2010).</ref>
mehrfache Veröffentlichungen von US-Dokumenten durch {{wpd|Wikileaks}}
</poem>


static int maximum(int[] a)  {
== Anmerkungen ==
int n = a.length;
<references/>
int max = a[0];
for (int i = 1;i < n;i++)
  if (a[i] > max)
    max = a[i];
return max;   
}
public static void main(String[] args)  {
int[] f = new int[] {9, 37,51,2,8,73,3,103,13,5,21};
int max = maximum(f);
System.out.printf("Das Maximum ist %d%n",max);


}
== Linkliste ==
}</source>
* {{wpde|Menschheitsgeschichte#Seit_dem_Zusammenbruch_des_Ostblocks|Menschheitsgeschichte seit dem Zusammenbruch des Ostblocks}} mit Links
* [http://www.fontanefan.de/Fontanefan/TabellezurGeschichtenach1945.htm Tabelle zur Weltgeschichte seit 1945] mit Links


Ausgabe:
[[Kategorie:Geschichte]]
 
Das Maximum ist 103
 
In diesem Beispiel haben wir die Belegung des Feldes <code> f </code> gleich bei der Objekterzeugung von <code> f </code> als sog. Arrayliteral angegeben; interessanter ist es natürlich, das Feld zur Laufzeit z.B. durch einen Zufallsgenerator zu füllen. Außerdem wollen wir das Feld auch ausgeben.
 
Natürlich werden wir auch dafür  statische Methoden einsetzen:
 
=== Methoden auch für Ein- und Ausgabe ===
 
<source lang="java">
import java.util.Scanner;
public class Max1 {
 
static int feld_laenge() {
Scanner s = new Scanner (System.in);
int n;
                //Eingabeschleife bis sinnvolle Feldlänge               
do  {
    System.out.println("Welche Feldlänge?");
    n = s.nextInt();
}
while (n < 1);
return n;
}
 
static void feldein(int[] a) {
//Feldeingabemodul
for (int i = 0; i < a.length; i++)
  a[i] = (int) Math.floor(Math.random()*10);
}
 
static void feldaus (int[] a) {
//Feldausgabemodul
System.out.printf("Ausgabe des Feldes:%n");
for (int i = 0; i < a.length; i++)
  System.out.printf("%3d",a[i]);
System.out.printf("%n%n");      
} 
 
        static int maximum(int[] a)  {
          // Bestimmung des Maximums
          int n = a.length;
      int max = a[n - 1];
      for (int i = n - 2;i >= 0;i--)
  if (a[i] > max)
    max = a[i];
      return max;   
}
        // Hauptprogramm
        public static void main(String[] args)  {
      int[] f = new int[feld_laenge()];
      feldein(f);
      feldaus(f);
      System.out.printf("Das Maximum ist %d%n",maximum(f));
}
}</sourcE>
 
Beispielausgabe:
 
Welche Feldlänge?
 
8
Ausgabe des Feldes:
3 2 0 5 0 2 6 5
 
Das Maximum ist 6
 
Auch hier erhalten die Methoden zur Ein- und Ausgabe einen Parameter (das Feld); eine Rückgabe ist jeweils nicht nötig, da der Feldübergabeparameter und die Feldvariable letztlich auf den gleichen Speicherplatz referenzieren (in den nächsten Kapiteln werden wir darlegen, dass Gleichsetzen von Objekten immer die Zuweisung des gleichen Speicherplatzes bedeutet).
Methoden ohne Rückgabe erhalten den Modifier void. Außerdem  ist  zu beobachten, dass die Methode zur Eingabe der Feldlänge keinen Übergabeparameter hat (zu Methoden gehören aber immer - u.U. offene - Klammern) . Hier ist eine Rückgabe vorgesehen, und deshalb erzwingt der Compiler das return. Bemerkenswert ist, dass in Java die Feldlänge auch noch zur Laufzeit bestimmt werden kann!
 
Nochmals sei darauf hingewiesen, dass durch den Aufruf der Methoden der "rote Faden" im Hauptprogramm viel deutlicher erkennbar ist; die main-Methode hat an Übersichtlichkeit gewonnen.
 
 
== Sortieren eines Feldes ==
 
Aus der Maximumsbestimmung lässt sich sehr konsequent '''Straight Selection''' als eines der drei elementaren Sortierverfahren ableiten; mehr darüber in den Erläuterungen zum Sortieren und in Algorithmen / Methoden und Aufwand.
 
<source lang="java">
import java.util.Scanner;
public class Sort{
 
static int feld_laenge() {
Scanner s = new Scanner (System.in);
int n;
do  {
    System.out.println("Welche Feldlänge n? (ganze Zahl ab 1)");
    if (s.hasNextInt())
      n = s.nextInt();
 
 
    else {s.nextLine();
                            n = 0;}    //Damit Eingabeschleife weiter läuft
}
while (n < 1)  ;
return n;
}
//Die bereits bekannten Methoden sind wieder klein gedruckt
        static void feldein(int[] a) {
//Feldeingabemodul
for (int i = 0; i < a.length; i++)
  a[i] = (int) Math.floor(Math.random()*10);
}
 
static void feldaus (int[] a) {
//Feldausgabemodul
for (int i = 0; i < a.length; i++)
  System.out.printf("%3d",a[i]);
System.out.printf("%n%n");      
} 
 
      static void max_sort(int[] c)  {
//Sortieren mit straight selection
int max;
int pos;
int n = c.length;
for (int i = n - 1; i > 0; i--)  {
                //Maximum für einen Schleifendurchgang
max = c[i];
                // Position, an der man das Maximum findet
pos = i;
                // ob man noch ein besseres Maximum für diesen Schleifendurchgang findet?
for (int j = i - 1 ; j >= 0; j--)
  if (c[j] > max)  {
  max = c[j];
  pos = j;
  }
                  // Der alte Wert für das Maximum kommt an die Stelle, an der man den
                  // richtigen Wert fand
c[pos] = c[i];
c[i] = max; 
}    
}
 
public static void main(String[] args)  {
    int[] f = new int[feld_laenge()];
    feldein(f);
    System.out.printf("Ausgabe des Feldes vor dem Sortieren:%n");
    feldaus(f);
    max_sort(f);
    System.out.printf("Ausgabe des Feldes nach dem Sortieren:%n");
    feldaus(f);
}
}</source>
 
Beispielausgabe:
 
Welche Feldlänge n? (ganze Zahl ab 1)
 
10
 
Ausgabe des Feldes vor dem Sortieren:
 
4 1 2 5 7 0 9 5 4 2
 
Ausgabe des Feldes nach dem Sortieren:
 
0 1 2 2 4 4 5 5 7 9
 
Mit diesem Programmbeispiel soll wieder gezeigt werden, wie man durch Modularisierung die Überschaubarkeit des Programmes optimieren und vom Hauptprogramm ausgehend die Intentionen nachvollziehen kann.
Ein weiteres wichtiges Thema ist die Robustheit der Benutzerschnittstelle und damit der Eingabemethode am Anfang: Diese muss fehlertolerant programmiert werden, d.h. das System darf nicht abstürzen, wenn  Größenbereich oder Typ der Eingabedaten falsch gewählt sind.
Sehr gut lassen sich dazu Eingabeschleifen handhaben, welche solange laufen bis die Eingaben ok sind.
Dazu muss man wissen, dass der Scanner die Eingaben zunächst als Zeichenkette übernimmt, mit s.hasNextInt()prüft, ob der String in eine ganze Zahl umgewandelt werden kann und dies dann ggf. mit <code>s.nextInt()</code> realisiert. Im ungünstigen Fall muss mit <code>s.nextLine()</code> ein neuer String angefordert werden (hier wird außerdem noch der verbotene Wert 0 gesetzt; der Compiler achtet nämlich genau darauf, dass die Rückgabevariable der Methode wenigstens initialisiert ist).
 
=== Mischen zweier sortierter Felder ===
Elementare Sortierverfahren lassen sich anschaulich beschreiben; für die praktische Anwendung ist ihr quadratischer Aufwand jedoch nicht vertretbar; Ziel der weiteren Überlegungen wird also sein, den Aufwand deutlich zu reduzieren:
 
In einem ersten Schritt werden wir  in diesem Abschnitt zwei sortierte Felder zu einem sortierten Feld mischen.
 
Im Sinne von "teile und herrsche" werden wir später ein Feld in zwei Felder teilen, jeweils sortieren  und dann mischen.
 
In einem rekursiver Ansatz werden wir schließlich "teile und herrsche" "auf die Spitze treiben" und den Aufwand zwar nicht linear, aber immerhin linear - logarithmisch einstellen.
 
Für das Mischen übertragen wir folgenden Algorithmus:
 
Gegeben zwei sortierte Felder a und b mit den Längen n und m.
 
[[Bild:Java-Sortieren-1.gif]]
               
Erzeuge ein drittes Feld c (Feldplätze vom gleichen Datentyp) der Länge n + m.
 
Vergleiche die  Feldplätze von a und b und schreibe das kleinere Feldelement auf den nächsten Feldplatz
von c. Falls das  letzte Feldelement noch nicht erreicht ist, erhöhe den Feldindex in dem Feld, in dem das kleinere Feldelement gefunden wurde; ansonsten übertrage künftig (schrittweise und ohne  Vergleich) die übrigen Werte des anderen Feldes nach c.
 
<source lang="java">
import java.util.Scanner;
public class Mischen {
 
      // Hier erhält auch eine Variable den Modifier static;
        // dadurch steht der Scanner in allen Methoden zur Verfügung
static Scanner s = new Scanner (System.in);
 
      // Welche Länge soll ein Feld haben?
static int feld_laenge(int ug,int og) {
    // Untere und obere Grenze als Übergabeparameter
int n;
 
            // Eingabeschleife
do  {
System.out.printf(" Ganze Zahl ab %d bis %d%n",ug,og);
if (s.hasNextInt())
  n = s.nextInt();
else {s.nextLine();
                        n = ug - 1;}  //Damit Eingabeschleife weiter läuft
}
while ((n < ug) ||(n > og)) ;
return n;
}
 
 
//Die bereits bekannten Methoden sind wieder klein gedruckt
 
static void feld_ein(int[] c) {
//Feldeingabemodul
for (int i = 0; i < c.length; i++)
      c[i] = (int) Math.floor(Math.random()*10);
      }
 
static void feld_aus(int[] c) {
// Feldausgabemodul
System.out.println();
for(int i = 0; i <c.length; i++)
System.out.printf("%3d,",c[i]);
}
 
static void max_sort(int[] c)  {
//Sortieren mit straight selection
int max;
int pos;
int n = c.length;
for (int i = n - 1; i > 0; i--)  {
max = c[i];
pos = i;
for (int j = i - 1 ; j >= 0; j--)
if (c[j] > max)  {
  max = c[j];
  pos = j;
  }
c[pos] = c[i];
c[i] = max; 
}    
}
 
static int [] mischen (int[]a, int[] b ) {
//sortierte Felder mischen,indem man jeweils die Feldelemente vergleicht
            // und das kleinere in einem dritten Feld notiert.
// Feldlängen
int n = a.length;
int m = b.length;
// neues Feld erzeugen
int[] c = new int[n + m];
int i = 0;
int j = 0;
int k = 0;
// Jeweils prüfen, welches Feldelement in c kommt
// Aufhören, wenn ein Feld alle Werte eingefügt hat;
// Dann muss man später nur noch mit dem anderen Feld auffüllen
while ((k < n + m) && (i != n) && (j != m))  {
    if (a[i] <= b[j])  {
    c[k] = a[i];
    i++; 
      }
  else    {
    c[k] = b[j];
    j++;
      }
      k++;
    }
 
// Wenn aus a schon alle Werte eingefügt sind, muss man nur noch die Werte
            //  aus b auffüllen; etc.
// Die Werte der Laufvariablen k, i und j werden aus der While-Schleife
            //übernommen.
if (i == n )
    for (int l = k  ; l < (n + m); l++) {
  c[l] = b[j];
  j++;}
else
    for (int l = k ; l < (n + m); l++) {
  c[l] = a[i];
  i++;}
return c;
            }
 
public static void main (String[] args)  { 
    // Laenge der Felder erfragen
    System.out.printf("Wie lange ist das erste Feld? (höchstens 20) %n");
    int n = feld_laenge(1,20);
    System.out.printf("Wie lange ist das zweite Feld? (höchstens 20) %n");
    int m = feld_laenge(1,20);
 
    // 2 Felder einrichten, einlesen und sortieren
    int[] a = new int[n];
    int[] b = new int[m];
          feld_ein(a);
          feld_ein(b);
          System.out.printf("%nDie beiden unsortierten Felder%n");
    feld_aus(a);
    feld_aus(b);
    max_sort(a);
    max_sort(b);
    System.out.printf("%nDie beiden sortierten Felder%n");
    feld_aus(a);
    feld_aus(b);
    int[] c = new int[n+m];
 
    // Zwei sortierte Felder mischen
    c = mischen(a,b);
    System.out.printf("%nDas sortierte Feld nach dem Mischen%n");
    feld_aus(c);
  }
 
}</source>
 
Beispielausgabe:
 
Wie lange ist das erste Feld? (höchstens 20)
Ganze Zahl ab 1 bis 20
10
Wie lange ist das zweite Feld? (höchstens 20)
Ganze Zahl ab 1 bis 20
3
Die beiden unsortierten Felder
5, 9, 4, 3, 8, 3, 7, 5, 1, 0,
0, 6, 6,
Die beiden sortierten Felder
0, 1, 3, 3, 4, 5, 5, 7, 8, 9,
0, 6, 6,
Das sortierte Feld nach dem Mischen
0, 0, 1, 3, 3, 4, 5, 5, 6, 6, 7, 8, 9,
 
Grundsätzlich wäre es sinnvoll gewesen, die Feldlängen n und m zu statischen Variablen zu erheben (vgl. Scannervariable s);
man hätte sich dann erspart, in allen Methoden die Feldlänge neu zu bestimmen...
Andererseits sollten zentrale Input- / Output - / Sortiermethoden leicht in andere Projekte portierbar und damit autonom sein.
Die bisherigen Feldmethoden hatten alle den Modifier void. Eine Rückgabe war nicht erforderlich, da man in der Aufrufebene
und auf Methodenebene immer das gleiche Feld-Objekt referenzierte; vgl.
Die Methode Mischen allerdings gibt ein weiteres (sortiertes) Feld zurück; dieses muss vor dem Aufruf der Methode erzeugt werden.
 
=== Feld halbieren, sortieren und mischen ===
Wie oben schon angekündigt werden wir jetzt im Sinne von "divide and conquer" daran gehen, den Aufwand durch Halbieren des Feldes zu verringern: Der Aufwand lässt sich z.B. durch die Zahl der Vergleiche beschreiben; für diese Zahl kann man  bei  Straight Selection den Term
 
<code>1/2*n*(n - 1)</code>
 
elementar herleiten; halbe Feldlänge bedeutet also weniger als halb soviel Aufwand, so dass es sich also lohnt, Untersuchungen in dieser Richtung anzustellen.
 
Unser Verfahren wird also die beiden Feldhälften  elementar sortieren und dann mischen.
Diesmal lassen wir uns nicht die Felder, sondern die Zahl der notwendigen Vergleiche ausgeben. Dazu benötigen wir eine statische Variable v, die wir im Sortier- und Mischalgorithmus jeweils passend als Zähler einbauen.
 
Als Vergleichswert bei n = 100 Feldelementen (wenn man ausschließlich mit Straight Selection sortiert) ist nach obiger Formel  4950 anzusetzen. Diesen Wert gilt es zu unterbieten&hellip;:
 
<source lang="java">
import java.util.Scanner;
public class Halb_Sort {
 
static Scanner s = new Scanner (System.in);
  // Zähler für Vergleiche
    static int v= 0;
   
 
static void feld_ein(int[] c) {
  //Feldeingabemodul
  for (int i = 0; i < c.length; i++)
    c[i] = (int) Math.floor(Math.random()*10);
  }
   
 
static int feld_laenge(int ug) {
  // Untere Grenze als Übergabeparameter
  int n;
    do  {
System.out.printf(" Ganze Zahl ab %d %n",ug);
if (s.hasNextInt())
n = s.nextInt();
else {s.nextLine();n = ug - 1;}
}
    while (n < ug);
    return n;
}
 
static void max_sort(int[] c)  {
  //Sortieren mit straight selection
int max;
int pos;
int n = c.length;
for (int i = n - 1; i > 0; i--)  {
max = c[i];
pos = i;
for (int j = i - 1 ; j >= 0; j--)  {
    v++;
    if (c[j] > max)  {
    max = c[j];
      pos = j;
  }
}
c[pos] = c[i];
c[i] = max; 
}    
}
   
 
static int [] mischen (int[]a, int[] b ) {
      //Wie oben; bis auf den Zähler v    
    int n = a.length;
    int m = b.length;
    int[] c = new int[n + m];
    int i = 0;
    int j = 0;
    int k = 0;
    while ((k < n + m) && (i != n) && (j != m))  {
    if (a[i] <= b[j])  {
    c[k] = a[i];
    i++; 
      }
      else    {
    c[k] = b[j];
    j++;
      }
        k++;
                          v++;
    }
 
    if (i == n )
  for (int l = k  ; l < (n + m); l++) {
  c[l] = b[j];
  j++;}
    else
  for (int l = k ; l < (n + m); l++) {
  c[l] = a[i];
  i++;}
    return c;
 
 
}
 
static int[] sort (int[] a) {
 
int n = a.length;
if (n > 1)
{
  // Zwei neue Felder anlegen
            int m = n / 2;
  int []l =new int[m];
  int []r =new int[n-m];
  // Die zwei Hälften mit den passenden Feldelementen füllen
  for (int i = 0; i < m; i++)
l[i] = a[i];
 
 
  for  (int i = 0; i < (n-m); i++)
r[i] = a[m +i];
 
  //  jede Hälfte sortieren
  max_sort(l);
  max_sort(r);
 
 
  // Die beiden sortierten Hälften zusammenfügen
  a = mischen(l,r);
    } 
        return a;
}
 
public static void main(String[] args)  {    
    System.out.printf("Wie lange soll das  Feld sein? %n");
    int n = feld_laenge(1);    
    // Feld einrichten und einlesen
    int[] f = new int[n];
          feld_ein(f);
          // Sortieren
    f = sort(f);
    System.out.printf("%d Vergleiche", v);
}
}</source>
 
Beispielausgabe:
 
Wie lange soll das Feld sein?
 
Ganze Zahl ab 1
 
100
 
 
2545 Vergleiche
 
Falls man sich die Mühe macht und das Feld sogar in vier Teile teilt, sortiert und mischt, schwankt die Zahl der Vergleiche sogar nur noch um  1380 (vgl. Quelltext Viertel_Sort.java).
Insgesamt haben wir also unser Ziel erreicht, den Aufwand deutlich zu verringern; allerdings kann man leicht zeigen, dass sich die Zahl der wesentlichen Vergleiche immer noch mit dem Quadrat von n entwickelt. Außerdem war der Programmieraufwand für das Zerlegen des Feldes  in 4 Teile bereits schon sehr groß (vgl. Quelltext Viertel_Sort.java).
Ein Aufwand weniger als quadratisch wäre aber letztlich nur erreichbar, wenn wir das Feld so weit zerlegen, dass die Feldlänge jeweils 1 ist.... Dies soll im nächsten Abschnitt begründet werden.
 
 
== Sortieren durch Mischen (Mergesort) ==
Es bietet sich also an, das gegebene Feld fortgesetzt zu halbieren, d.h. aus der Methode die Methode selbst aufzurufen: Das optimierte Sortierprogramm  ist  rekursiv zu formulieren und allgemein als Mergesort bekannt:
 
Wenn wir im folgenden Beispiel von n = 8 Feldelementen ausgehen, erreichen wir mit drei Halbierungsdurchgängen jeweils als Feldlänge 1.
Die Drei ist der Schlüssel zur Lösung unseres Aufwandproblemes:
 
 
[[Bild:Java-Sortieren-2.gif]]
 
[[Bild:mergesort3.png]]
 
 
Entsprechend vollzieht sich auch das Mischen in drei Ebenen:
 
# In der ersten Stufe gibt es 4 = n / 2 Vergleiche.
 
# In der zweiten Stufe gibt es (mindestens) 2 * 2 = 4 Vergleiche.
 
# In der dritten Stufe gibt es (mindestens) 4 Vergleiche.
 
Insgesamt gibt es also 3 * 4 =  log( 8) * 8 / 2  Vergleiche; damit ist die bekannte Beziehung für den Aufwand n * log (n) motiviert.
 
Um Mergesort zu realisieren, müssen wir im letzten Programm (Halb_Sort) nur die Methode <code>sort()</code> durch folgenden rekursiven Ansatz austauschen; alle anderen Methoden - auch das Mischen - sind bereits entwickelt! Die Methode <code>max_sort (Straight Selection)</code> entfällt naturgemäß ganz!
 
<source lang="java">
  static int[] sort (int[] a) {
// Rekursionsende bei Feldlänge 1
        int n = a.length;
if (n > 1)
  {
  // Zwei neue Felder anlegen
  int m = n / 2;
  int []l =new int[m];
  int []r =new int[n-m];
 
  // Die zwei Hälften mit den passenden Feldelementen füllen
  for (int i = 0; i < m; i++)
    l[i] = a[i];
  for  (int i = 0; i < (n-m); i++)
    r[i] = a[m +i]; 
 
  //  jede Hälfte sortieren; rekursiver Aufruf!
  l = sort(l);
  r = sort(r);
 
  // Die beiden sortierten Hälften zusammenfügen
  a = mischen(l,r);
  }
return a;
}
</source>
 
Wesentliche Vergleiche werden hier nur in der Mischenmethode gezählt: 
Beispielausgabe:
 
Wie lange soll das Feld sein?
 
100
 
530 Vergleiche
 
Mit 4950 Vergleichen bei 100 Feldelementen hatten wir bei Straight Selection begonnen, so dass wir am Schluss auch eine sehr schöne experimentelle Bestätigung der Theorie zur Aufwandsbetrachtung haben.
 
{{Fortsetzung|
weiter=Klassen und Objekte|weiterlink=Java/Klassen und Objekte|
vorher=Mustererkennung|vorherlink=Java/Mustererkennung|
übersicht=Einstieg in Java<br>(Übersicht)|übersichtlink=Java#Übersicht|}}
 
[[Kategorie:Java]]

Version vom 12. Dezember 2010, 11:04 Uhr

Die Weltgeschichte ab 1990 steht durch den Zusammenbruch des Ostblocks von 1989/90 in einer neuen weltpolitischen Konstellation. Die zentralen Ereignisse danach waren der Angriff auf das World Trade Center 2001Wikipedia-logo.png und die Weltfinanzkrise ab 2007.

Kurzdarstellung

Zunächst erschien es so, als könne die Beendigung des Kalten Krieges aufgrund allgemeiner Abrüstung zu einer Friedensdividende und zu allgemeiner Demokratisierung führen. Dabei herrschte angesichts der unumstrittenen Stellung der USA als einziger verbliebener Supermacht auch eine gewisse Einigkeit darüber, dass die wirtschaftliche Entwicklung von Deregulierung und Globalisierung geprägt sein sollte.[1] Jedoch das Auseinanderbrechen Jugoslawiens und mehr noch die Vorlage:Wpd durch l-Qaida beendigten diese Friedenshoffnung. Die USA riefen einen weltweiten Krieg gegen den Terrorismus aus. Sie griffen 2001 AfghanistanWikipedia-logo.png und im März 2003 den Irak an. Es kam zu weiteren Terroranschlägen in Madrid (2004), in LondonWikipedia-logo.png (2005) und in MumbaiWikipedia-logo.png (2008).

Russland kehrte unter Gorbatschows Nachfolger Boris Jelzin zu einer nationalistischeren Politik zurück, doch bereicherten sich WirtschaftsführerWikipedia-logo.png unverhältnismäßig, während ein großer Teil der Bevölkerung verarmte. Ab 2000 setzte Wladimir Putin mit diktatorischen Methoden die staatliche Autorität wieder durch, doch bei dem inneren Konflikt mit Tschetschenien ließ er schwere MenschenrechtsverletzungenWikipedia-logo.png zu. Beim Vorlage:Wpd trat Russland deutlich als Hegemonialmacht auf. Auch nachdem Putin aus verfassungsrechtlichen Gründen als Staatspräsident von Dmitri Medwedew abgelöst wurde, blieb er als Ministerpräsident weiterhin der starke Mann.

2004 nahm die Europäische Union 10 neue Mitglieder auf. Mit dem Vertrag von Lissabon von 2009[2] wurde die Struktur an die neue Situation angepasst, nachdem ein Verfassungsvertrag 2005 an Negativvoten bei Volksabstimmungen in Frankreich und den Niederlanden gescheitert war.

In den USA ging Barack Obama, der erste schwarze Präsident, 2009 in deutlicher Abkehr von seinem Vorgänger George W. Bush zu einer kooperativen Außenpolitik über,[3] und trieb die atomare AbrüstungWikipedia-logo.png voran. Innenpolitisch erzielte er 2010 mit seiner - aufgrund massiver Gegenwehr freilich verwässerten - GesundheitsreformWikipedia-logo.png einen ersten und mit den Maßnahmen zur Regelung des Finanzmarktes[4] einen zweiten Erfolg.

Neben die Vorlage:Wpd trat als internationales Konsultationsforum die G 20, der neben anderen Schwellenländern insbesondere China und Indien angehörten. Diese gewannen bei Beratungen über die Finanzkrise ab 2007 verstärkte Bedeutung[5] und machten auch sonst immer häufiger als Großmächte ihre nationalen Interessen geltend, z.B. auch auf der Vorlage:Wpd 2009, die deshalb und wohl auch aufgrund unzureichenden Engagements der USA scheiterte.[6]

Daten

1990
Wahlen in DDR, Währungsunion,
deutsche Einigung (3.10.) Major Premier (in Großbritannien)
Litauen selbständig,
KSE-Vertrag (über konventionelle Streitkräfte in Europa)
Irak besetzt Kuweit
1991
Maastrichter Vertrag beschlossen,
Krieg Serbien-Kroatien
Moskauer Putsch (19.8.) Zerfall der SU, Jelzin russ. Präsident, Gründung GUS (21.12.), START I (unterzeichnet)
2. Golfkrieg; Apartheid in Südafrika aufgehoben
1992
Krieg in Bosnien
Vertrag über offenen Himmel (unterzeichnet)
Umweltgipfel Rio,
Agenda 21
Nahrungsmittelhilfe in Somalia
1993
1.1. Maastrichter Vertrag in Kraft (EU)
Clinton Präsident, russische Verfassungskrise Verbot von C-Waffen, START II (unterz.)
UNO Kämpfe in Somalia, Israel.- paläst. Abkommen, Ruanda Bürgerkrieg
1994
Herzog Bundespräsident der BRD
USA Intervention in Haiti, Partnerschaft für den Frieden
Israel.-jordan. Friedensvertrag; Bevölkerungskonferenz Kairo
1995
Österreich, Finnland u. Schweden in EU
Friedensvertrag für Bosnien (Dayton; Paris)
Autonomieabkommen für Westjordanland, Ermordung Rabins (4.11.)
1996
Ifor-Einsatz der Bundeswehr
Jelzins Wiederwahl
1997
Blair (GB), Jospin (Fkr.)
Partnerschaftsvertrag Rußland-NATO (Grundakte)
Hebronabkommen, Bürgerkrieg in Zaire
1998
Friedensregelung für Nordirland (10.4.)
Rot-grüne Koalition in BRD (Schröder-Fischer)
7.5. Daimler-Chrysler-Fusion vereinbart
1999
Rücktritt Lafontaines (11.3.), CDU Parteispendenaffäre in BRD
Kosovo-Friedenskonferenz
März: 1. Osterweiterung der NATO (Polen, Tschechien, Ungarn) NATO-Angriff auf Serbien (24.3.)
Wahlen zum europäischen Parlament
UNO in Ost-Timor
6 Mrd. Menschen auf der Erde
2000
Sturz von Milosevic (Serbien)
Putin, Präsident Russlands,
Bush junior, Präsident der USA
2001
11.9. Terrorangriff auf New York u. Washington
7.10. US-Angriff auf Afghanistan
2002
Einführung des Euro-Bargelds
Wiederwahl Chirac, Rücktritt Jospin; Wiederwahl Schröder
USA-Russland Kooperation
Bundeswehr in Afghanistan
Indien-Pakistan-Konflikt
2003
Berlusconiskandal , Ermordung der schwedischen Außenministerin Lindh
Uneinigkeit in SR über Irak
19.3. Angriff der USA auf Irak (3. Golfkrieg)
2004
Köhler Bundespräsident,
große EU-Erweiterung, Terroranschläge in Spanien
Bundeswehreinsatz im Sudan
2. Nato-Osterweiterung, Köhler Rücktritt von IWF, Wiederwahl Bushs,
Krise und Wahl in Ukraine , Juschtschenko Präsident
US-Besatzungsherrschaft und Folter im Irak, Völkermord im Sudan, Arafat (Tod)
26.12. Erdbeben im Indischen Ozean
2005
Visa-Affäre um Fischer, 19.4. Benedikt XVI. gewählt, 29.5. Frankreich gegen EU-Verfassung, 7.7. Terroranschlag in London ; 18.9. BRD-Wahlen; 4.10. EU Beitrittsgespräche mit Türkei u. Kroatien; Unruhen in Frankreich (ab 27.10.), Merkel Kanzlerin einer Großen Koalition
Sept. Hurrikankatastrophe in New Orleans (USA)
30.1. Wahlen im Irak
8.10. Erdbeben in Pakistan 30 000 Tote
2006
Proteste gegen Mohammed-Karikaturen. I: Prodi neuer Minsiterpräsident;
Nordkorea Atomtest
Kongowahlen, Libanonkrieg, Ban Ki Moon wird UNO-Generalsekretär
2007
Deutsche EU-Ratspräsidentschaft; G8-Gipfel Heiligendamm
Bulgarien u. Rumänien werden 26. und 27. Mitglied der EU.
Sarkozy Sieger der Präsidentschaftswahlen in Frankreich,
Gordon Brown Premier in GB.
USA Subprimekrise
Hamas erobert gegen Fatah Gazastreifen; Ban Ki Moon UNO-Generalsekretär
4. Weltklimabericht
Friedensnobelpreis für Al Gore und den Weltklimarat (IPCC).
 Proteste in Myanmar
Ermordung von Benazir Bhutto
2008
Finanzkrise in Europa
Medwedew russ. Präsident
russ-georgischer Krieg
Weltfinanzkrise
Proteste in Tibet
Olympische Spiele in Peking
2009
Schuldenkrise Griechenland
Obama US-Präsident
2010
23. April: Griechenland bittet um Finanzhilfe, um Staatsbankrott zu verhindern
April bis August Ölpest im Golf von MexikoWikipedia-logo.png
30. Juni: Wulff Bundespräsident der Bundesrepublik Deutschland
August: Volksrepublik China erreicht Platz zwei der wirtschaftsstärksten Nationen der Welt.[7]
19.8. Sieben Jahre nach der Invasion verlassen die letzten US-Kampftruppen den Irak.[8]
mehrfache Veröffentlichungen von US-Dokumenten durch Vorlage:Wpd

Anmerkungen

  1. ↑ vgl. Washington Consensus von 1990 und Umbau des GATT in die WTO mit stärkeren Kompetenzen, Zollabbau zu erzwingen, und die Kritik an dieser Politik durch attac (1998 gegründet) und u.a. den Wirtschaftsnobelpreisträger Joseph E. Stiglitz in //wpd|Die Schatten der Globalisierung}} (2002).
  2. ↑ unterzeichnet 2007, endgültig ratifiziert 1. Dezember 2009
  3. ↑ Dafür wurde er 2009 mit dem Friedensnobelpreis geehrt. (>The Norwegian Nobel Committee, 9. Oktober 2009: The Nobel Peace Prize for 2009)
  4. ↑ spiegel.de: Schutzwall gegen die wilde Wall Street (Zugriff am 17. Juli 2010).
  5. ↑ 2008 trafen in Washington erstmals die Staats- und Regierungschefs der Gruppe zusammen, wobei China und Indien, weil sie von der Krise weniger betroffen waren, eine stärkere Position hatten.
  6. ↑ "Als wesentlich für das Scheitern gilt die mangelnde Einigung zwischen China und den USA. Während der Konferenz versuchte Präsident Obama Zeitungsmeldungen zufolge, eine nächtliche Kompromissformulierung in direkten Verhandlungen mit dem chinesischen Premierminister Wen Jiabao zu erreichen und traf Wen in einer Runde mit den Regierungschefs von Indien, Brasilien und Südafrika an." (UN-Klimakonferenz in KopenhagenWikipedia-logo.png) sieh Bericht über die Videoaufzeichnung einer entscheidenden Verhandlungsphase Spiegel online 3. Mai 2010, abgerufen 17. Mai 2010
  7. ↑ stern.de: Auf der Überholspur - China ist jetzt zweitgrößte Wirtschaftsmacht hinter USA (Zugriff am 17. August 2010).
  8. ↑ spiegel.de:US-Abzug aus dem Irak - "Die Tore zur Hölle stehen weit offen" (Zugriff am 19. August 2010).

Linkliste

Abgerufen von „https://unterrichten.zum.de/index.php?title=Java/Sortieren&oldid=99176“