Insertion Sort mit Aray

[Garfild2015]

Aufgabe 2 – InsertionSort als Array
Implementieren Sie wie oben diesmal den InserstionSort als Array. Wählen Sie dazu zwei Arrays der Größe 10, z.B. A und B, wobei A unsortiert ist und mit zufälligen Zahlen belegt ist und B leer. Am Ende sollte das Array B aufsteigend sortiert sein.

Ich habe keine Ahnung wie ich Anfangen soll. Kann mir da jemand helfen?

 

[Flown]

Ich helfe hier mal aus:

public static void main(String[] args) {
  int[] a = new int[10];
  Random r = new Random();
  for (int i = 0; i < a.length; i++) {
    a[i] = r.nextInt();
  }
  int[] b = new int[10];
  System.out.println("unsorted: " + Arrays.toString(a));
  insertionSort(a, b);
  System.out.println("sorted: " + Arrays.toString(b));
}

public static void insertionSort(int[] unsorted, int[] sorted) {
  //insert code here
}

Die Frage ist, was verstehst du nicht?

 

[Garfild2015]

Ich habe immer Probleme anzufangen mit dem programmieren. Den Insortion Sort habe ich auch nicht wirklich verstanden

 

[Flown]

Man kann auch nichts programmieren, wenn man nicht verstanden hat, wie es funktioniert und was man machen sollte.
Google/YT hat dir hier keine Erklärungen geliefert?

 

[Garfild2015]

Man kann auch nichts programmieren, wenn man nicht verstanden hat, wie es funktioniert und was man machen sollte.
Google/YT hat dir hier keine Erklärungen geliefert?

Hab mir gerade mehrere angeschaut.
Ich glaube verstanden habe ich es jetzt. Aber mir fehlt immer noch irgendwie der Anfang des sortieren.
Vielleicht komme ich dann weiter 🙂

wäre das eine möglichkeit?:
for a in 0 -> l.lenght – 2
do
b = a + 1
tmp = l
while b > 0 AND tmp < l[b-1] do
l = l[b-1]
b – –
l = tmp

 

[Garfild2015]

Hab mir gerade mehrere angeschaut.
Ich glaube verstanden habe ich es jetzt. Aber mir fehlt immer noch irgendwie der Anfang des sortieren.
Vielleicht komme ich dann weiter 🙂

wäre das eine möglichkeit?:
for a in 0 -> l.lenght – 2
do
b = a + 1
tmp = l
while b > 0 AND tmp < l[b-1] do
l = l[b-1]
b – –
l = tmp

Ok ich hab mal irgendwie fürs Verständnis was zusammen gebastelt

public static void insertionSort(int[] unsorted, int[] sorted) {
        int sortedCount = 0; // Anzahl der bereits einsortierten Elemente
        
        // Jedes Element der unsortierten Liste durchgehen
        for (int element: unsorted) {
            boolean positionFound = false;     // Die folgende Schleife soll abgebrochen
                                            // werden, wenn die Position des Elements
                                            // gefunden wurde.
            // Von hinten alle Elemente der sortierten Liste durchgehen
            for (int index = sortedCount - 1; index >= 0 && !positionFound; index--) {
                // Falls das sortierte Element an der aktuellen Position
                // größer ist, als das Element, was einsortiert werden soll,
                // schieb das sortierte Element eine Position weiter nach hinten
                if (sorted[index] > element) {
                    sorted[index+1] = sorted[index];
                } else {
                    // Ansonsten das Element, was einsortiert werden soll, hinter
                    // dem aktuellen Element einsortieren
                    sorted[index+1] = element;
                    positionFound = true;
                }
            }
            
            // Falls alle Elemente der sortierten Liste größer waren, als das
            // einzusortierende Element, wurde das Element nicht in der Schleife
            // einsortiert und muss hier an die erste Position des Arrays gesetzt
            // werden.
            if (!positionFound) {
                sorted[0] = element;
            }
            
            sortedCount++;     // Zähler für sortierte Elemente erhöhen (alternativ könnte
                            // man auch eine Zählschleife benutzen)
        }
    }