Insertion Sort als Array

Question

Frage:

Ich hab eine Aufgabe die wie folgt lautet:

Implementieren Sie wie oben diesmal den Insertion Sort 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.

Code:

Das habe ich schon:

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) {
//jetzt komme ich nicht mehr weiter, Kann da jemand helfen?
}

Answer 1

Array A, welches die zu sortierenden Werte enthält, soll nicht verändert werden. Die Werte von Array A sollen am Ende in Array B aufsteigend sortiert gespeichert sein.

Du könntest also einfach die Werte von Array A am Anfang der insertionSort Methode in das Array B speichern und dann Array B mittels InsertionSort sortieren.

Array A bleibt damit unverändert und Array B enthält am Ende die sortierten Werte.

Code:

 public static void insertionSort(int[] unsorted, int[] sorted) {
  // sorted Array mit Werten von unsorted füllen
  for (int i = 0; i < unsorted.length; i++) {
   sorted[i] = unsorted[i];
  }
 
  // InsertionSort
  for (int i = 1; i < sorted.length; i++) {
   int j = i;
   while ((j > 0) && (sorted[j] < sorted[j - 1])) {
    vertausche(sorted, j, j - 1);
    j--;
   }
  }
 }

 private static void vertausche(int[] a, int i, int j) {
  int tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
 }

Ein Beispiel Aufruf:

 System.out.println("unsorted: " + Arrays.toString(a));
 System.out.println("sorted: " + Arrays.toString(b));
 System.out.println("-------------------------------");
 insertionSort(a, b);
 System.out.println("unsorted: " + Arrays.toString(a));
 System.out.println("sorted: " + Arrays.toString(b));

Ergebnis:

unsorted: [-1967452523, 308775492, -205807514, 418077230, -1927516270, -492568803, -477760823, 1094445828, 1767611133, 19961656]

sorted: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

-------------------------------

unsorted: [-1967452523, 308775492, -205807514, 418077230, -1927516270, -492568803, -477760823, 1094445828, 1767611133, 19961656]

sorted: [-1967452523, -1927516270, -492568803, -477760823, -205807514, 19961656, 308775492, 418077230, 1094445828, 1767611133]