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

1 Antwort

Valentin1720653

15.05.2023, 12:32

Naja was heißt "gut", das ist halt ein normaler Mergesort.

An sich hat ist Mergesort heutzutage kein guter Sortieralgorithmus mehr, da dieser O(n) zusätzlichen Speicher benötigt für eine n große Eingabemenge.

Soll heißen, auch wenn er im schlechtesten fall in O(n log(n)) läuft, Quicksort ist im avg-case schneller und benötigt keinen extra Speicher.

Das ist mitunter auch der Grund, warum Mergesort eigentlich nirgens implementiert ist.

Dazu sollte man bei diesen Algorithmen eher auf Bibliotheken zurückgreifen, da diese getestet sind und irgendwelche Randfälle besser abdecken.

Schau dir mal std::sort<>() aus der c++ Standardbibliothek an, der dort implementierte Algorithmus nennt sich "Introsort" und ist das schnellste was mit Vergleichsorientierten Sortierverfahren so geht.

Ist eine Mischung aus Quicksort, Heapsort und Insertionsort, und wenn man keinen stabilen Algorithmus braucht, auch den den man verwenden sollte.

Deadlock

Fragesteller

15.05.2023, 12:33

verstehst du mergesort auf anhieb, ich versteh den nicht ganz richtig

Valentin1720653

15.05.2023, 12:49

@Deadlock

Also ich habe ihn in meinem Studium behandelt,daher ja ich verstehe ihn.

Es gibt mehrere Versionen von ihm, einen rekursiven und einen nicht rekursiven.

Das Prinzip ist relativ simpel, eine Liste wird einfach rekursiv in n große Teillisten zerteilt, die dann Schritt für schritt richtig sortiert zusammengefügt werden.

https://youtu.be/ZRPoEKHXTJg

Bedenke hier aber dass die Rekursionen nacheinander abgearbeitet werden.

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

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

Merge Sort wie gehe ich weiter vor?

wenn ich das so auführe, dann wird folgendes ausgegeben:

aber weiseo wird das teilarray 7 6 oder auch 5 4 nicht weiter unterteilt?

und wie würde ich jetzt weiter vorgehen bei mergesort, das teilen funktioniert ja bis auf das letzte

public class Mersa {
    




    public static void main(String[] args) {
        int[] arr = {7,6,5,4,3,2,1};
        //System.out.println(Arrays.toString(arr));
        merser(arr);
    }


    public static void merser(int[] arr){
        mert(arr,0, arr.length-1);
    }
    
    public static void mert(int[] arr, int left, int right){
        if(left < right){
            
            int mid = (right+left)/2;
            mert(arr, left, mid);
            mert(arr, mid+1, right);
            for(int i = left; i <= right; i++){
                //dat hier ist debugging
                System.out.print(arr[i] + " ");
            } System.out.println();
            


        }



    }
}

...zur Frage

Wie "verschiebe" ich Werte von Arrays in C#?

Moin, liebe Community, die Aufgabenstellung ist folgend:

Wir haben einen INT-Array mit 10 Stellen und werden nach der reihe alle gefüllt (zB Array[0]=1; Array[1]=2; .... Array[9]=10;). Danach müssen die Werte um eines verschoben werden, dass es so aus: Array[0]=10; Array[1]=1;Array[2]=2; ..... Array[9]=9;

An sich ist das für mich nicht schwer, aber ich habe das Problem, dass ich nicht weiß, wie ich den alten Wert von "Array[9]" auf den neuen Wert von "Array[0]" schreibe

Mein Ansatz wäre wiefolgt:

int[] Array = new int[21]; int Zwischenspeicher = 0, Zwischenspeicher1 = 0; Random RNG = new Random();

for(int i = 0; i < Array.Length-1; i++) { //Array mit Zahlen füllen Array[i] = RNG.Next(1, 101); }

Array[Array.Length-1] = Zwischenspeicher1;

for(int i = Array.Length; i>0; i--) { //Array[i] wird in Zwischenspeicher verschoben Array[i+1] = Array[i]; } Array[0] = Zwischenspeicher1

//Sollte jetzt den ursprünglichen Wert //von Array[Array.Length-1] haben Console.Write("{0} -> {1}"Array[Array.Length-1] , Array[0]);

Hätte jemand einen guten Verbesserungsvorschlag für einen C#-Neuling? 😅 Danke schon im Vorraus

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

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

Array nach Wert prüfen rekrusiv (java)?

Hi sagen wir mal ich habe einen COde der so aussieht:

  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
   else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
     
 
  }
}

(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)

Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?

...zur Frage

C# Array erstellen - Wochentage und Temperatur?

Hallo,

ich habe ein kleines Problem beim erstellen eines Array. Bei dem Array sollen die Wochentage Montag bis Sonntag angezeigt werden und dann soll man zu jedem Tag eine Temperatur eintippen. Wie kann man Montag: Dienstag: Mittwoch: Donnerstag: ... anstelle von ,,Wochentage" angezeigt bekommen?

So viel habe ich schon geschafft:

public static void Main()

    {
        int anzahl = 7;
        

        int[] array = new int[anzahl];

        for (int i = 0; i < anzahl; i++)
        {

            Console.Write("{0}. Wochentag: ", i + 1);
            array[i] = Convert.ToInt32(Console.ReadLine());
        }
       
    }

Vielen Dank für Antworten.

...zur Frage

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

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

Array jeden wert addieren?

package com.companyenelogy;

import java.lang.reflect.Array;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        System.out.println("Geben sie ihr Array ein:");

        int[] array = new int[scanner.nextInt() ];

                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] + ",");
;
        }

        /*
        *Schreibe folgende Funktion: Jedem Wert im Array soll die 13 addiert werden (Verschlüsslung der Zahlen

ich kriege diese aufgäbe nicht hin ich muss jede Zahl in einen array mit 13 addieren aber wen ich was versuche wird nur die erste Zahl mit 13 addiert

...zur Frage

C# random array?

Ich habe hier in dem Code ein Random-Array erstellt. Wenn ich es starte, bekomme ich immer ein Array mit gleichen Zahlen. Wenn ich einen Breakpoint reinmache und es durchlaufen lasse, liefert es mir ein Array mit unterschiedlichen Zahlen. Ich weiß nicht mehr weiter! Kann mir bitte wer helfen? Danke.

Hier der Code:

static void Main(string[] args)
{
  int[] arr = new int[6];
  RandomArray(arr);

  for (int i = 0; i < arr.Length; i++)
  {
    Console.WriteLine(arr[i]);
  }

  Console.ReadKey();
}

static int[] RandomArray(int[] arr)
{
  for (int i = 0; i < arr.Length; i++)
  {
    Random zufallszahlen = new Random();
    int zahl = zufallszahlen.Next(1, 45);
    arr[i] = zahl;
  }

  return arr;
}

...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: Methode wird nicht erkannt?

Hallo, ich arbeite gerade an einem Text Adventure. Intellij erkennt meine Methoden nicht. Hat jemand Lösungsvorschläge?

Code:

public class main {
    public static void main (String[] args){
        player();
        enemies();
        cases();
    }
    public static void player() {
        String name = "Shadow";
        int health = 50;
        int damage = 30;
    }
    public static void enemies() {
            public static void dragon() {
                String name = "Barbaton";
                int health = 100;
                int damage = 40;
            }
            public static void lion() {
                String name = "Eon";
                int health = 85;
                int damage = 55;
            }
            public static void pig() {
                String name = "Memba";
                int health = 20;
                int damage = 5;
            }
            public static void frog() {
                String name = "Zee";
                int health = 5;
                int damage = 1;
            }
            public static void zebra() {
                String name = "Zoy";
                int health = 28;
                int damage = 18;
            }
            public static void monkey() {
                String name = "Bart";
                int health = 45;
                int damage = 38;
            }
            public static void fox() {
                String name = "Foxie";
                int health = 35;
                int damage = 24;
            }
        }
    }
    public static void cases() {
        int min = 1;
        int max = 8;
        int random_int = (int)Math.floor(Math.random()*(max-min+1)+min);
        if(random_int == 1){
            System.out.println("Du hast Barbaton(Drache) als Gegner bekommen.");
        }
        else if (random_int == 2){
            System.out.println("Du hast Eon(Löwe) als Gegner bekommen.");
        }
        else if (random_int == 3){
            System.out.println("Du hast Memba(Schwein) als Gegner bekommen.");
        }
        else if (random_int == 4){
            System.out.println("Du hast Zee(Frosch) als Gegner bekommen.");
        }
        else if (random_int == 5){
            System.out.println("Du hast Zoy(Zebra) als Gegner bekommen.");
        }
        else if (random_int == 6){
            System.out.println("Du hast Bart(Affe) als Gegner bekommen.");
        }
        else if (random_int == 7){
            System.out.println("Du hast Foxie(Fuchs) als Gegner bekommen.");
        }
        else {
            System.out.println("");
        }
    }
}

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen