versuche Merge Sort zu verstehen Informatik?

static void msort(int[] array, int left, int right) {
    int i, j, k;
    int[] b = new int[array.length];
    if (right > left) {
        int mid = (right + left)/2;
        msort(array, left, mid);
        msort(array, mid + 1, right);
        for (k = left; k <= mid; k++)
            b[k] = array[k];
        for (k = mid; k < right; k++)
            b[right + mid - k] = array[k + 1];
        i = left;
        j = right;
        for (k = left; k <= right; k++) {
            if (b[i] < b[j])
                array[k] = b[i++];
            else
                array[k] = b[j--];
        }
    }
}


static void mergeSort(int[] array) {
    msort(array, 0, array.length - 1);
}

Hier werden ja die Werte in umgekehrter Reihenfolge ins hilfsarray b gespeichert, aber weiso ist das notwendig, chat gpt sagt mir wegen speicher, aber geht das ncith auch einfach in dem man die werte normal reinspeichert, weiso umgekehrt?

for (k = mid; k < right; k++)
            b[right + mid - k] = array[k + 1];

3 Antworten

W00dp3ckr

01.06.2023, 08:24

Willst Du Mergesort verstehen oder willst Du diese Implementierung verstehen?

Mergesort an sich ist super simpel.

Eine Folge von einem Element ist sortiert. Eine leere Folge auch.

Wenn Du eine längere Folge hast, dann halbiere sie und mache mit jeder halben Folge Mergesort. Danach vereinige beide sortierten Folgen. Du vereinigst (mergest) sie, dadurch, dass Du jeweils das erste Element beider Folgen ansiehst und das größere Element entnimmst und an die sortierte Folge anhängst. Das machst Du so lange, bis beide Folgen leer sind. Das Resultat ist eine lange sortierte Folge.

EasternPremise

Fragesteller

01.06.2023, 09:44

jo also den algorithmus verstehe ich auch und hab auch einen umgesetzt, aber diesen da oben verstehe ich nur so halb, wieso wird dann bei der 2. forschleife das umgekehrt reingespeichert?

teehouse

31.05.2023, 22:19

Hier werden ja die Werte in umgekehrter Reihenfolge ins hilfsarray b gespeichert, aber weiso ist das notwendig,

Vermutlich, weil sonst irgendwas überschrieben werden würde. Generell ein nicht einfach zu verstehender Algorithmus. Ich würde erst versuchen, ihn anhand eines Videos zu verstehen. Sich den Code zu merken und Zeile für Zeile zu verstehen ist schon nicht ohne.

EasternPremise

Fragesteller

31.05.2023, 22:21

ok vielen dank, dachte schon ich würde nur son Knoten im Kopf haben, ich hab den merge sort algorithmus uach anders implementiert aber mit viel mehr zeilen und 2 zusätzlichen arrays in denen ich immer die hälften speichere, funktoinerit auch ist aber eben sclhechter als der da oben, aber der da oben ist auch etwas komplizierter

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Programmiersprache, Algorithmus, Programmieren & Softwareentwicklung

31.05.2023, 23:07

        for (k = left; k <= mid; k++)
            b[k] = array[k];

Kopiert das linke zu mergende Teilarray 1:1 nach b.

        for (k = mid; k < right; k++)
            b[right + mid - k] = array[k + 1];

Kopiert das rechte Teilarray in umgekehrter Reihenfolge nach b.

Es sei left=10, right=20 und mid=30/2=15

left               mid               right
  10 11 12 13 14   15    16 17 18 19 20

Für den rechten Teil gilt:

for (k=15; k<20; k++):
k=15: b[20+15-15] = array [15+1] 20 -> 16
k=16: b[20+15-16] = array [16+1] 19 -> 17
.....

Beim Merge sollen die beiden sortierten Teilarrays sortiert zusammengeführt werden, ich muß also schauen, in welchem Teilarray das nächstgrößere Element zu finden ist.

In der Regel wird aber ein Teilarray bereits konsumiert sein, während im anderen noch Elemente sind. Das müßte ich gesondert prüfen. Um mir genau dies zu ersparen, wird der rechte Teil umgedreht und stattdessen von rechts genommen, denn so lässt sich die Schleife einfacher formulieren.

EasternPremise

Fragesteller

01.06.2023, 09:49

kannst du kurz erklären was du mit "in der regel wird aber ein teilarray bereits konsumiert sein"

KarlRanseierIII

01.06.2023, 14:05

@EasternPremise

Schau Di ram besten einen Grenzfall an wie:

1 2 3 | 4 5 6 #oder
4 5 6 | 1 2 3 # <- hierrüber sprchen wir jetzt

Ich schaue z.B. 4<=1 ? Nei, 1 nehmen ... und wenn ich die 3 entnommen habe, ist das rechte Teilarray leer. Ich habe also nichts mehr zum Vergleichen und muß das linke Teilaray kopieren, dazu brauchts nen Bounds-Check, damit ich merke, daß ich am Ende angekommen bin.

Jetzt mit Umkehrung:

4 5 6 | 3 2 1

4<=1? 1 nehmen .... 4<=3, 3 nehmen, 4<=6, 4 nehmen ... 6<=6, 6 nehmen. Es entfällt die Sonderbehandlung, weil die benachbarten größten Elemente durch den Vergleich zur Grenze werden. Dadurch reduziert sich die Schleife auf eine fixe Anzahl Vergleiche, ohne irgendein Bounds-Checking o.ä. .

EasternPremise

Fragesteller

01.06.2023, 15:26

@KarlRanseierIII

ahhh, jetzt habe ich es verstanden, das rückwerts speichern machen wir also nur , damit diese methode funktioniert ohne extra kopieren der werte, vielen dank du hast mir sehr geholfen

Ähnliche Fragen

Ist das guter Sortieralgo?

also gut geschrieben?

static void mergeSort(int[] array) {
    msort(array, 0, array.length - 1);
}

static void msort(int[] array, int left, int right) {
    if (right > left) {
        int mid = (right + left) / 2;
        msort(array, left, mid);
        msort(array, mid + 1, right);
        
        int[] b = new int[array.length];
        for (int k = left; k <= mid; k++)
            b[k] = array[k];
        for (int k = mid + 1; k <= right; k++)
            b[right + mid + 1 - k] = array[k];
        
        int i = left;
        int j = right;
        for (int k = left; k <= right; k++) {
            if (b[i] < b[j])
                array[k] = b[i++];
            else
                array[k] = b[j--];
        }
    }
}

...zur Frage

Java Arrays?

Wir haben die Aufgabe bekommen dieses Programm umzuschreiben, sodass keine Schleifen vorkommen nur if, if else und else if. Sprich er soll sortieren aber nur mit den if abfragen.

Wir sollen Aufgabe 1 a) machen wie es oben in dem Bild geschrieben ist

public class Main
{
    public static void main(String[] args)
    {
        //Array deklarieren und initialisieren
        int[] array=new int[]{3,1,2};

        //Array sortieren
        for (int j=0; j<array.length-1;j++)
        {

            for (int i=0;i<array.length-1-j;i++)
            {

                //falls linkes Element größer > tauscht mit rechts
                if(array[i]>array[i+1])
                {
                    //tauschen
                    int memory=array[i];
                    array[i]=array[i+1];
                    array[i+1]=memory;
                }
            }
        }

        //Array ausgeben
        System.out.println("Anzahl der Schritte: ");


        //zählt die einzelnen zahlen bis er durch ist
        for(int i=0;i < array.length;i++)
        {
            System.out.print(array[i]+" ");
        }
    }

...zur Frage

Quicksort "Code" erklären?

Hi Leute, ich habe ein Problem mit Quicksort code und zwar ich verstehe wie das irl gemacht wird aber für mich ist der Code schwer zu verstehen. Kann mir bitte jemand diesen Code erklären?

public class QuicksortSimple {

  public void sort(int[] elements) {
    quicksort(elements, 0, elements.length - 1);
  }

  private void quicksort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left >= right) return;

    int pivotPos = partition(elements, left, right);
    quicksort(elements, left, pivotPos - 1);
    quicksort(elements, pivotPos + 1, right);
  }

  public int partition(int[] elements, int left, int right) {
    int pivot = elements[right];

    int i = left;
    int j = right - 1;
    while (i < j) {
      // Find the first element >= pivot
      while (elements[i] < pivot) {
        i++;
      }

      // Find the last element < pivot
      while (j > left && elements[j] >= pivot) {
        j--;
      }

      // If the greater element is left of the lesser element, switch them
      if (i < j) {
        ArrayUtils.swap(elements, i, j);
        i++;
        j--;
      }
    }

    // i == j means we haven't checked this index yet.
    // Move i right if necessary so that i marks the start of the right array.
    if (i == j && elements[i] < pivot) {
      i++;
    }

    // Move pivot element to its final position
    if (elements[i] != pivot) {
      ArrayUtils.swap(elements, i, right);
    }
    return i;
  }

}

...zur Frage

In Java bestimmte Werte aus einem Array in Indexvariable eines neuen Arrays speichern?

Hallo,

ich habe gerade das Problem, dass ich an einer Aufgabe sitze, bei welcher man ein Neues Feld erzeugen soll in welchem die Werte aus einem vorgegebenen Feld so eingefügt werden, dass alle negativen Zahlen im linken Bereich und alle postiven Zahlen sowie 0 im rechten Bereich liegen. Gegeben ist folgender Code:

public static int randomInt(int a, int e) {
    return (int) (Math.random() * ((e - a) + 1)) + a;
}

public static void fuellen(int[] feld, int a, int e) {
    for (int i=0;i<feld.length;i++){
        feld[i] = randomInt(a,e);
    }
}

public static void ausgeben(int[] feld){
    for (int i=0;i<feld.length;i++){
        System.out.printf("%3d ", feld[i]);
        if ((i+1) % 10 == 0) {
            System.out.println();
        }
    }
    System.out.println();
}

bis Jetzt war mein Ansatz dieser hier:

public static int[] verteilen(int[] feld){
    int[] feld2 = new int[feld.length];
    int first = feld2[0];
    int last = feld2[feld2.length - 1];
    int count = 0;
    int right = feld2.length - 1;
    for(int i=0;i<feld.length;i++) {
        if(feld[i] < 0) {
            first = feld[i];
            count++;
        }
        else {
            last = feld[i];
            right--;
        }
    }
    return feld2;
}

und als Ergebnis soll das rauskommen aber irgendwie klappt es nicht:

39-34 76-84-79-61-59-50 96 55 -71-51-89 77 64 93-20-86 43 33

-34 -84 -79 -61 -59 -50 -71 -51 -89 -20
-86  33  43  93  64  77  55  96  76  39

...zur Frage

wie kann ich durch einen baum iterieren Java?

package ListenInJava.Baume;


public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;


    TreeNode(int data){
        this.data = data;
        this.left = null;
        this.left = null;
    }
}





package ListenInJava.Baume;


public class Tree {
    TreeNode root;


    Tree (){
        root = null;
    }


    public void add(int data){
        TreeNode t1 = new TreeNode(data);
        if(root == null){
            root = t1; 
            return;
        }
        TreeNode help = root;
        while(help != null){
            if(help.data > t1.data){
                
                if(help.left == null){
                    help.left = t1;
                    return;
                }
                help = help.left;
            } else{
                if(help.right == null){
                    help.right = t1;
                    return;
                }
              help = help.right;   
            }
        }
        return;
    }


 
}

ich möchte dann den baum in form von:

root

left right

usw. haben, aber wie genau könnte ich denn durch den baum iterieren mit einer schleife?

...zur Frage

Java: Hat Array ein Zeichen vom Char Element?

Hallo,

weiß jemand wie ich überprüfen kann, ob ein zweidimensionales String Array ein Zeichen von einem Char Array hat? Mein Ansatz ist so, allerdings wird das Zeichen[j] im contains rot markiert:

for (int i = 0; i < Array.length; i++) {
    for (int j = 0; j < Array.length; j++) {
        if (Array[j].contains(Zeichen[j]) == true) {
            Array[j] = "Zeichen";
        }
        else if (Array[j].contains(Buchstabe[j]) == true) {
            Array[j] = "Buchstabe";
        }
        else if (Array[j].contains(Sonderzeichen[j]) == true) {
            Array[j] = "Sonderzeichen";
        }
    }

...zur Frage

Java Array mit individuellem Namen und Größe erstellen?

Wie vom Code her. Mit individuell meine ich selbst bestimmbar.

...zur Frage

Elemente in Arrays (java) einfügen?

Hallo! Hier habe ich ein bisschen mit Arrays rumgespielt. Es soll eine 0 in das kopierte Array vor der jeweiligen Zahl eingesetzt werden, wenn diese kleiner als 10 ist. Wenn die Zahl größer als 10 ist, dann wird eine 1 vor die jeweilige Zahl gesetzt.

Wäre so ein Lösungsansatz akzeptabel oder haben sich Fehler eingeschlichen?

Muss dazu sagen, dass ich ein Anfänger bin :)

Danke im Vorraus!

Der Code lautet:

public class Array {
    public static void main (String[] args){
       Array arrayListe = new Array();
       int[] liste = {5, 20, -9};
       int[] rueckgabe = Array.veraendereArray[liste];
       for(int element : rueckgabe){
       System.out.println(element);
    }
 }
public static int [] veraendereArray(int[] liste){
   int[] rueckgabe = new int[liste.length+4];
   for(int i = 0; i <= liste.length; i++){
      if(element <10){
         rueckgabe[i+1]=0;
      }
      else{
         rueckgabe[i+1] =1;
      }
   }
}
 }

...zur Frage

wie berechne ich das Produkt eines Arrays?

Ich habe echt alle jetzt hinbekommen aber jetzt fehlt mir das Produkt ich wollte das so machen

int produkt = 0;

produkt *= Array[i]; system.out... (produkt);

aber da kommt immer ein Fehler in der console undzwar :** Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 at Array.main(Array.java:36) 0**

hier erstmal mein Code import java.util.Scanner;

public class Array {

public static void main(String[] args)
{
    // TODO Auto-generated method stub
    {
        Scanner input=new Scanner(System.in);
        int summe=0;
       

        System.out.print("Wie groß soll das Array sein?");
        int Arraygroeße=input.nextInt();

        int Array[]=new int[Arraygroeße]; // erstellt ein Array mit der
                                          // Größe
                                          // die man eingibt

        int i;
        for (i=0; i<Array.length; i++)
        {
            System.out.print("Feldwert an Stelle "+i+" eingeben: ");
            Array[i]=input.nextInt(); // soll den Wert einlesen den der
                                      // Nutzer
                                      // haben möchte bis das ganze Array
                                      // ausgefüllt ist
        }

        for (i=0; i<Array.length; i++)



            summe+=Array[i];
        System.out.println("Die Summe ist :"+summe);

        int max=Array[0];
        for (i=0; i<Array.length; i++)
            if (max<Array[i])
                max=Array[i];

        System.out.println("Größter Wert des Arrays ist "+max);

        int min=Array[0];
        for (i=0; i<Array.length; i++)
            if (min>Array[i])
                min=Array[i];

        System.out.println("Kleiner Wert des Array ist "+min);

        double mittel=0; // Mittelwert auf 0 setzen
        mittel=summe/Array.length; // Mittelwert berechnen durch Summe
                                   // geteielt durch die Anzahl der Zahlen
                                   // im Array
        System.out.println("Der Mittelwert beträgt:  "+mittel);
        
       
        input.close();

    }
  }
}

kann mir jemand bitte helfen wie ich das Produkt berechnen kann ? ( Java)

...zur Frage

Java void-Methode: If return, oder If else. Was ist professioneller?

Ein If mit Return:

public void printArray(int[] array) {
  if(array.length > 0) {
    System.out.println("Content of Array:");
    System.out.println(Arrays.toString(array));
    return;
  }
  System.out.println("Array is empty");
}

Ein If mit Else:

public void printArray(int[] array) {
  if(array.length > 0) {
    System.out.println("Content of Array:");
    System.out.println(Arrays.toString(array));
  } else {
  System.out.println("Array is empty");
  }
}

Was ist professioneller?

...zur Frage

Java arrays nebeneinander?

package com.companyenelogy;

import java.lang.reflect.Array;

public class Main {

    public static void main(String[] args) {

        int [] array = new int [10];

        System.out.print("Das Array beinhaltet folgende Zahlen: ");
        for (int i = 0; i < array.length; i++) {
          array[i]=i+1;

        }
        for (int i = 0; i < array.length; i++){
            System.out.print(array[i]);

        }

Bin ein Anfänger und wollte fragen wie ich es hin kriege die Array am ende nebeneinander kriege und nicht untereinander

...zur Frage

Java Char Array mit einem String ausffüllen?

Ich möchte ein Array von einer bestimmten Position aus mit einer Kette füllen, aber ich merke, dass das Array nicht durchlaufen wird. Wie kann ich das umsetzen? Hier ist mein Code:

Ich wollte ab Positon 64 ausfüllen, das heißt for int i = 64 bis die Position 91 in der result Tabelle.

Habe alles versucht, aber weiß nicht, was das Problem ist.

public class Ausffuellen {

public static void main(String[] args) {

char[] key = fuell("WXZJKACSRTPNOMLYVFHEGIUDBQ");

System.out.println(key[67]);

System.out.println(key[91]);

}

public static char[] fuell(String key) {

char[] result = new char[256];

for (int j = 0; j <=key.length(); j++) {

for (int i = 64; i < result.length - 164 ; i++){

result [i] = key.charAt(j);

}

return result;

}

...zur Frage

Wie mache ich daraus ein Strucktogramm?

import java.util.Scanner;
public class ChristmasTreeMain {
  Scanner scanner = new Scanner(System.in);
  int Tage;
  public static void main(String args[]) {
    ChristmasTreeMain tannenbaum = new ChristmasTreeMain();
    tannenbaum.inputTage();
    tannenbaum.drawTop(tannenbaum.Tage);
    tannenbaum.drawMiddle(tannenbaum.Tage);
    tannenbaum.drawBottom(tannenbaum.Tage);
  }
  public void inputTage() {
    boolean isInputValid = false;
    do {
      System.out.println("Bitte geben Sie einen Tage zwischen 1 und 24 ein:");
      while (!scanner.hasNextInt()) {
        System.out.println("Ungueltige Eingabe, geben Sie eine Zahl zwischen 1 und 24 ein.");
        scanner.next();
      }
      Tage = scanner.nextInt();
      if (Tage >= 1 && Tage <= 24) {
        isInputValid = true;
      } else {
        System.out.println("Ungueltige Eingabe, geben Sie eine Zahl zwischen 1 und 24 ein.");
      }
    } while (!isInputValid);
    scanner.close();
  }
  public void drawTop(int Tage) {
    for (int i = 2; i <= Tage; i++) {
      System.out.print(" ");
    }
    System.out.print("ii");
    System.out.println();
  }
  public void drawMiddle(int Tage) {
    int Dots = 0;
    for (int Tag = 1; Tag <= Tage; Tag++) {
       
      if (Tag > 2) {
        Dots += 2;
      }
   
      if (Tag > 1) {
   
        for (int i = 0; i < Tage - Tag; i++) {
          System.out.print(" ");
        }
   
        System.out.print("i/");
        for (int i = 0; i < Dots; i++) {
          System.out.print(".");
        }
        System.out.print("\\i");
   
        System.out.println();
      }
    }
  }
  public void drawBottom(int Tage) {
    for (int r = 1; r <= Tage; r++) {
      System.out.print("--");
    }
    System.out.println();
    for (int l = 2; l <= Tage; l++) {
      System.out.print(" ");
    }
    System.out.print("||");
  }
}

...zur Frage

Kann mir jemand folgenden Code erklären?

Hallo Leute,

in der Schule habe ich die Aufgabe bekomme, aus einer Liste, das größte und zweit größte Element raus zu picken. Im Internet habe ich hierfür eine Lösung gefunden, die funktioniert. Doch verstehen tu ich die Lösung nicht hundert Prozent. Ich verstehe nicht wie max und secondmax die Werte bekommen und die einzelnen Werte aus der Liste gefiltert werden.

// Ausgabe 3
int[]array={3,1,5,7,4,12,3,8,-2};


// Ausgabe 3
public static void sortiereElement(int[] array){
    int max = 0;
    int secondmax = 0;

    for(int i=0; i<array.length; i++){
        if(array[i] > max){
            secondmax = max;
            max = array[i];
        }else if(array[i] > secondmax){
            secondmax = array[i];
        }
    }

    // Ausgabe
    System.out.print("Aufgabe 3:" + "\t" + "\n");
    System.out.print("Größtes Element: " + max + "\t" + "\n");
    System.out.print("Zweitgrößtes Element: " + secondmax + "\t" + "\n");

}

--------------------------------------------------------------------
Ausgabe:
Aufgabe 3:	
Größtes Element: 12	
Zweitgrößtes Element: 8

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen