Hi.
Gibt es einen einfachen Weg, wie man zwei sortierte Subarrays gleicher Länge M (die sich in einem nicht sortierten Array befinden) in ein sortiertes Array überführt mit der Beeinträchtigung dass nur ein Hilfsarray der Länge M genutzt werden kann?
Hierbei soll die Länge der Subarrays der Methode als Parameter übergeben werden.
Folgender Code funktioniert zwar, aber ist ziemlich umständlich (meiner Meinung nach)
Hierbei wird zuerst die gesamte linke Teilhälfte ins Hilfarray gepackt, anschließend werden alle Werte der rechten Teilhälfte mit den Werten im Hilfsarray verglichen. Was am Ende im Hilfsarray übrig bleibt wird dann ans Ende des Arrays gepackt.
Gibt es einen einfachen Weg, wie man zwei sortierte Subarrays gleicher Länge M (die sich in einem nicht sortierten Array befinden) in ein sortiertes Array überführt mit der Beeinträchtigung dass nur ein Hilfsarray der Länge M genutzt werden kann?
Code:
aus a = [2, 4, 6, 1, 3, 5] soll werden
a = [1, 2, 3, 4, 5, 6]
wobei nur aux = [0, 0, 0] als Hilfsarray genutzt werden darf
Hierbei soll die Länge der Subarrays der Methode als Parameter übergeben werden.
Folgender Code funktioniert zwar, aber ist ziemlich umständlich (meiner Meinung nach)
Hierbei wird zuerst die gesamte linke Teilhälfte ins Hilfarray gepackt, anschließend werden alle Werte der rechten Teilhälfte mit den Werten im Hilfsarray verglichen. Was am Ende im Hilfsarray übrig bleibt wird dann ans Ende des Arrays gepackt.
Java:
private static void merge(Comparable[] a, int lo, int hi, Comparable[] aux, int m)
{
int mid = lo + m - 1;
int i = lo;
int j = mid + 1;
//fill the auxiliary array with values of left subarray
int auxIndex = 0;
for(int k = i; k <= mid ; k++)
{
aux[auxIndex++] = a[k];
}
auxIndex = 0;
//merge both left and right subarrays
for(int k = lo; k <= hi; k++)
{
if(aux[auxIndex].compareTo(a[j]) >= 0)
{
a[k] = a[j++];
}
else
{
a[k] = aux[auxIndex++];
}
if(j > hi) break;
if(auxIndex > aux.length - 1) break;
}
//put the remaining items inside the array (if there are any)
for(int k = auxIndex + m; k < a.length && auxIndex <= aux.length - 1; k++)
{
a[k] = aux[auxIndex++];
}
}
public static void main(String[] args)
{
//Integer[] test = new Integer[]{9, 8, 4, 6, 1, 0, 4, 2};
//System.out.println(Arrays.toString(test));
//sortByBlock(test, 4);
//System.out.println(Arrays.toString(test));
int m = 3;
Integer[] a = new Integer[]{2, 4, 6, 1, 3, 5};
Integer[] aux = new Integer[m];
System.out.println(Arrays.toString(a));
merge(a, 0, 5, aux, m);
System.out.println("Nach sortierung:\n" + Arrays.toString(a));
}
}